Question

1.比较排序

比较排序是指通过输入元素间的比较来确定各元素次序的排序算法。

任何比较排序在最坏情况下都要用 O(nlgn) 次比较来进行排序

合并排序和堆排序是渐近最优的

2.非比较排序

非比较排序指使用一些非比较的操作来确定排序顺序的排序算法

对于非比较排序，下界 O(nlgn) 不适用

计数排序是稳定排序，若 n 个数据的取值范围是[0..k]，则运行时间为 O(n+k)，运行空间是 O(n+k)

基数排序也是稳定排序，需要另一个稳定排序作为基础，若 n 个 d 位数，每一位有 k 种取值可能，所用的稳定排序运行时间为 O(n+k)，则基数排序的时间是 O(d(n+k))

桶排序也是稳定排序，当输入数据符合均匀分布时，桶排序可以以线性时间运行。所设所有元素均匀分布在区间[0,1) 上，把区间[0,1) 划分成 n 个相同大小的子区间（桶），对各个桶中的数进行排序，把依次把各桶中的元素列出来。