一、排序算法总结
| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 基本原理 | ||
|---|---|---|---|---|---|---|
| 最坏性能 | 最好性能 | 平均性能 | ||||
| 插入排序 | O(n*n) | O(n) | O(n*n) | O(1) | 稳定 | A[1...j]已经排好序，现在将A[j+1]插入到合适位置 |
| 堆排序 | O(n*lgn) | O(n*lgn) | O(n*lgn) | O(1) | 不稳定 | 维护一个最大堆，每次把堆首元素放入最终正确位置 |
| 归并排序 | O(n*lgn) | O(n*lgn) | O(n*lgn) | O(n*lgn) | 稳定 | 递归对左子序列和右子序列进行排序，然后合并 |
| 快速排序 | O(n*n) | O(n*lgn) | O(n*lgn) | O(1) | 不稳定 | 根据某个划分值划分得到左右两个子序列，递归排序 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 | 在每个元素的值介于0-k的前提下，统计小于等于每个元素的总个数，这个总个数也是该元素的最终正确位置 |
| 基数排序 | O(d(k+n)) | O(d(k+n)) | O(d(k+n)) | O(d(k+n)) | 稳定 | 一个d位元素，然后从低位到高位进行计数排序 |
| 桶排序 | O(n*n) | O(n) | O(n) | O(n+k) | 稳定 | 先对数据进行乘等某种处理，将之分到有序桶中，第一层排序；然后对每个桶中的元素进行插入排序，第二层排序 |
| 冒泡排序 | O(n*n) | O(n) | O(n*n) | O(1) | 稳定 | 左右交换，接力棒似地传导，把最大的元素放在最后正确的位置 |
二、几点说明
2.1、空间复杂度
空间复杂度是指额外还需要多少空间，本来保存元素的数组不算在内。
2.2、归并排序
归并排序的空间复杂度是O(n*lgn)：空间复杂度的递归式为T(n)=2T(n/2)+n，因此根据主定理可得到最终的空间复杂度即为O(n*lgn)。
优化以上空间复杂度有两个方案：
- 优化方案一，建立三个长度为n的数组，一个保存最终结果[S]，一个保存左递归结果[L]，另外一个保存右递归结果[R]，那么在每次递归中，先左递归调用，然后把S中的内容复制到L，再右递归调用，把S的内容复制到R，最后将结果合并到S，进行返回，这样就优化成O(n)，但是代价是计算复杂性提升了，因为需要有复制操作
- 优化方案二，也可以优化成O(1)，但是随之而来的是更大的计算复杂性的提升
2.3、快速排序
快速排序如果按照《算法导论》进行实现，那么可以是稳定的；如果按照从左右两个方向相向而行的方法实现，那么是不稳定的（快速排序有两个方向，左边的i下标一直往右走，当a[i]<=a[center_index]，其中center_index是中枢元素的数组下标，而右边的j下标一直往左走，当a[j]>a[center_index]。如果i和j都走不动了，i<=j， 交换a[i]和a[j]，重复上面的过程，直到i>j）。
