关于算法:聊一聊插入排序和比较排序

简介

插入排序和比拟排序是排序算法中比拟根底和简略的两种，其工夫复杂度均为 $O(N^{2})$，在剖析算法工夫复杂度时，咱们往往会只会剖析比拟开销，然而替换开销也的确存在。这里我将综合比拟开销和替换开销，来剖析一下插入排序和比拟排序的区别，以及何时抉择插入排序？何时该抉择比拟排序？

我之前的文章 排序算法详解 里给出了几个根本排序算法的JavaScript 版本 实现，感兴趣的也能够移步。

空间复杂度

插排和选排的均在替换时应用了一个长期空间，其空间复杂度均为 $O(1)$。而且插排和选排在排序时同时保护了一个已排序的有序列表和一个待排序的无序列表，不同在于：

• 插排从无序列表中取第一个数，与有序列表的数顺次比拟，有序列表的已排数据的地位均可能发生变化。
• 选排从无序列表中取最小数，只和无序列表中第一个数替换，此时无序列表第一个数归于有序列表（相当于最初一个数）。

在每一轮排序过程中，均须要有一个长期空间用来存储无序列表提取的这一个数，用于将来的替换。

工夫复杂度

家喻户晓，插排和选排的工夫复杂度均为 $O(N^{2})$。咱们在剖析工夫复杂度的时候，其实都是剖析的比拟工夫复杂度，然而计算机做算法的时候除了比拟，还有替换，并不是说替换工夫复杂度不重要，而是它大部分状况绝对于比拟复杂度能够疏忽，至于起因，接下来联合比拟和替换开销，来剖析插排和选排，天然就明确了。

比拟复杂度比照

• 插入排序

  • 最差状况：最差状况下反向有序，每一轮插入，都须要顺次比拟到有序列表的第一个数，第一轮比拟 0 次，第二轮比拟 1 次，第 N 轮比拟 N - 1 次。一共比拟 $\frac{N \times (N-1)} {2}$ 次，复杂度 $O(N^{2})$
  • 最好状况：最好状况下有序，每一轮插入，都只须要比拟 1 次，一共比拟 $N$ 次，复杂度 $O(N)$
  • 均匀状况：均匀状况下，每一轮插入，假如顺次比拟到有序列表的两头地位，一共比拟 $\frac {N \times (N-1)} {4}$ 次，复杂度 $O(N^{2})$
• 抉择排序

  抉择排序比拟次数是固定的，每一轮都须要从待排序的无序列表中选取一个最小（或最大）的数，选取中都须要比拟到最初一个元素能力失去后果。第一轮比拟 N - 1 次，第 N 轮比拟 0 次。一共比拟 $\frac {N \times (N-1)} {2}$ 次，复杂度 $O(N^{2})$

因而能够得出结论：在最差状况下，两者复杂度一样。在最好状况下，两者复杂度差别是比拟大的（1 个次方），而在 均匀状况下，插排的比拟次数也只是选排的一半。这也是对于插排和选排的通用论断，个别状况下插排优于选排，次要就在于插排是插入有序列表，而选排是须要在无序列表中抉择一个最大值（或最小值），设想一下咱们斗地主摸牌，摸到一张牌咱们是能够马上从小到大判断插入到哪的（这里假如只能从小到大比拟），而不用每一张牌都比照一下。

然而下面的论断只探讨了比拟复杂度，其实在[为什么说均匀状况下，插入排序比抉择排序快? – 莫涛的答复 – 知乎
](https://www.zhihu.com/questio…Stack Overflow 上，也有人对这种答复中不谈替换示意纳闷，上面咱们再来剖析一下替换复杂度。

替换复杂度比照

• 插入排序

  • 最差状况：每一次比拟完都须要替换。第一轮替换 0 次，第二轮替换 1 次，第 N 轮替换 N - 1 次。一共替换 $\frac{N \times (N-1)} {2}$ 次，复杂度 $O(N^{2})$
  • 最好状况：每一次比拟完都无需替换，总共替换 $0$ 次，复杂度 $O(0)$
  • 均匀状况：每一轮都插入到两头地位，总共替换次数为 $\frac{N \times (N-1)} {4}$ 次，复杂度 $O(N^{2})$

• 抉择排序

  • 最差状况：每一轮都须要替换，总共替换 $N$ 次，复杂度 $O(N)$
  • 最好状况：每一轮都无需替换，总共替换 $0$ 次，复杂度 $O(0)$
  • 均匀状况：有一半轮次须要替换，总共替换 $\frac N 2$ 次，复杂度 $O(N)$

替换复杂度的比照中咱们能够得出：最好状况下两者都无需替换，然而在最差和均匀状况下，插入排序的替换次数都高于抉择排序，差别为一个次方。能够看出差别还是很大的，单从这样来看，是无奈疏忽其影响的。

影响工夫复杂度的其余因素

其实，在《算法导论》一书中还提到了一个算法性能剖析依赖的以下因素：

1. 待排项数
2. 这些项已排序水平
3. 项值的限度
4. 计算机体系结构
5. 应用的存储设备品种（主存，磁盘或磁带）

回到这个例子中，咱们能够假如疏忽硬件的影响、项值无限度。而已排序水平随机（也就是选用均匀复杂度，不过个别算法剖析都采纳最坏状况下的复杂度作为瓶颈进行剖析），因而剖析因素只剩下待排项数 N，能够应用下面的剖析给出论断。

论断

插入排序和比拟排序谁更优？次要在于比拟开销和替换开销的量级：

1. 如果两者量级相当，则插入排序优于抉择排序
2. 如果比拟开销量级小于替换开销，则抉择排序优于插入排序
3. 如果比拟开销量级大于替换开销，如果差异不大则难以比拟，如果差别较大，则能够疏忽替换复杂度，此时插入排序优于抉择排序

事实上，替换个别间接替换内存地址（指针）而不是替换实在的数据，而比拟则须要 CPU 的一些运算。这里的一个答复便给出了自定义赋值函数，如果间接替换数据，当数据量过大，替换开销大大增加，此时插入排序反而不如抉择排序，因为其替换次数均匀状况下和抉择排序不在一个量级。

当然，因为替换排序进行了过多的替换次数（也就是写操作），如果应用 Flash Memory，则须要额定留神，因为 Flash Memory 的擦除次数无限，过多的写操作会耗费其擦除次数，从而耗费 Flash Memory 的寿命。

总结 & 参考

个别状况下，插入排序的确优于抉择排序，但也有须要留神的点，而不单单是只判断比拟复杂度那么简略。须要咱们理解分明再做判断。

文章参考了以下材料：

1. Insertion Sort vs. Selection Sort
2. 为什么说均匀状况下，插入排序比抉择排序快? – 知乎
3. When should one use Insertion vs. Selection sort?