选择排序

• 类似插入排序，也是分为已排序区间，和未排序区间，每次从未排序区间中找到最小的元素，放到已排序区间末尾。
  

复杂度

• 最好时间复杂度O(N^2)

• 最坏时间复杂度O(N^2)

• 平均时间复杂度O(N^2)

• 是不稳定排序，因为每次选择阶段选出最小元素后，交换阶段会破坏原序列的顺序，例如[5,8,5,2,9]中有两个5, 第一次选出最小的2后，会和第一个5交换，那么原序列中的两个5就换顺序了

• 因为不稳定，所以不常用选择排序

插入排序与选择排序对比

• 其实类似打扑克牌，分为选择和插入共2个阶段

• 选择排序：是选择阶段选出最小的，插入阶段直接append

• 插入排序：是选择阶段随便选一个，插入阶段放到有序的位置

冒泡排序和插入排序对比

• 两者的交换次数是相同的，均为序列的逆序数，但冒泡排序的交换操作需4个指令，而插入排序仅需1个指令，故插入排序时间复杂度更优

// 冒泡排序的交换指令
if a[k] > a[k+1] {
    int tmp = a[k];
    a[k] = a[k+1];
    a[k+1] = tmp;
    hasExchange = true;
}

// 插入排序的交换指令
if a[k] > value {
    a[k+1] = a[k]
} else {
    break;
}

• 若逆序数为k，则冒泡为4k指令时间，而插入为1k指令时间

• 例如6长度的数组，冒泡排序需209ms, 插入排序仅需155ns

2022/05/08 21:53:30 cost: 209ns
2022/05/08 21:53:30 BubbleSort: [6 5 4 3 2 1]
2022/05/08 21:53:30 cost: 155ns
2022/05/08 21:53:30 InsertSort: [1 2 3 4 5 6]

- 例如200长度的数组，冒泡排序需26us, 插入排序仅需6us

2022/05/08 21:57:32 cost: 26.684µs
2022/05/08 21:57:32 cost: 6.568µs

- 所以如果做极致优化，应选插入排序，且其还可更优化(希尔排序)

这些排序函数，主要是扩展视野，但有些编程语言的内部排序函数实现会用到(如插入排序)

思考

之前讲的都是用array，如果换成linked-list实现的话(仅能交换node，不能改node的值)

• 冒泡排序比较次数不变，但list交换操作更复杂

• 插入排序比较次数不变，交换次数从array的O(N)下降为list的O(1)，但若需支持升降序的话会有链表逆序则为O(N)

资料

算法图解