排序算法--基于比较vs线性排序
since 2012-15-15
- 基于比较的排序
这类排序包括插入，归并，堆，快速的等排序，共同点是都需要对数据进行比较，因此，时间复杂度不能突破
O(NlogN)，可以通过“二叉决策树模型”简单分析：
- N个元素进行排序，最多有N!种排列方式
- 决策树的根节点表示初始状态，可以认为有N!中不同可能方式，每个叶子节点是一种排序结果，所以最多有N!个叶子；
- 非叶子节点是中间的一次比较；从根节点到叶子节点的每条路经代表一次排序过程；
- 决策树的高度就对应了一次排序的比较次数（最差情况下）；
- 比较排序算法就可归结到二叉决策数深度问题；
- 假设决策树高度为h，叶子节点个数最多为
2^h,要求2^h>=N!,所以h>=log(N!),根据Stirling公式，log(N!)~O(Nlog(N))，所以，h>=O(Nlog(N))
- 严重推荐 刘未鹏的一篇博文
- 非基于比较的排序
对输入数据有额外限制之后，可以使用一些时间复杂度更小的算法，如计数排序，桶排序，基数排序。
- 计数排序(Counting Sort)
- 要求输入必须是在[0,n]之间的整数序列
- 建立一个数组c=[0,n]，初始化为0
- 遍历输入序列，用c对出现的值进行计数
- 桶排序(Bucket Sort)
- 额外的空间换取时间，可以看成对计数排序的改进和增强
- 同样要求输入是上下界是可知的
- 桶排序先按照输入的上下边界分成M个区间（桶），之后将输入放到对应的桶中，之后对每个桶进行排序（任意排序算法），之后搜集所有的桶内数据。
- 时间复杂度是：O(n)+O(M)*O(N/M * log(N/M))=O(N+Nlog(N)-Nlog(M))
- 可以看出，M越大，时间复杂度趋近O(N)，但是空间复杂度变大（？）
- 桶中的元素顺序存放则保证排序是稳定的
- 桶排序基于一个假设：输入的数据由随机过程构成，否则在最坏情况下都分配到一个桶子里面，如果又不满足计数排序的假设要求，那么只能使用基于比较的排序算法进行排序，运行时间就退化到Ω(nlogn)。
- 基数排序(Radix sort)
- 基数排序是在桶排序基础上的再次拓展，可以对多关键字进行排序
- 假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b的次要关键字的排序。
- 先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序,最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。
- 如果从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。