由排序算法引出的数据结构
2011年09月29日


     本文较为深入地研究了各类基本的排序算法,并由此引伸到对于数据结构的认识

 

      怎样选择算法?哪种排序算法最好?要回答这些问题首先要建立在数据特征和对数据的操作要求上,根据不同的数据特征和操作要求选择合适的数据存储结构

       数据存储结构分类如下:

(1)顺序存储(2)链表结构(3)索引(4)散列表

       对于顺序表和链表,实际应用中又分栈、队列、树、图等。


再回头来看排序算法:

       直插、希尔、直选、堆、冒泡、快排、归并、基数排序。为O(n2)的是直插、直选和冒泡。直选的效率最低,其次是冒泡,直插比较好而且稳定,但是若用在顺序表上会大量挪动记录,插入和删除操作是顺序表上无法克服的弱点。直选和冒泡相比,直选比较的次数较多但是最多交换n-2次,而冒泡交换记录的次数稍微多一点,但是冒泡可改进:采用提前终止位置和交替扫描方向能使冒泡适应复杂多样的数据。但是效率的提升也是有限的,例如我用2万个整数去测试时,基本的冒泡用了2.428秒,设置了flag的用了2.279秒,提前终止位置的用了2.153秒,双向扫描用了1.652秒,相对于快排的零点几秒和堆排序的零点零零几秒,完全不在一个数量级。

       快排速度最快但是不稳定而且只适合顺序表,它用两个指针i、j左右移动,交换较小的元素到基准的前端,交换量取决于数据的初始有序情况,但我估计它的平均交换量小于改进的冒泡排序。快排有一个缺点就是数据越有序,那么它的效率越差,这是因为每次都是选首元素为基准的缘故。现实中有排过序的文件稍微打乱了一下顺序,要再次排序的情况,这时是基本有序,快排就比较吃力。这是就应该改进一下快排算法,取中间元素作为基准,但是又为了避免运气霉,抽到的中间那个元素偏偏是极大或者极小的情况,所以用首、中、尾三者取中作为基准的办法。但是快速排序除了不稳定和只能对顺序表进行排序外,还有一个很大的缺点就是空间开销大,因为它是用递归算法写的,需要在内存中开辟递归栈空间,最坏情况下空间开销为O(n)。当我测试快排的时候遇到了递归栈空间不足的情况,VC默认给栈空间开辟的内存最大为2~8M,我用最原始的快排算法,元素个数约为20W个时递归栈空间就不足了,用首、中、尾三者取中的改进的快排,内存开销更大,大约只能排3万个元素。而且排序的速度上快排并不是最快,要比堆排序慢很多。快速排序的最坏时间复杂度为O(n2),平均时间复杂度和最坏时间复杂度均为nlg(n)。

       希尔排序其实就是分段的插入排序,定义一个初始增量d,然后依次减小d使得每次直插比较的元素增多,但是d变得越小,也就意味着元素变得越来越有序,就有利于直插排序。其交换量应该还是蛮大的,我估计与改进冒泡的交换量相当或者稍好。

       堆排序是一种树形(完全二叉树)的选择排序,效果非常好,当数据量较大时(比如1000个)比快速排序要快很多,但是也不稳定。由于建初始堆所需要的比较次数较多,所以堆排序不适合记录数较少的情况。堆排序的“最坏时间复杂度”为nlg(n)(由此可见它比快排要快),而且堆排序的空间开销要小于快排。

       总之,若顺序存储,假设存的是长度小于16的字符串,个数为1000或者10W,则用堆排序或者快排,因为如果用希尔排序或者改进的冒泡算法,则要多次挪动或交换数据,拷贝字符串(strcpy)也是要挺大的开销吧?但是如果比较的是数量少于300个,那就用直选吧,因为拷贝量大,不宜用希尔排序和冒泡排序以及快速排序,而且数据量确实很小,用快排好像效率也不算高,但如果比较的不是长度为16的字符串而是简单的4位整数,那显然用希尔排序,移动的数据量不大而且算法又稳定,但如果是4位的小数呢,用基数排序?还是快排、希尔、堆?没试过还真不知道!因为我不知道系统完成2>4?与2.125>2.112?的效率之间的差别,也不知道交换一对整数的值和交换一对实数的值时系统开销的差别,倘若整数之间的比较比实数之间的比较要麻烦很多,而且整数之间的赋值要比实数之间的赋值速度慢、开销大,则也许用基数排序才是王道!否则,类似于上面的16位字符串,用堆排序或者快排!

       对于链表结构,链表本身就有很多学问:是动态链表还是静态链表?是单链表还是双链表?是栈还是队列?是二叉树还是红黑树还是其他神马树甚至图?

       于是乎,在此我们只以完全二叉树为例,则用堆排序较好,也可以用插入排序。如果是双链表则用插入排序吧,如果是其他链表结构,不外乎也是与插入排序和堆排序类似的方法,但是会针对某一种结构优化算法,例如“败者树”“置换-选择排序”神马的!

       综上可知,最没用的是冒泡排序,直选有一点点用处(因为它记录移动次数少),直插(希尔)、快排和堆排序最有用了,特别是堆排序,速度最给力了,其思想适合用在树形结构上,分配排序(基数排序)也许有用,虽然打着O(n)的幌子,但是据我分析,其效率一般不及快排,除非你n上几十亿并且关键字的位数d、箱子的个数rd都很小(否则d*rd会大于lg(n),lg(n)(2为底的对数)其实是一个很小的数,当n=1000W时,lg(n)才约为23)。而归并排序只是一种多文件归并的方法,实际上还是以内部排序(例如直插)为主,通常(直插+归并)搞定要求排序稳定的大链表文件。

 

       最后分析一下数据结构,首先要熟练掌握(甚至精通)的是(单/双链表、二叉树,包括在它上面的一些基本操作,必须熟练)。对于排序算法,要熟练掌握(甚至精通)的是(直插、希尔,直选、堆,快排)。补充一点:实际应用中,散列表查找算法是很有用,其O(n)的时间复杂度非常高效,例如输入法,拼音或者五笔,对于查找算法的要求非常苛刻,二叉查找和树查找算法根本达不到要求