iOS 选择排序（Selection Sort）

algo

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

算法过程描述

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

动图演示

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²)
空间复杂度为：并未开辟额外空间, 所以为O(1)
稳定性: 不稳定

代码实现(Swift)

假设要对以下数组进行选择排序:

let numbers = [1, 4, 3, 2, 0, 5, 9, 7, 8, 6]

对n个元素进行选择排序，主要是确定每一轮的最小(大)值的角标, 来和该轮的第一个元素进行位置交换, 如果相同, 则不需要交换:

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 j in i + 1..<sortedNumbers.count {
            
            if sortedNumbers[minIndex] > sortedNumbers[j] {
                minIndex = j
                print("minIndex changed to \(minIndex)")
            }
        }
        
        if minIndex != i {
            sortedNumbers.swapAt(minIndex, i)
            print("swap at \(minIndex) and \(i)")
        }
    }
    return sortedNumbers
}

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

终端打印结果：

[1, 4, 3, 2, 0, 5, 9, 7, 8, 6] (0th circle begin)
minIndex init with 0
minIndex changed to 4
swap at 4 and 0
[0, 4, 3, 2, 1, 5, 9, 7, 8, 6] (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, 9, 7, 8, 6] (2th circle begin)
minIndex init with 2
minIndex changed to 3
swap at 3 and 2
[0, 1, 2, 3, 4, 5, 9, 7, 8, 6] (3th circle begin)
minIndex init with 3
[0, 1, 2, 3, 4, 5, 9, 7, 8, 6] (4th circle begin)
minIndex init with 4
[0, 1, 2, 3, 4, 5, 9, 7, 8, 6] (5th circle begin)
minIndex init with 5
[0, 1, 2, 3, 4, 5, 9, 7, 8, 6] (6th circle begin)
minIndex init with 6
minIndex changed to 7
minIndex changed to 9
swap at 9 and 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)

当测试数据修改为:

let numbers = [1, 4, 3, 2, 0, 5, 6, 7, 8, 9]

终端打印结果：

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

可以看出, minIndex 为3之后已经成为了有序数组, 但是还是继续了排序的操作;

细想一下，每次扫描未排序区间只选取一个最小值，那么是否可以每次扫描时选择一个最小元素和一个最大元素，分别放置在有序区间的尾部和尾部有序区间的头部呢？

代码优化

在循环选取时，每次扫描未排序区间分别选择最小、最大值放于数组始、末位置, 当最小元素的位置+1 =最大元素的位置时，数据已经全部有序，可以提前退出:

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)")
        
        // 最大下标也要随着最小下标的增加而对应减小
        var maxIndex = sortedNumbers.count - i - 1
        print("maxIndex init with \(maxIndex)")
        
        // 内部循环比较, 也是在双向缩小范围
        for j in i + 1..<sortedNumbers.count - i {
            
            if sortedNumbers[minIndex] > sortedNumbers[j] {
                minIndex = j
                print("minIndex changed to \(minIndex)")
            }
            
            if sortedNumbers[maxIndex] < sortedNumbers[j] {
                maxIndex = j
                print("maxIndex changed to \(maxIndex)")
            }
        }

        if minIndex != i {
            sortedNumbers.swapAt(minIndex, i)
            print("swap at \(minIndex) and \(i)")
        }
        
        if maxIndex != sortedNumbers.count - i - 1 {
            sortedNumbers.swapAt(maxIndex, sortedNumbers.count - i - 1)
            print("swap at \(maxIndex) and \(sortedNumbers.count - i - 1)")
        }
        
        // 一定要交换完成 才判断是否符合提前退出的条件
        if (minIndex + 1 == maxIndex) {
            break
        }
    }
    return sortedNumbers
}

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

终端打印结果：

[1, 4, 3, 2, 0, 5, 6, 7, 8, 9] (0th circle begin)
minIndex init with 0
maxIndex init with 9
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
maxIndex init with 8
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
maxIndex init with 7
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
maxIndex init with 6
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (4th circle begin)
minIndex init with 4
maxIndex init with 5

[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的前面，现实中必然是不公平的。

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

回目录:常用的排序算法

结语

路漫漫其修远兮，吾将上下而求索~

作者简书

作者掘金

作者GitHub

.End