1.引言

　　2005年10月25～26日，包括笔者在内的十多位成员组队参加了武汉原动力的野外拓展（Outward Bound）。在攀岩悬崖之前，教官组织了这样的一个游戏项目：

　　教官将团队里的所有成员分开，然后用布条蒙上大家的眼睛，接着给每人一个3位或4位的数字。他要求成员们蒙着眼睛集合，在不说话也看不到彼此的情况下，在限定的时间内，按所分得数字的大小顺序排成一条线。

　　要成功地完成这个游戏的确有相当的难度，成员们唯一可以借助的分辨彼此大小的手段可能是摸手指、拍肩膀或跺脚等，而要在限定的时间内分别出所有的大小并排成一条线却依赖一个好的排序算法。 最后我们团队失败了，我们这群都有一定数据结构和算法学习背景的所谓IT人败在了这个游戏的面前。最后，教官对我们进行了一番“团队合作精神如此重要”之类的教育云云。

　　本文对排序算法的全面论述将从这个游戏说开去，并用Visual C++ 6.0编写一个示例工程以动画演示这个游戏中的成员以各种算法实现成功排序的过程。排序算法是数据结构学科的经典内容，也是计算机科学中最重要的研究问题之一。由于它的应用广泛和固有的理论上的重要性，2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一。对于排序的研究既有理论上的重要意义，又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。 常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。在演示完各种排序算法的动态过程后，本文将给出面对特定问题时选用合适排序算法的原则。

　　2.演示工程

　　单击此处下载演示工程。

　　以Visual C++编写一个基于对话框的程序，我们假设待排序的队员的总数为10，排序的整个过程为（每个步骤对应一个菜单）：

　　（1）队员分散：模拟教官将队员分散开来的过程

　　　对应的菜单为：IDM_Disperse_Member

　　　菜单标题为：队员分散 （2）分配数字：模拟教官给每个队员一个3位或4位的数字的过程

　　　对应的菜单为：IDM_CREAT_NUMBER

　　　菜单标题为：产生数字

　　（3）集合：所有成员在获得数字后，为进行排序，他们需要先集合

　　　对应的菜单为：IDM_Muster_Member

　　　菜单标题为：队员集合

　　（4）排序：成员们依据摸手指、拍肩膀或跺脚等手段进行由小到大的排序，又依据排序算法分为：

　　　a.冒泡法

　　　　对应的菜单为：IDM_Bubble_Sort

　　　b.交换排序

　　　　对应的菜单为：IDM_Exchange_Sort

　　　c.选择排序

　　　　对应的菜单为：IDM_Selection_Sort

　　　d.插入排序

　　　　对应的菜单为：IDM_INSERT_SORT

　　　e.快速排序

　　　对应的菜单为：IDM_QUICK_SORT

　　　整个对话框的消息映射关系为：

图1 队员分散

图2 分配数字

图3 队员集合

　　上述CSortDlg::OnCreatNumber()及CSortDlg::OnMusterMember()函数中用到的sortObject定义为：

SortObject sortObject[SORT_OBJECT_NUM];

　　即SortObject数组，而SortObject的含义则为待排序的成员，其定义为：

    3.排序

　　3.1冒泡排序

　　冒泡排序的名字来源于其工作方式，在这种排序算法中，较小的数一个一个往水面上“冒”，最终所有数均变成了由小到大排列。在冒泡排序算法中我们要对待排序的对象序列进行若干遍处理，处理的过程是：自底向上检查序列，并比较相邻对象的大小。如果发现两个相邻对象的顺序不对（较小对象在后面），就交换它们的位置。经过一遍处理之后，最小的对象就“冒”到了最前面的位置；经过第二遍处理，次小的对象又“冒”到了次前位置，依此类推。

(编者注：本图为动画，请设置IE浏览器：工具－>internet->高级->多媒体，选择播放网页中的动画，即可观看，后同)

　　对于n个待排序成员，冒泡排序需要进行n(n-1)/2次比较，平均情况下需进行3n(n-1)/4次交换；因为每交换一对不合顺序的元素，需进行三次操作，所以最坏情况下，交换次数是比较次数的三倍，即3n(n-1)/2 。因此，冒泡法是效率最差的排序方法，一般只适合于数组较小的情况。

　　因此，有学者提出了“拉锯法”、“双边冒泡法”等改进措施。“拉锯法”不再是总按同一方向读数组元素，而是这一遍从下到上把最小的送到最前面，下一遍从上到下把最大的元素送到最后面；“双边冒泡法”则每次除了冒出最小元素外，还“下沉”最大元素。

　  3.2交换排序

　　交换排序的基本思想是对待排序的对象序列进行n-1遍处理，第i遍处理的过程为：将对象i~对象n-1与对象i-1进行比较，若其较小，则与i-1对象交换位置；经过i遍处理之后，前i个对象就是顺序排列的了。

