编程点将台(38)
软件世界
编程点将台：一个编程爱好者学习、动手、交流的天地。注重培养编程思想，强调多种解法。
多样的参与方式：
在每期的请战帖里向各路编程好手发出邀请，来信请寄 liz@cpcw.com(请在来信中写明通讯地址和联系方式，不限开发工具和语言)，为照顾拿到报纸较晚的读者，我们会在隔一周后才公布结果。
1.是编程好手？那就去武将堂耍耍刀枪！那里为大家提供完整程序的学习交流。
2.是理论英雄？那就来文臣殿会会朋友！这里和大家探讨算法和数据结构。
3.我眼界开阔、能力过人？那你就是阿志要找的军师，直接将你好的编程问题连同解法发给阿志(liz@cpcw.com)，说不定下期出题的就是你！
直接的奖励方式：
将来信中的优秀读者大名公布在点将录中，上榜的文臣、武将的成果还将放在网上供大家学习交流，另外还将获得50元现金奖励。
请战帖
国庆将到，不少新人将要踏入婚姻的殿堂。阿志坐在就要成婚的皇甫和阿飙之间，也感受到了不少喜悦的氛围，这期就先为大家出一个有关结婚的题目。
三对新人举行婚礼，假设新郞分别为A、B、C，新娘分别为X、Y、Z。在来宾中有人不知道他们是谁和谁结婚，于是就询问了六位新人中的三位，听到的回答是这样的：A说他将和X结婚；X说她的未婚夫是C；C说他将和Z结婚。这人听后知道他们全在开玩笑，都说的是假话。请编程找出三对新人分别是谁和谁结婚。
点将录
第36期请战帖题目回顾：100名运动员同场竞技，十个评委为每个运动员打分。打分规则是去掉一个最高分，再去掉一个最低分，剩下的取平均值就为该名选手得分。请将100名选手按此规矩打分后的成绩排序。
很高兴到截稿为止，阿志不但收到了大家关于运动员排序的大量来稿，在其中还欣喜地看到有些读者对一些主要的排序方法做了详尽的分析比较和关于适用场合的总结。在对各个排序方法效率的阐述上，都采用了针对特定问题编程比较运行效率的方法，使得结果客观而具有说服力，下面我们来看看几位解答相对突出的读者。
来自陕西的朱勇。做了一个详尽的排序比较报告，严格按照软件工程的要求和顺序对以下7种常用的内部排序算法进行了实测比较：冒泡排序、插入排序、折半插入排序、简单排序、快速排序、希尔排序、堆排序。有相应的文档说明和测试程序，推荐大家下载看看。
来自江苏的徐小兵。在对运动员的排序上，他使用了冒泡法、选择法、快速法等几种排序方法来解决问题，并对几种排序方法做了详细的分析。
来自山东的张锐。
前面两位读者的解答都很详尽，但限于报纸篇幅，只能将他们的作品放在网上供大家下载学习了。(下载地址：http://www.cpcw.com/38/rec.rar)山东的张锐则对各个排序方法做了简单的分析，下面我截选了部分供大家参考交流：
记录多了当然要排序，而对于排序，有太多排序的方法。而常用的不外乎简单排序、希尔排序、快速排序等方法。每种方法有什么特点呢？他们适合哪些问题的排序呢？下面就简单讲讲：
主要排序方法介绍
简单排序：简单排序中又有直接插入排序和冒泡排序，还有简单选择排序等方法。
(1)直接插入排序：这是一种简单的排序方法，具体做法就是：从待排记录中取一个放入一个队列中，如果该队列已经有元素，则从第一个元素起进行比较，找到当前元素应该插入的位置并插入该元素。对所有的待排记录重复上述过程直到所有元素全部插入到队列中去。
(2)冒泡排序：具体做法是：把记录不分大小先排在一起(假设共n个)，首先将第一个记录与第二个记录比较。若第一个记录大于第二个记录，则交换两个记录。然后比较第二个记录与第三个记录，重复下去，直到倒数第二个记录与最后一个记录(第n-1个记录与第n个记录)进行过比较为止。
这样就经过了第一趟冒泡排序。经过这样一次排序后，所有记录中最大的记录就被交换到第n个位置。然后进行第二次冒泡排序，对前n-1个记录进行排序。依次进行第3，4……n-1次冒泡排序，当进行完第n-1次(最坏情况)冒泡排序时，所有记录已有序排列(当无元素交换时，所有元素已有序排列)。
……
各种排序适用场合
迄今为止，已有的排序方法远远不止上述几种，选取排序方法需考虑以下因素：
a.待排序的记录个数n
b.记录本身的大小
c.堆排序稳定性的要求
d.语言工具的条件，辅助空间的大小
依据这些因素，可以有以下几点结论：
1.从平均性能而言快速排序最佳，所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较，在n较大时，归并排序比堆排序所需时间少，但是，它所需的辅助存储量最多。
2.除希尔排序外，所有简单排序中直接插入排序最为简单，当序列中的记录基本有序时，它是最佳选择。因此，常把它和其他排序方法(诸如：快速排序，归并排序)结合使用。
3.从方法的稳定性来说，快速排序，堆排序，和希尔排序等时间性能好的排序方法都是不稳定的。而简单排序法是稳定的。一般说来：排序过程中的比较是在相邻两个记录间进行的排序方法是稳定的。
小结
1.记录数目n较小时，可采用插入排序和选择排序。
2.若待排记录基本有序，则宜采用直接插入排序或冒泡排序。
3.当n较大时，则应采用快速排序，堆排序或归并排序。快速排序是目前内部排序方法中被认为最好的方法。当待排记录为随机分布时，快速排序的平均运行时间最短。快速排序和堆排序都不是稳定的排序方法，若要求稳定可以选择归并排序。
基于所给题目有100个记录，个数较多，且相邻选手的数据基本无序，可以选择快速排序。
本期获奖读者和更多的读者的作品可以在http://www.cpcw.com/38/rec.rar下载。三位读者各获得50元现金奖励。