选择排序

参考链接

• 选择排序：简单选择排序（Simple Selection Sort）

• 白话经典算法系列之四 直接选择排序及交换二个数据的正确实现

基本思想

选择排序和插入排序类似，都将数据分为有序区和无序区，不同的是选择排序是从无序区选一个最小的元素直接放到有序区的最后。

设数组为a[0…n-1]。

• 初始时，数组全为无序区为a[0..n-1]。令i=0
• 在无序区a[i…n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。
• i++并重复第二步直到i==n-1。排序完成。

算法的实现

extension Array where Element: Comparable {
    mutating func selectSort() {
        for i in 0 ..< count {
            var minIndex = i
            for j in (i + 1) ..< count where self[j] < self[minIndex] {
                minIndex = j
            }

            if minIndex != i {
                swapAt(i, minIndex)
            }
        }
    }
}

改进（二元选择排序）

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置，从而减少排序所需的循环次数。

改进后对n个数据进行排序，最多只需进行n/2趟循环即可。具体实现如下：

extension Array where Element: Comparable {
    mutating func selectSortBetter() {
        var next, end, minIndex, maxIndex: Int
        /*
         1. 整个排序过程共进行n/2趟
         2. 每次循环，会找出最小和最大的元素，与开始和结束位置的元素交换
         */
        for begin in 0 ..< count / 2 {
            end = count - 1 - begin
            minIndex = begin
            maxIndex = begin

            next = begin + 1
            while next <= end {
                if self[next] < self[minIndex] {
                    minIndex = next
                    continue
                }

                if self[next] > self[maxIndex] {
                    maxIndex = next
                }
                next += 1
            }

            /*
             先放最小的元素
             因为会将最小元素和第一个元素交换
             所以如果第一个元素就是最大的元素，那么max应该指向交换后的索引
             */
            if minIndex != begin {
                swapAt(begin, minIndex)
                if maxIndex == begin {
                    maxIndex = minIndex
                }
            }

            if maxIndex != end {
                swapAt(end, maxIndex)
            }
        }
    }
}