排序

排序分类:

1. 按照待排记录是否全部被放置到内存中，可以分为内排序与外排序；

2. 按照是否需要辅助空间，可以分为原址排序与非原址排序

3. 按照两个相等的数排序后相对位置是否发生变化，可以分为稳定排序和不稳定排序；

4. 按照是否有比较的排序，可以分为基于比较的排序与非基于比较的排序。

基于比较的排序:

• 交换排序：冒泡排序，快速排序
• 选择排序：简单选择排序
• 插入排序：直接插入排序，Shell排序
• 归并排序

上述最优的平均时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

非基于比较的排序：

• 计数排序
• 桶排序

最优平均时间复杂度为O(n)，但应用场景有所限制。

相关参考：知乎链接