内部排序

基本概念

内部排序是指排序期间数据元素全部存放在内存中的排序；

相应的，外部排序是指待排序的数据量很大，排序期间数据元素无法同时存放在内存中，必须在在排序过程中根据要求不断在内、外存之间移动的排序。

稳定排序（stable sort）：插入排序、冒泡排序、归并排序、计数排序、桶排序、基数排序。

不稳定排序（unstable sort）：希尔排序、快速排序、选择排序、堆排序。

在基数排序中，排序的稳定性显得尤为重要，关系到排序结果是否正确。

给每个输入元素加一个index，表示初始时的数组索引，当不稳定的算法排好序后，对于相同的元素重新按 index 排序，这样改进可以使得那些不稳定的算法也稳定。

原地算法（In-place sort 不占用额外内存或占用常数的内存）：插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。

非原地算法（Out-place sort）：归并排序、计数排序、桶排序、基数排序。

当需要对大量数据进行排序时，In-place sort就显示出优点，因为只需要占用常数的内存。

设想一下，如果要对10000个数据排序，如果使用了Out-place sort，则假设需要用200G的额外空间，则一台老式电脑会吃不消，但是如果使用In-place sort，则不需要花费额外内存。

基于比较的排序都是遵循“决策树模型”，而在决策树模型中，可以证明基于比较的排序算法最坏情况下的运行时间为 O(nlogn)，证明的思路是因为将 n 个序列构成的决策树的叶子节点个数至少有 n!，因此高度至少为 nlogn。

虽然能够理想情况下能在线性时间排序，但是每个排序都需要对输入数组做一些假设，比如计数排序需要输入数组数字范围为[0,k]等。

待排序列初始状态对时间复杂度的影响，乱序，基本正序，基本逆序等。

一趟排序能否确定一个元素的最终位置，会不会产生有序子序列（局部有序、全局有序）。