选择排序算法详解及快速代码实现

选择排序算法详解

选择排序也是一个两级循环：

• 外层循环的边界为[0, array.count-1)，索引为 i。
• 内层循环的边界为[i+1, array.count)，索引为j，可以看到内层的范围也在不断递减，范围的前面正在变成返回，而背面保持不变。

具体方法是：

• 在外循环开始时，使用i作为最小值索引（可能不是数组的最小值）。
• 在内循环中查找当前内循环范围内的最小值，并与记录的最小值进行比较：
  • 如果与当前记录的最小值索引不同，则替换
  • 如果与当前记录的最小值索引不同记录的最小值索引 如果记录的最小索引相同，则不会被替换

我们来看看使用手写迭代的选择排序机制。使用的数组与上面交换排序和冒泡排序（非优化版本）的数组相同： [4, 1, 2, 5, 0] 当

i = 0时：

1. 注册当前最小值的索引为0，当前最小值为4。
2. 内循环开始，[1,5)之间的最小值变为0。 0的索引是4，与当前最小值的索引0不同，所以两者必须交换。交换后的数组：[0, 1, 2, 5, 4]。当前内循环结束，i++。当

i = 1时，：

1. 记录当前最小值的索引为1，当前最小值为1。
2. 内循环开始，最小值在[2.5)之间结果是1，与当前记录的最小值索引相同。也就是说后面没有任何小于1的东西，所以不发生交换。当前内循环结束，i++。当

i = 2时，：

1. 记录当前最小值的索引为2，当前最小值为2。
2. 内循环开始，最小值在[3.5)之间结果是2，与当前记录的最小值索引相同。也就是说后面没有任何小于1的东西，所以不发生交换。当前内循环结束，i++。当

i = 3时，：

1. 记录当前最小值的索引为3，当前最小值为2。
2. 内循环开始，取[4, 5之间的最小值)结果是4。 4的索引为4，与当前记录的最小值index3不同，所以两者必须互换。交换后的数组：[0, 1, 2, 4, 5]。当前内循环结束，i++。当

i = 4时，：不满足外循环的边界条件，不执行外循环，排序结束。

我们可以看到，对于同一个初始集，使用选择排序只进行了两次交换，因为它知道要替换的最小值，并且很少进行无意义的交换。

代码实现

我们用代码来实现上面的选择排序算法：

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

    for i in 0 ..< array.count - 1{
        
        var min = i
        
        for j in i + 1 ..< array.count {
            
            if array[j] < array[min] {
                min = j 
            }
        }
        
        //if min has changed, it means there is value smaller than array[min]
        //if min has not changed, it means there is no value smallter than array[min]
        if i != min {
            array.swapAt(i, min) 
        }
    }
    return array
}
复制代码

在上面的代码中可以看到，这里使用了minus。该变量记录当前的外循环。要比较的索引值。如果在当前外循环的内循环中发现小于该最小值的值，则将其替换。

我们用log来看看此时选择排序的替换次数：

original array:
[4, 1, 2, 5, 0]

advanced bubble sort...
after swap: [1, 4, 2, 5, 0]
after swap: [1, 2, 4, 5, 0]
after swap: [1, 2, 4, 0, 5]
after swap: [1, 2, 0, 4, 5]
after swap: [1, 0, 2, 4, 5]
after swap: [0, 1, 2, 4, 5]

selection sort...
after swap: [0, 1, 2, 5, 4]
after swap: [0, 1, 2, 4, 5]
复制代码

从上面的log我们可以看出两者的对比应该一目了然。

为了进一步验证选择排序的性能，作者在网上找到了两个工具：

• 计算程序运行时间的类：executionTimeInterval.swift
• 包含不同类型随机数的数组的分类Numbers : Array+Extension.swift

先看executionTimeInterval.swift的实现：

//time interval
public func executionTimeInterval(block: () -> ()) -> CFTimeInterval {
    let start = CACurrentMediaTime()
    block();
    let end = CACurrentMediaTime()
    return end - start
}


//formatted time
public extension CFTimeInterval {
    public var formattedTime: String {
        return self >= 1000 ? String(Int(self)) + "s"
            : self >= 1 ? String(format: "%.3gs", self)
            : self >= 1e-3 ? String(format: "%.3gms", self * 1e3)
            : self >= 1e-6 ? String(format: "%.3gµs", self * 1e6)
            : self < 1e-9 ? "0s"
            : String(format: "%.3gns", self * 1e9)
    }
}
复制代码

第一个函数以块的形式传递要测试运行时的函数，并返回函数运行时间。

第二个函数是CFTimeInterval的分类，它给秒添加了单位：毫秒以毫秒显示，微秒以微秒显示，大于1秒的值以秒显示。

使用方法是：将两个Swift文件拖到playground中的Resources文件夹中，点击打开playground：

var selectionSortedArray = [Int]()
var time4 = executionTimeInterval{
    selectionSortedArray = selectionSort(&originalArray4) //要测试的函数
}

print("selection sort time duration : \(time4.formattedTime)") //打印出时间
复制代码

我们来看看Array+Extension.swift类：

先介绍一种生成随机数组的方法：

import Foundation

extension Array {
    
    static public func randomArray(size: Int, maxValue: UInt) -> [Int] {
        var result = [Int](repeating: 0, count:size)
        
        for i in 0 ..< size {
            result[i] = Int(arc4random_uniform(UInt32(maxValue)))
        }
        
        return result
    }
}
复制代码

该方法只需要传递数组的大小和最大值即可生成一个不存在最大值超出的随机数组。

比如我们要生成一个数组长度为10，最大值为100的数组：

var originalArray = Array<Int>.randomArray(size: inputSize, maxValue:100)
//originalArray:[87, 56, 54, 20, 86, 33, 41, 9, 88, 55]
复制代码

现在，利用上面的两个工具，我们就可以根据需要生成测试用例数组并打印使用的了。算法的执行时间。我们现在生成一个数组长度为10，最大值为100的数组，然后使用优化的冒泡排序和选择排序来看看两者的表现：

original array:
[1, 4, 80, 83, 92, 63, 83, 23, 9, 85]

advanced bubble sort...
advanced bubble sort result: [1, 4, 9, 23, 63, 80, 83, 83, 85, 92] time duration : 8.53ms

selection sort...
selection sort result: [1, 4, 9, 23, 63, 80, 83, 83, 85, 92] time duration : 3.4ms
复制代码

我们现在把数组长度弄长一点：a length 100 就是最大值 200：

advanced bubble sort...
advanced bubble sort sorted elemets: 100 time duration : 6.27s

selection sort...
selection sort sorted elemets: 100 time duration : 414ms
复制代码

可以看到，两者相差大约 12 倍。这个差距已经是巨大的了。如果对选择进行排序需要 1 天，那么对气泡进行排序则需要 12 天。

现在我们已经了解了选择排序，知道它通过减少交换次数来提高排序算法的性能。

但是对于排序来说，除了交换操作之外，比较操作也需要时间：选择排序通过不断比较内循环得到当前内循环的最小值，然后进行后续的排序判断和操作。