-------------------siwuxie095
排序算法总结
| 平均时间复杂度 | 原地排序 | 额外空间 | 稳定排序 |
插入排序（Insertion Sort） | O(n^2) | √ | O(1) | √ |
归并排序 （Merge Sort） | O(n*lgn) | × | O(n) | √ |
快速排序（Quick Sort） | O(n*lgn) | √ | O(lgn) | × |
堆排序（Heap Sort） | O(n*lgn) | √ | O(1) | × |
（1）平均时间复杂度
1）插入排序在数组已经是有序的情况下，时间复杂度是 O(n) 级别的
2）快速排序在极其特殊的情况下，将退化到 O(n^2)，可以采用随机
化的方式来处理，使得这种情况发生的可能性极其极其低
3）总体而言，快速排序是更加快的一种排序算法
对于归并排序、快速排序、堆排序 这三种 n*lgn 级别的排序算法来说，
它们也有常数上的差异，而快速排序在这个常数上相对占优
正因为如此，一般系统级别的排序都是使用快速排序来实现的，特别的，
对于可能有大量重复键值的排序，可以使用三路快速排序
（2）原地排序
归并排序必须开辟额外的空间来完成归并的过程，进而完成整个归并
排序。所以，如果一个系统对空间相对比较敏感的话，归并排序可能
就并不适合
（3）额外空间
1）对于插入排序和堆排序来说，它们都可以通过在数组上直接交换元素
来完成，所以它们所需要的额外空间是 O(1) 级别的，即 常数级别的一个
空间
2）而快速排序所需要的额外空间是 O(lgn) 级别的，这是因为快速排序是
采用递归的方式来进行排序，递归的过程一共有 lgn 层，相应的就需要 lgn
的栈空间来保存每一次递归过程中的临时变量，以供递归返回的时候继续
使用
3）归并排序也可以通过递归来实现，因此归并排序所需要的额外空间是
O(n)+O(lgn) 的，由于 lgn 比 n 小，lgn 可以忽略不计
（4）稳定排序
稳定排序：对于相等的元素，在排序后，原来靠前的元素依然靠前。
相等元素的相对位置没有发生改变
所谓排序算法的稳定性是和具体实现相关的，也就是说，如果实现
的不好的话，很有可能将插入排序和归并排序实现成了一个不稳定
的排序算法
另外，排序算法的稳定性可以通过自定义比较函数，使得排序算法
不存在稳定性的问题
如：现在就想使用快速排序，但是又要顾及稳定性，应该怎么做呢？
以学生分数的排序为例，排序的主要键值是学生的分数，希望通过
排序算法的稳定性，来使得相同分数的学生是按照姓氏的字典序来
进行排列的
bool operator<(const Student &otherStudent)
{
//在分数相同时，字母小的排在前面（即 字典序更靠前） return score != otherStudent.score ? score < otherStudent.score : name < otherStudent.name;
} |
在判断两个学生之间的分数大小关系的时候，要先看他们的分数是
不是相等，如果不等的话，就看分数就好了，如果相等的话，就看
他们名字的字典序
不难看出，在比较函数中，其实相当于多比较了一下，正因为如此，
效率有所损耗，不过在一般情况下，由于使用现代的是计算机，这
个效率的损耗，完全是可以承受的
插入排序和归并排序都是稳定的排序算法，通常在系统级别的类库
中，要实现实现一个稳定的排序，通常选择的是归并排序
后记
对于上面四个指标来说，每种排序，都各有优劣，各有侧重
但是不是存在一种神秘的排序算法，使得上面四个指标都是最优呢？
即 平均时间复杂度是 O(n*lgn) 级别的，且在有序的情况下还能降为
O(n) 级别的，且对于任何情况下都不可能退化成 O(n^2) 级别，且
是原地排序，且额外使用空间是 O(1)，且是一个稳定的排序
到现在（2017/6/6）为止，计算机科学家们，还没有发现这样一种
排序算法。不过理论上，这种排序算法是存在的
【made by siwuxie095】