iOS-选择排序（Selection sort）

选择排序

时间复杂度：O(n²)
稳定性：不稳定

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

1. 在未排序的序列中遍历找到最小的元素，放到已排序的序列末;
   起始整个序列都是未排序的，已排序的序列个数为0，经过第一轮遍历，已排序的序列中有一个最小的元素
2. 再从剩余未排序元素中继续寻找最小的元素，然后继续放到已排序的序列末；
   剩余未排序元素中最小的元素，是整个序列中第2小的元素，经过第二轮遍历，已排序的序列中有两个最小的元素
3. 重复第2步，直至所有元素均排序完成。

selectionSort.gif

时间复杂度分析

假设序列有n个元素，n>1，根据算法步骤，第1轮需在n个元素中遍历n次查找到最小的元素，第2轮需在剩余的(n-1)个元素中遍历(n-1)次找到最小的元素，… 第n-1轮需在剩余的2个元素中找到最小的元素，第n轮剩余1个元素放在已排序元素的末尾。

函数表达式为：
f(n) = n+(n-1)+…+2+1
f(n) = (n+1)*n/2
f(n) = (n²+n)/2

用大O表示法，忽略常量、低阶和常数系数。

时间复杂度为：O(n²)

算法代码（Swift）

func selectionSort(numbers: [Int]) -> [Int] {
    
    var sortedNumbers = numbers
    
    for i in 0..<(sortedNumbers.count-1) {
        
        print("\(sortedNumbers) (\(i)th circle begin)");
        
        var minIndex = i
        print("minIndex init with \(i)")
        
        for index in (i+1)..<sortedNumbers.count {
            
            if sortedNumbers[index] < sortedNumbers[minIndex] {
                minIndex = index
                print("minIndex changed to \(minIndex)")
            }
        }
        
        if minIndex != i {
            sortedNumbers.swap(minIndex, i)
            print("swap at \(minIndex) and \(i)")
        }
        
        print("")
    }
    
    return sortedNumbers
}

let numbers = [1, 4, 3, 2, 0, 5, 6, 7, 8, 9]
print("\(numbers) (random numbers)\n")

let sortedNumbers = selectionSort(numbers: numbers)
print("\(sortedNumbers) (selection sort result)\n")

终端打印结果：

[1, 4, 3, 2, 0, 5, 6, 7, 8, 9] (random numbers)

[1, 4, 3, 2, 0, 5, 6, 7, 8, 9] (0th circle begin)
minIndex init with 0
minIndex changed to 4
swap at 4 and 0

[0, 4, 3, 2, 1, 5, 6, 7, 8, 9] (1th circle begin)
minIndex init with 1
minIndex changed to 2
minIndex changed to 3
minIndex changed to 4
swap at 4 and 1

[0, 1, 3, 2, 4, 5, 6, 7, 8, 9] (2th circle begin)
minIndex init with 2
minIndex changed to 3
swap at 3 and 2

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (3th circle begin)
minIndex init with 3

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (4th circle begin)
minIndex init with 4

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (5th circle begin)
minIndex init with 5

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (6th circle begin)
minIndex init with 6

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (7th circle begin)
minIndex init with 7

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (8th circle begin)
minIndex init with 8

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (selection sort result)

为什么“选择排序”是不稳定的？

网上搜了一下，很多都说得云里雾里的，下面举个栗子🌰说明：

假设某学校积分入学剩余2个学位，A、B、C三位学生先后报名，积分分别为[A(90), B(90), C(100)]，积分从高到低排序，前两名获得入学资格，如果使用选择排序：
第一轮排序会将A和C交换，变成[C(100), B(90), A(90)]，此时排序已完成；
A、B同积分，但原来A比B优先报名的，本应优先取得入学资格，排序后却变成了B在A的前面，现实中必然是不公平的。

因此可以看出，选择排序是不稳定的。

参考资料

RUNOOB.COM-1.2 选择排序