选择排序

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

工作原理

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

例子

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

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

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

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

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

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

7.排序完成

代码

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)。