阅读 9

排序算法笔记之选择排序

###选择排序

  • 选择排序的执行流程
    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)
      • 属于原地算法

源码及单元测试:https://github.com/yukifeng/suanfaStudy