1、最基础排序算法


时间复杂度
稳定性
冒泡排序 O(n^2)
稳定选择排序
O(n^2)不稳定
插入排序 O(n^2)稳定


2、5个中间改良排序算法


时间复杂度稳定性归并排序
O(nlogn)
稳定
希尔排序
平均O(nlogn)，最坏O(n^2)
不稳定
堆排序
O(nlogn)
不稳定
快速排序
平均O(nlogn)，最坏O(n^2)不稳定
随机化快排
O(nlogn)不稳定

(1)、归并、堆、快排是渐进性的最优排序算法(在大规模的数据下尤为体现)；

(2)、解决快排最坏情况的方案：随机化快排，随机选择主元；(与输入无关，就是随机器的概率问题了)；

(3)、以上都是比较模型的排序算法，最快时间复杂度为：O(nlogn)；

(4)、归并排序用并行算法的话，时间复杂度：O(n/logn)；


3、3个局限性的排序算法


时间复杂度稳定性桶排序
O(n)
稳定计数排序
O(n)稳定基数排序
O(n)稳定

(1)、这3个排序算法的时间复杂度都为：O(n)，都是稳定性的排序算法；

(2)、都是以空间换时间为代价的算法，处理数据的规模在较小范围内；

(3)、无重复数字出现：建议用桶排；

(4)、有重复数字出现，用计数/基数排序；基数排序是对计数排序的优化，在辅助空间上的优化，基数排序所需辅助空间为：10个该元素空间，计数排序所需辅助空间为：最大数字+1个空间；


4、空间复杂度

O(n)：桶排，计数，基数

O(logn)：归并，快排，递归堆排

O(1)：非递归堆排，希尔