排序算法笔记之选择排序

###选择排序

• 选择排序的执行流程
  1. 从序列中找出最大（或最小）的元素，与最末尾的元素交换位置
  2. 排除已经排序好的尾部序列，重复上一步操作

for end in (1..<array.count).reversed() {
            /// 最大元素的位置
            var max = 0
            for begin in 1...end {
                cmpCount += 1
                if array[begin] >= array[max] {
                    max = begin
                }
            }
            let temp = array[end]
            array[end] = array[max]
            array[max] = temp
            swapCount += 1
        }

• 选择排序的优化

  • 构建堆来选择最大值
  • 即堆排序

• 选择排序的稳定性

  • 选择排序属于不稳定的排序
  • 假设数组为[10,1(a),1(b),1(c),1(d),1(e)]，第一次排序后为：[1(e)，1(a),1(b),1(c),1(d)，10]，e标记的1元素与其他元素的相对位置发生变化，所以为不稳定的排序

• 选择排序的时间复杂度和空间复杂度

  • 时间复杂度 采用两层循环，时间复杂度为O(n^2)
  • 空间复杂度
    • O(1)
    • 属于原地算法

源码及单元测试：github.com/yukifeng/su…