转用VISUAL C 实现排序算法大全.pdf

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 整个对话框的消息映射关系为： BEGIN_MESSAGE_MAP (CSortDlg, Cdialog ) //{{AFX_MSG_MAP (CSortDlg ) ON_WM_SYSCOMMAND() ON_WM_PAINT() ON_WM_QUERYDRAGICON() ON_COMMAND ( IDM_Disperse_Member, OnDisperseMember ) ON_COMMAND ( IDM_CREAT_NUMBER, OnCreatNumber ) ON_COMMAND ( IDM_Muster_Member, OnMusterMember ) ON_COMMAND ( IDM_Bubble_Sort, OnBubbleSort ) ON_COMMAND ( IDM_Exchange_Sort, OnExchangeSort ) ON_COMMAND ( IDM_Selection_Sort, OnSelectionSort ) ON_COMMAND ( IDM_INSERT_SORT, OnInsertSort ) ON_COMMAND ( IDM_QUICK_SORT, OnQuickSort ) //}}AFX_MSG_MAP END_MESSAGE_MAP() “队员分散”实现的功