选择排序

8/17/2020 数据结构与算法基础

选择排序就是重复“从待排序的数据中寻找最小值,将其与序列最左边的数字进行交换” 这一操作的算法。在序列中寻找最小值时使用的是线性查找。

754476-06a4090ebc2f5655

# 工作原理

  1. 找到数组中的最小数字。 从索引 0 开始,遍历数组中的所有数字,并追踪最小数字的位置。
  2. 使用索引 0 处的数字交换最小数字。现在,已排序部分仅包含索引 0 处的数字。
  3. 转到索引 1 处。
  4. 找到数组其余部分中的最小数字。 从索引 1 开始查看。再次循环直到数组结束并追踪最小数字。
  5. 使用索引 1 处的数字交换最小数字。现在,已排序部分包含两个数字,索引 0 和索引 1。
  6. 转到索引 2 处。
  7. 从索引 2 开始,找到数组其余部分中的最小数字,并将其与索引 2 处的数字交换。现在,数组从索引 0 到 2 已排序; 此范围包含数组中的三个最小数字。
  8. 并继续,直到没有数字需要排序。

# 例子

1.对数字 1~9 进行排序 -w320

2.使用线性查找寻找最小值,于是找到了最小值 1。

-w299

3.将最小值 1 与序列左边的 6 进行交换,最小值 1 归位。 -w573

4.然后在余下的数据中继续寻找最小值。这次我们找到了最小值 2。 -w314

5.将数字 2 与左边第 2 个数字 6 进行交换,最小值 2 归位。 -w313

6.重复同样的操作直到所有数字都归位为止。 -w304

7.排序完成 -w308

# 代码

func selectionSort(_ array: [Int]) -> [Int] {
    guard array.count > 0 else {return array}

    var tmpArr = array
    for x in 0..<tmpArr.count - 1 {
        var min = x
        for y in x+1 ..< tmpArr.count {
            if (tmpArr[y] < tmpArr[min]) {
                min = y
            }
        }
        if x != min {
            tmpArr.swapAt(x, min)
        }
    }
    return tmpArr
}

let list = [5,8,3,4,6]
selectionSort(list)

# 性能

选择排序使用了线性查找来寻找最小值,因此在第 1 轮中需要比较 n - 1 个数字,第 2 轮需要比较 n - 2 个数字......到第 n - 1 轮的时候就只需比较 1 个数字了。因此,总的比 较次数与冒泡排序的相同,都是(n-1)+(n-2)+...+1 ≈ n^2/2 次。

每轮中交换数字的次数最多为 1 次。如果输入数据就是按从小到大的顺序排列的, 便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样,都为 O(n^2)

选择排序很容易理解,但执行速度慢 O(n^2)。它比插入排序更糟,但优于冒泡排序。查找数组其余部分中的最低元素很慢,特别是因为内部循环将重复执行。

堆排序使用与选择排序相同的原则,但使用了一种快速方法在数组的其余部分中查找最小值。 堆排序性能是 O(nlogn)。

上次更新: 9/10/2024, 11:42:33 PM