数据结构学习(C++)续——排序【6】内部排序总结

类别:VC语言 点击:0 评论:0 推荐:

基数排序本文后面将会提到,我觉得将其和前面的排序算法放在一起比较有些不伦不类。前面介绍了四类排序方法,每种都有基本型和改进型。对于内部排序,我们最关心的当然是速度,这也是为什么快排受欢迎的原因。考虑到快排的缺陷,有时候我们可能会用堆排或者希尔排序、归并排序。

上面可能是选择排序方法最直接的思路了(我们的选择范围也不算广,就那几个翻过来调过去的,好一点的,综合一下搞一个“杂牌”),出于“赌徒”的思维,我们大多数人可能用快排包打天下——出最坏情况?我没那么倒霉吧?大不了再加一个“三者取中”(或者随机选取)。但是,有时候速度并不是一切,我们还要考虑排序的稳定性。

前面没有涉及稳定性,主要是考虑每提到一种算法都要说一些本来并不是十分重要的“是否稳定”实在是干扰读者思路,并且前面的测试也无法反映稳定性。现在我们放在一起来说。排序的稳定性是指,对于相同的关键字,排序完成后他们的次序是否发生了改变,维持原状是稳定,否则就是不稳定的。实际上就是说,对一个多关键字序列,多次排序结果是否能够累积——多次排序能否最终达到预期的有序。打个比方,首先我们按学号对学生排序得到一个序列(在实际的应用中,初始序列总是这样的,我们根本不需要排序),然后按照成绩排序,对于成绩相同的学生,我们希望学号靠前的排在前边(预期的有序),如果排序是不稳定的,就会破坏前面按照学号排好的序列,从而导致得不到最终的预期序列。注意到是“预期有序”,在排成绩的例子中,如果我们不要求相同成绩的学号有序,排序是否稳定就无关紧要了。

什么排序算法是稳定的呢?首先看一下是什么导致了“不稳定”。注意到前边的四类方法都有稳定的算法(这是现有结论,不要问我是怎么来的,反正是就是是了,^_^),排序的思路应该不是不稳定的因素。排序肯定有记录的移动(或者指针的修改),移动方法有平移(直插排序)、交换(起泡排序)、重排(表插、归并)。仔细观察一下,就会发现,不相邻位置记录的交换是导致不稳定的因素。这样一来,凡是有这个隐患的排序算法都是不稳定的,对于原来稳定的算法,如果采用了这样的交换策略,也会导致不稳定,比如直接选择排序对于链表来说是稳定的,但对于数组来说就是不稳定的,然而,如果采用平移来代替原来的交换,那么对于数组也是稳定(估计没人愿意把本来的交换1次改成平移一堆)。

另外对于本来稳定的算法,当更改关键字判断条件后,比如大于变为大于等于,也会导致不该移动的移动,从而稳定的算法变成不稳定的,但这种低级的失误不在我们讨论范围——蓄意把稳定改不稳定,没带来性能的提升,谁这样做谁有病。

当了解稳定性的本质之后,就可以看透基数排序了。

基数排序

当初听到可以突破O(nlogn)下限的排序方法很惊奇,实际看过之后不过尔尔,我们日常生活中经常在应用,只是我们没有注意到。我们都玩过“十二月”的排阵游戏吧,当我们抽到6的时候就会把他放在6号位置上(第1排第6个位置),如果一切顺利,最后就会得到12叠排,依次是1、2……12,可以看到,排序实现了。再来看看0~999内整数的排序,假设数字互不重复,最为直接的就是,建一个1000大小的数组a[],如果是1,就放到a[1],如果是400,就放到a[400],将数字都放好之后,从a[0]到a[999]重新读一遍,排序就完成了。

很清楚的,这里使用了散列查找技术,而散列表的最佳查找性能是O(1),整体上看,上面的0~999无重复数字的分配的时间复杂度就为O(n)了。当有重复数字的时候,这里使用的处理冲突的办法是链地址法——将所有的重复数字组成一个链表挂在对应的位置。很显然的,这个过程只不过是链表的重排,因此是稳定的(非要写成不稳定的我也没办法)。

在上面的“分配-收集”的基础上,就可以完成基数排序。讨论基数排序是否稳定实际上是件很可笑的事情,因为基数排序能工作的前提就是必须是稳定的——它是多关键字排序的累积结果,如果其中有不稳定的操作,整个结果也就是错的。

对于单关键字,要么可以一字排开的分配,然后收集,时间复杂度为O(n+r)(最后的收集过程O(r));要么嫌附加储存太多,也可以拆成多个关键字,附加储存成指数下降(不是上升^_^),自然的就要多分配收集几次。因为高位的关键字决定序列的最终顺序,所以必须最后做高位的分配收集,基数排序一般来说都是LSD(最低位优先)的。

另外不要一看到用基数排序对整数排序就想到百、十、个位分解,注意到“基数”这个概念,你用多少基数分解都可以,比如1000进1的“1000进制”。例程不给了,因为基数排序的限制条件太苛刻了。

关于外部排序

这个看似很神秘,但只要知道了“归并”的分段有序变整段有序的作用,就明白这样的任务也是能够完成的,剩下的是如何提高效率。

提到磁盘,我们总想到“内存操作时间”远小于“读盘时间”,但现在的技术使得读盘时间已经越来越短了,我自己的感受是对40MB的整数排序不会比从硬盘读40MB内容来得快(在我的机器上内排一千万乱序整数的时间是18s,可能是我算法写的不好)。但提高速度的不二法门就是减少不必要的慢速设备的信息流量,就像Cache于内存,内存于硬盘。所有我们能够想到的提高外排速度的方法,也不外乎减少内存和外存的信息流量。这里边采用的技术就有增加归并路数、增加初始归并段长度,最佳归并树等等。

然而实际上,对于1000个以上的数据,我们从来不会自己去管理,都是借用数据库了事。也就是说,如果不去写数据库,估计也用不到外排;而如果写数据库,外排的知识也不过是九牛一毛。

相对于内排的常用,外排或许不是必须掌握的技术,学习它的目的更应该是为我们提供了一个如何解决“内存不够”的思路,以及如何提高外存性能的思路。

没有见过真实模拟的例程,也就不献丑了。

本文地址:http://com.8s8s.com/it/it1344.htm