7.6.1 内部排序算法的比较
各种内部算法的比较及应用
基于四个因素进行对比：时间复杂度，空间复杂度，算法的稳定性，算法的过程特征。
一、从时间复杂度看
1、简单选择排序、直接插入排序和冒泡排序的平均情况下的时间复杂度都为O(n^2)，并且实现过程比较简单，但直接插入排序和冒泡排序在最好的情况下时间复杂度可以达到O(n)。而且简单选择排序则与序列的初始状态无关。
2、希尔排序作为插入排序的拓展，对较大规模的排序都可以达到很高的效率，但目前未得出其精确的渐进时间。
3、堆排序是利用了一种称为堆的数据结构，可以在线性时间内完成建堆，而且在O(nlog2n)内完成排序过程。
4、快速排序时基于分治的思想，虽然在最坏的情况下快速排序时间会达到O(n^2)，但快速排序的平均性能可以达到O(nlog2n)，在实际应用中，常常优于其他排序算法。
5、归并排序同样是基于分治的思想，但由于其分割子序列与初始序列的排序无关，因此它的最好、最坏和平均时间复杂度均是O(nlog2n)。
二、从空间复杂度来看
1、简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需要借助常数个辅助空间。
2、快速排序在空间上只使用一个小的辅助栈，用于实现递归，平均情况下大小为O(log2n)，当然在最坏的情况下，可能会增长到O(n)。
3、二路归并排序在合并操作中需要借助较多的辅助空间用于复制，大小为O(n)。
三、从稳定性看
插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法
而简单选择排序（2，2，1 ->1，2，2）
快速排序（3,2,2->2,2,3）
希尔排序（当相同的关键字被划分到不同的子表是，可能会改变他们之间的相对次序，如3,2,2->2,2,3）
堆排序（1,2,2->1,2,2）
都是不稳定的排序方法。
三、从过程特性来看
冒泡排序和堆排序每次循环后能产生当前的最大值和最小值
快速排序一次循环就确定一个元素的最终位置
算法种类 | 最好情况 | 平均情况 | 最差情况 | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|---|
直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 是 |
冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 是 |
简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 否 |
希尔排序 | O(1) | 否 | |||
快速排序 | O(nlog2 n) | O(nlog2 n) | O(n^2) | O(nlog2 n) | 否 |
堆排序 | O(nlog2 n) | O(nlog2 n) | O(nlog2 n) | O(1) | 否 |
2-路归并排序 | O(nlog2 n) | O(nlog2 n) | O(nlog2 n) | O(n) | 是 |
基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 是 |
其中r表示数字的位数，n表示数字的个数