线性时间排序

算法设计与分析2019年9月4日讲授内容：动态规划I教师：胡学钢、吴共庆至今为止，我们见过的排序都是比较排序:仅仅使用比较来比较各项的相对顺序.•比如：插入排序,合并排序,快速排序,堆排序.我们见过的比较排序的最好的最坏运行时间是O(nlgn).O(nlgn)是不是我们能做到的极限?决策树可以帮助我们回答这个问题.排序可以做到多快？9/4/2019算法设计与分析-线性时间排序2排序〈a1,a2,…,an〉每个内部节点标识为i:ji,j∈{1,2,…,n}.•左子树表示当ai≤aj时的比较序列.•右子树表示当ai≥aj时的比较序列.9/4/2019算法设计与分析-线性时间排序3决策树举例排序〈a1,a2,a3〉=〈9,4,6〉:每个内部节点标识为i:j,i,j∈{1,2,…,n}.•左子树表示当ai≤aj时的比较序列.•右子树表示当ai≥aj时的比较序列.9/4/2019算法设计与分析-线性时间排序4决策树举例每个内部节点标识为i:j,i,j∈{1,2,…,n}.•左子树表示当ai≤aj时的比较序列.•右子树表示当ai≥aj时的比较序列.排序〈a1,a2,a3〉=〈9,4,6〉:9/4/2019算法设计与分析-线性时间排序5决策树举例每个内部节点标识为i:j,i,j∈{1,2,…,n}.•左子树表示当ai≤aj时的比较序列.•右子树表示当ai≥aj时的比较序列.排序〈a1,a2,a3〉=〈9,4,6〉:9/4/2019算法设计与分析-线性时间排序6决策树举例每个内部节点标识为i:j,i,j∈{1,2,…,n}.•左子树表示当ai≤aj时的比较序列.•右子树表示当ai≥aj时的比较序列.排序〈a1,a2,a3〉=〈9,4,6〉:9/4/2019算法设计与分析-线性时间排序7决策树举例决策树可以模拟任何的比较排序的执行过程:•每个输入大小为n的序列都可以用这棵树表示.•将算法视为每次两个项相比后就分叉.•树包含了所有可能比较的指令路径.•算法的运行时间=路径的长度.•最坏运行时间=树的高度.9/4/2019算法设计与分析-线性时间排序8决策树模型定理.对n个项排序的任何决策树的高度是Ω(nlgn).证明.树肯定包含≥n!个叶子,因为有n!种可能的排列.高度h的二叉树有≤2h个叶子.因此,n!≤2h.(lg单调递增)(Stirling’s公式)9/4/2019算法设计与分析-线性时间排序9决策树排序的下界推论.在最差情况下，任何一种比较排序至少需要O(nlogn)比较操作。这是比较操作所获的信息有限所导致的，或者说是全序集的模糊代数结构所导致的。从这个意义上讲，堆排序和合并排序是渐进最佳的比较排序算法.9/4/2019算法设计与分析-线性时间排序10比较排序的下界计数排序:各项之间不进行比较.•输入:A[1..n],A[j]∈{1,2,…,k}.•输出:B[1..n],有序.•辅助存储:C[1..k].9/4/2019算法设计与分析-线性时间排序11线性时间排序fori←1tokdoC[i]←0forj←1tondoC[A[j]]←C[A[j]]+1⊳C[i]=|{key=i}|fori←2tokdoC[i]←C[i]+C[i–1]⊳C[i]=|{key≤i}|forj←ndownto1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–19/4/2019算法设计与分析-线性时间排序12计数排序9/4/2019算法设计与分析-线性时间排序13计数排序举例fori←1tokdoC[i]←09/4/2019算法设计与分析-线性时间排序14循环1forj←1tondoC[A[j]]←C[A[j]]+1⊳C[i]=|{key=i}|9/4/2019算法设计与分析-线性时间排序15循环2forj←1tondoC[A[j]]←C[A[j]]+1⊳C[i]=|{key=i}|9/4/2019算法设计与分析-线性时间排序16循环2forj←1tondoC[A[j]]←C[A[j]]+1⊳C[i]=|{key=i}|9/4/2019算法设计与分析-线性时间排序17循环2forj←1tondoC[A[j]]←C[A[j]]+1⊳C[i]=|{key=i}|9/4/2019算法设计与分析-线性时间排序18循环2forj←1tondoC[A[j]]←C[A[j]]+1⊳C[i]=|{key=i}|9/4/2019算法设计与分析-线性时间排序19循环2fori←2tokdoC[i]←C[i]+C[i–1]⊳C[i]=|{key≤i}|9/4/2019算法设计与分析-线性时间排序20循环3fori←2tokdoC[i]←C[i]+C[i–1]⊳C[i]=|{key≤i}|9/4/2019算法设计与分析-线性时间排序21循环3fori←2tokdoC[i]←C[i]+C[i–1]⊳C[i]=|{key≤i}|9/4/2019算法设计与分析-线性时间排序22循环3forj←ndownto1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–19/4/2019算法设计与分析-线性时间排序23循环4forj←ndownto1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–19/4/2019算法设计与分析-线性时间排序24循环4forj←ndownto1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–19/4/2019算法设计与分析-线性时间排序25循环4forj←ndownto1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–19/4/2019算法设计与分析-线性时间排序26循环4forj←ndownto1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–19/4/2019算法设计与分析-线性时间排序27循环4forforforfortototodowntododododo9/4/2019算法设计与分析-线性时间排序L5.28分析如果k=O(n),那么计数排序用的时间为(n).•但是,排序的时间是Ω(nlgn)!•问题出在什么地方?答案:•比较排序的时间是Ω(nlgn).•计数排序不是比较排序.•实际上,各项之间根本没有比较!9/4/2019算法设计与分析-线性时间排序29运行时间计数排序是一种稳定排序:它会保持相等的项的相对顺序.练习:哪种其他的排序有这种特征?9/4/2019算法设计与分析-线性时间排序30稳定排序•发源:HermanHollerith为1890年美国人口普查设计的卡排序机(参考附录)•一位一位的排序.•Hollerith最初(不好)的想法:从最高位开始排序.•好的想法:使用辅助的稳定排序方法从最低位开始排序.9/4/2019算法设计与分析-线性时间排序31基数排序9/4/2019算法设计与分析-线性时间排序32基数排序过程数位推导•假设数字已经按照其低阶t–1位排序.•按照t位排序9/4/2019算法设计与分析-线性时间排序33基数排序的正确性数位推导•假设数字已经按照其低阶t–1位排序.•按照t位排序两个在位t不同的数被正确排序.9/4/2019算法设计与分析-线性时间排序34基数排序的正确性数位推导•假设数字已经按照其低阶t–1位排序.•按照t位排序两个在位t不同的数被正确排序.两个t位相同的数保持与输入相同的次序⇒正确的顺序.9/4/2019算法设计与分析-线性时间排序35基数排序的正确性•假设使用计数排序作为辅助的稳定排序方法。•对n个b比特字进行排序。•每个字可以看成有b/r个以2r为基的数.例子:32-位字r=8⇒b/r=4遍基于28位的计数排序;或者r=16⇒b/r=2遍基于216位的计数排序.我们要作多少遍?9/4/2019算法设计与分析-线性时间排序36基数排序分析回忆:计数排序使用(n+k)的时间对n个范围在0到k–1的数进行排序。如果每个b-位字分成r-比特份,每遍计数排序花费(n+2r).因为有b/r遍,我们有选择r使得T(n,b)最小:•增加r意味着更少的遍数,但是因为r≫lgn,时间成指数增长。9/4/2019算法设计与分析-线性时间排序37基数排序分析（续）通过求导并将方程置0求得最小值T(n,b)。.或者,观察我们不要2r≫n,在满足这个限制的条件下选择尽可能大的r对对称性没有影响。选择r=lgn意味着T(n,b)=(bn/lgn).•对于界于在0到nd–1的数,我们有b=dlgn⇒基数排序运行时间为(dn).9/4/2019算法设计与分析-线性时间排序38选择r实际上,在大量输入的情况下，基排序速度很快，算法也很容易编码和维护.例子(32-比特数):•对≥2000个数排序适合最多走3遍.•合并排序和快速排序至少要lg2000=11遍.缺点:与快速排序不同,基排序基本上没有引用局部性,这样在现代的处理器上一个调优的快速排序，利用内存的分层体系，可以在性能上超过基数排序。9/4/2019算法设计与分析-线性时间排序39结论•HermanHollerith(1860-1929)•穿孔卡•Hollerith的制表系统•排序工人的操作•基数排序起源•“现代的”IBM卡片•关于穿孔卡技术的网络资源9/4/2019算法设计与分析-线性时间排序40附录:穿孔技术•在1880年美国人口普查花费了近10年的时间处理.•在MIT担任讲师期间,Hollerith发明了穿孔卡技术的原型.•他的机器,包括一个“卡排序员”,使得1890的统计结果在6个周的时间内就处理完了。•他在1911年创建了制表机器公司，这个公司在1924年和其他公司合并后组成了国际商用机器公司(IBM).9/4/2019算法设计与分析-线性时间排序41HermanHollerith(1860-1929)•穿孔卡=数据记录.•洞=值.•算法=机器+操作员.1900美国人口普查使用的穿孔卡的复制品.[Howells2000]9/4/2019算法设计与分析-线性时间排序42穿孔卡Hollerith’s制表系统图片请参考[Howells2000].•穿孔•手压阅读器•转盘计数器•排序盒图片请参考[Howells2000].图片请参考[Howells2000].9/4/2019算法设计与分析-线性时间排序43•操作员插入一个卡片。•按住穿过穿孔卡的孔的键，使得电流接触卡下面的水银杯.•每当一个数位被穿孔后,对应排序盒的盖子升起。•操作员将卡片放入盒子并且合上盖子.•当所有的卡片处理完毕后,前端的面板打开,卡片已经安装顺序排放,完成了一遍稳定排序。9/4/2019算法设计与分析-线性时间排序44排序员的操作Hollerith在1889年的最初专利展示了最高位优先的基数排序:“Themostcomplicatedcombinationscanreadilybecountedwithcomparativelyfewcountersorrelaysbyfirstassortingthecardsaccordingtothefirstitemsenteringintothecombinations,thenreassortingeachgroupaccordingtotheseconditementeringintothecombination,andsoon,andfinallycountingonafewcountersthelastitemofthecombinationforeachgroupofcards.”最低位优先的基数排序好像是由一位机器操作员发明的。9/4/2019算法设计与分析-线性时间排序45基数排序的起源•每列一个字符.请看列了吧!9/4/2019算法设计与分析-线性时间排序46“现代的”IBM卡•DougJones的穿孔卡索引•HermanHollerith传记•1890年美国人口普查U.S.Census•IBM的早期历史•Hollerith的发明的图片•Ho