常见内部排序的分析（面试）

插入排序

直接插入排序

每一次从无序子序列中取出一个数，插入有序子序列中，并保证有序子序列在放入该数前后保持有序。直接插入排序时间花费在找到插入位置以及移动数据上。

直接插入排序性能受到原序列的有序性影响较大，如果原序列已经有序，那么时间复杂度为$O(n)$；如果原序列与目标顺序完全相反，那么时间复杂度为$O(n^2)$​。算法的平均时间复杂度为$O(n_2)$，空间复杂度为$O(1)$​。

适用性：直接插入排序适用于顺序存储和链式存储。

稳定性：稳定。

折半插入排序

折半插入要保证原序列有序，然后向原序列中插入数据的可以减少比较次数，为$O(nlog_2n)$​，但是移动次数还是无法优化，故时间复杂度仍然为$O(n^2)$，空间复杂度为$O(1)$。

稳定性：稳定。

希尔排序

希尔排序的想法来自直接插入排序，直接插入排序性能受到原序列的有序性影响较大，希尔排序设定步长d从原序列中选出数据，将选出的数据组成新的序列并排序（不是将选出的数据真正的挑出来，然后用新的内存空间来存储，而是直接在原序列的基础上进行排序），这样对多个子序列重新排序之后，缩小步长d，重复上述过程直至d=1排序之后得到的就是排序完成的序列。

当n在某个特定的范围时，希尔排序的时间复杂度为$O(n^{1.3})$，空间复杂度为$O(1)$，最坏的情况下时间复杂度为$O(^2)$。

稳定性：不稳定。

交换排序

冒泡排序

冒泡排序每一趟排序可以确定一个最终元素的位置，就像泡泡一样可以不断的将一个数据“浮”到最顶/尾端。可以使用哨兵位来优化，当某一趟结束之后发现并没有交换数据位置的操作，就表明此时已经有序，结束排序。

最好、最坏的时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。

稳定性：稳定。

快速排序

快速排序每一次也可以确定一个最终元素（枢轴元素）的位置，只不过其位置不一定是在序列的首部或者尾部，也可能在中间的某一个位置。

快速排序使用双指针，假设序列的长度为n，将n-1个数据和1个数据比较（枢轴元素），并划分成大于该数据的部分和小于该数据的部分。然后递归该数据左右两部分，使用上述方式来重新将两个部分进行划分。

容易发现快排最终可以形成一个递归树，所以分析快排的空间复杂度除了额外的内存空间之外，还要考虑递归的深度。最好的情况下递归的深度为$O(log_2n)$，最坏的情况下为$O(n)$，平均情况下为$O(log_2n)$。

时间复杂度也和枢轴元素的选取有关，如果枢轴元素选取可以将序列比较均匀的分为两部分，那么时间复杂度为$O(nlog_2n)$；如果枢轴元素划分序列很不对称，那么快排将退化为冒泡排序（每一次都从中确定一个最大/最小元素），时间复杂度为$O(n^2)$。快排是平均性能最高的内部排序。

为了缓解枢轴元素选取不恰当而导致快排性能下降的问题，可以随机从序列中选取3个元素，然后取中间元素作为枢轴元素。

稳定性：不稳定。

选择排序

简单选择排序

简单选择排序每一趟可以从无序序列中选取出来一个最大或者最小值，这就意味着每一趟需要遍历无序序列，所以不论初始序列是否有序，时间复杂度均为$O(n^2)$，空间复杂度为$O(1)$。

稳定性：不稳定。

堆排序

堆排序需要考虑两个核心问题：

1. 如何将无序的序列构造成初始堆？
2. 输出堆顶元素之后，如何将剩余元素调整成新的堆？

堆使用完全二叉树实现，所以存储堆的数据结构应该是顺序表。

堆排序适合关键字较多的情况，比如在1亿个数中选出前100个最大值？

首先使用一个大小为100的数组，读入前100个数，建立小顶堆，然后依次读入余下的数，如果小于小顶堆则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中100个数即为所求。

空间效率：仅使用了常数个辅助单元，所以空间复杂度为$O(1)$。

时间复杂度：建堆时间为$O(n)$，之后有n-1次向下调整操作，每次调整的时间复杂度为$O(h)$，故在最好、最坏和平均情况下，堆排序的时间复杂度为$O(nlog_2n)$。

稳定性：不稳定。

其他类别

归并排序

假定待排序序列含有n个记录，则可以将其视为n个有序的子表，每个子表的长度为1，然后两两归并，得到若干个长度为2或1的有序表，继续两两归并，如此重复，知道合并成一个长度为n的有序表为止，这就是2路归并。

空间效率：在两个表相互合并的过程中，需要使用n个单元来存储，所以算法的空间复杂度为$O(n)$。

时间效率：每趟归并的时间复杂度为$O(n)$，共需要 $O(log_2n)$趟归并，所以算法的时间复杂度为$O(nlog_2n)$。

稳定性：稳定。

基数排序

假设长度为n的线性表中每个结点$a_j$的关键字由d元组（$k_j^{d-1},k_j^{d-2},···,k_j^1,k_j^0$）组成，比如每一个节点是一个三位数，节点$a_j$为312，那么关键字$k_j^2,k_j^1,k_j^0$分别为3，1，2。基数排序就是通过对每个节点中的三位数中的每一位进行比较，最终得到排序结果。为实现多关键字排序，通常使用两种方法：最高位优先，最低位优先。

在排序的过程中，使用r个队列$Q_0,Q_1,Q_2,...,Q_{r-1}$​，针对每一个节点中的每一位依次做一次“分配”和“收集”。如果每个节点中的记录都是一个不大于999的正整数，那么r=10，表示每一个记录的每一位的取值范围长度。

空间效率：一趟排序需要的辅助存储空间为r（r个队列：r个队头指针和r个队尾指针），但是以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为$O(r)$。

时间复杂度：基数排序需要进行d趟分配和收集，假设序列中最大记录由三位数构成，那么这里的d=3。一趟分配需要$O(n)$，一趟收集需要$O(r)$，所以基数排序的时间复杂度为$O(d(n+r))$，它与序列的初始状态无关。

稳定性：稳定。