　　交换排序的时间复杂度为O(n2)，其比较次数与下文要介绍的选择排序相同，但是其交换次数比选择排序大，因此不推荐使用这种排序算法。

    3.3选择排序

　　由前文可知，交换排序的特点是每次用当前的对象一一与其后对象比较并交换。选择排序与交换排序类似，但是它并不是用当前对象与其后对象一一比较，而是直接以当前对象以后的最小对象与当前对象比较并交换，因而可以提高算法的时间性能。

　　选择排序法总的比较次数是n(n-1)/2次，但其交换次数有所减少。最坏情况下的交换次数接近于比较次数，为〔n2/ 4+3(n-1)〕；平均情况下交换次数为〔n*ln(n+u)〕，其中u 是尤拉常数，约为0. 577216。

   3.4插入排序

　　插入排序的基本思想是，经过i-1遍处理后，对象0～i-1己排好序，第i遍处理的过程是将对象i插入对象0～i-1之间的适当位置，使得对象0～i又是排好序的序列。

　　插入排序法的比较次数和交换次数与被排序数组的初始顺序情况有关：在最好、最坏、平均三种情况下，总的比较次数分别是(n-1)、(n2+n-2)/4、(n2+n)/2-1，总的交换次数是总比较次数减去n-1，它在最佳情况下为0，在最差及平均情况下为O(n2)。由此看出，在最坏情况下，插入排序法的交换次数与冒泡法、选择法一样糟糕，其执行时间和n2成正比。

　　D. L. Shell 发明了希尔（Shell）排序算法，该算法的基本思路是插入排序。希尔排序又称为缩小增量法，它的做法是先取定一个正整数d1 < n，把全部记录分成d1 个组，所有距离为d1倍数的记录放在一个组中，在个组内进行插入排序；然后取d2 < d1 ，重复上述分组和排序工作，直至取di = 1，即所有记录放在一个组中排序为止。大量的实验证明：当n在某个特定范围内时，希尔排序的比较次数和交换次数均为约n1.3。

    3.5快速排序

　　Tony Hoare在1962年首次提出了快速排序算法。对快速排序方法的研究表明，至今快速排序算法仍然是流传久远的最实用的排序算法。只在输入数据项有更详细的信息时，其它排序算法才可能胜过快速排序算法。快速排序算法是利用分治技术的典型例子，随机分治策略是设计组合优化与计算几何一类问题有效算法的基础。分治策略分为三步：

　　（1）将问题分成若干大小基本相等的子问题；

　　（2）独立地解决这些子问题；

　　（3）将子问题归并成原问题的解。

　　快速排序的基本思路是：首先我们选择一个中间值middle（程序中我们可使用数组中间值），把比中间值小的放在其左边，比中间值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架（从各类数据结构教材中可得）：

　　对于n个成员，快速排序法的比较次数大约为n*logn 次，交换次数大约为(n*logn)/6次。如果n为100，冒泡法需要进行4950 次比较，而快速排序法仅需要200 次，快速排序法的效率的确很高。快速排序法的性能与中间值的选定关系密切，如果每一次选择的中间值都是最大值（或最小值），该算法的速度就会大大下降。快速排序算法最坏情况下的时间复杂度为O(n2)，而平均时间复杂度为O(n*logn)。

　　4.总结

　　冒泡排序、选择排序和插入排序等的时间复杂性是O(n2)，快速排序、堆排序和归并排序等高级排序算法的时间复杂度为O(n*logn)，因此后者的排序效率较高。但这并不意味着总是要使用高级排序算法，下面给出各种排序算法选用的一般原则：

　　（1）当数据量不大时选插入或选择排序，不要用冒泡排序；

　　事实上，冒泡排序虽然简单，但的确是最不宜采用的排序算法，因为其性能表现是最差的。

　　（2）当数据量大而又注重时间复杂度时选快速或堆排序等；

　　堆排序的设计思路是：定义堆为一个键值序列{k1 ,k2 ,…,kn}，它具有如下特性：ki < = k2i，ki < = k2i + 1 (i = 1 ,2 ,…, [ n/ 2 ]) 。对一组待排序的键值，首先把它们按堆的定义排列成一个序列(称为初建堆)，这就找到了最小键值。然后将最小的键值取出，用剩下的键值再重新建堆，便得到次小键值。如此反复进行，直到把全部键值排好序为止。

　　由于快速排序和堆排序算法较复杂，因此在待排序的数据量较小时反而比插入和选择排序慢；

　　（3）当要在已排序数据上增加新数据时选插入排序。

　　当原有数据本身就有序时，插入排序的性能非常好。在已排序数据上增加新数据时，时间复杂性仅为O(n)。

评论