算法导论学习笔记——第8章 线性时间排序
浏览数：29 /
时间：2015年06月08日
任意一种比较排序算法，在最坏情况下的运行时间下限是Ω(nlgn)
计数排序
假设n个输入元素中的每一个都是介于0到k之间的整数，k为某个整数，当k=O(n)时，计数排序的运行时间为Θ(n)
1 //输入数组A[1..n]，存放排序结果数组B[1..n]，临时存储区C[0..k] 2 COUNTING-SORT(A,B,k) 3 for i←0 to k 4 do C[i]←0 5 for j←1 to length[A] 6 do C[A[j]]←C[A[j]]+1 7 for i←1 to k 8 do C[i]←C[i]+C[i-1] 9 for j←length[A] downto 1 10 do B[C[A[j]]]←A[j] 11 C[A[j]]←C[A[j]]-1
基数排序
假设长度为n的数组A中，每个元素都有d位数字，其中第1位是最低位，第d位是最高位
1 RADIX-SORT(A,d) 2 for i←1 to d 3 do use a stable sort to sort array A on digit i
桶排序
假设输入由一个随机过程产生，该过程将元素均匀的分布在区间[0,1)上
1 BUCKET-SORT(A) 2 n←length[A] 3 for i←1 to n 4 do insert A[i] into list B[floor(nA[i])] 5 for i←0 to n-1 6 do sort list B[i] with insertion sort 7 concatenate the lists B[0],B[1]...B[n-1] together in order
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
