第十章 排序

第十章 分数排序定位法

一、分数排序定位法的由来及其定义

由于每个高考分数都对应着相对的排序位置，而相应的排序位置也大体对应着一定的高考分数，只不过不是一一对应的关系而是大体相对应的关系罢了。既然可以利用高考分数来填报高考志愿，那为什么不能利用排序位置的定位作用来填报高考志愿呢？来预测高校的投档(录取)分呢？回答当然是肯定的。这就是分数排序定位法的由来。

二、分数排序定位法的重要性

许多考生和家长的两眼往往只习惯盯在考试及高考的分数上，学校的录取分数线上，其实，这是一个很大的误区。这是因为：

4．从考生排序的位置，可分析被录取的可能性。由于多年的招生，每所院校的排序位置也是大体相对稳定的，当然不排除有波动。比如说北大、清华总是当之无愧的龙头老大，它们的录取分数线总是最高的，排序位置也总是最靠前的。这既可以从每所院校每年的招生录取分中可以看到。也可以从每所院校每年的招生排序位置中可以看到。因此，根据当年的招生情况结合历史的资料，就大体可以知道，你的排序位置是多少，被录取的可能性有多大。如2005年北大、清华在鄂计划招生理工类分别为49名、95名，那么从理论上来说，这144人都有可能被录取；可是从理论上来说，这144人中按现行的录取办法，有可能排序位置是第50名或其以后的若干名考生就可能会被淘汰出局，原因很简单，那就是前49名考生甚至更多的考生第一志愿全都填报了北大。当然在实际中第50名考生会被淘汰出局的可能性微乎其微，同样第144名考生被录取的可能性也不是100%。虽然对于所有院校均按招生计划与排序位置一一对应地实现招生几乎没有可能，但对于北大、清华这两所学校来说，是完全可以做到的，而且办法也比较简单，这是后话，下面再说。

5．考生的排序位置比其高考分数更重要的现实分析。那么到底排序在第144位及其稍后的考生有无必要第一志愿填报北大、清华呢？要回答这个问题就要知道首先应关注的是排序位置，不是高考分数因为排序在第144位及其以前的考生不论考分是多少，被录取的概率非常之大。因此可以说，此时的分数是次要的。排序144位对应的分数大约是647分(647分对应的排序是147位)。

第十章 综合题

00

1. 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的?

00

2. 设待排序的关键字序列为(15, 21, 6, 30, 23, 6′, 20, 17), 试分别写出使用以下排序方法

每趟排序后的结果。并说明做了多少次比较。

00

(1) 直接插入排序 (2) 希尔排序(增量为5,2,1) (3) 起泡排序

00

(4) 快速排序 (5) 直接选择排序 (6) 锦标赛排序

00

(7) 堆排序 (8) 二路归并排序 (9) 基数排序

00

3. 在起泡排序过程中，什么情况下关键字会朝向与排序相反的方向移动，试举例说明。在

快速排序过程中有这种现象吗？

00

4. 快速排序在什么情况下所需关键字的比较次数最多？此时关键字比较次数应为多少？

00

5. 用直接插入排序方法对序列(94,32,40,90,80,46,21,69)进行排序（由小到大），试写出

排序的过程。

00

6. 已知初始序列为(125 ，11， 22， 34， 15， 44， 76， 66， 100， 8 ，14， 20， 2，

5， 1)，写出采用希尔排序算法排序的每一趟的结果（增量为5，3，1）。

00

7. 写出对初始序列(50,72,43,85,75,20,35，45，65，30)进行直接选择排序的过程。

00

8. 若用冒泡排序对关键字序列(18,16,14,12,10,8),进行从小到大的排序，所需进行的关

键字比较次数是多少。

00

9. 给出关键字序列(27，18，21，77，26，45，66，34)，试写出快速排序过程。

00

10. 无序序列为(10，2，13，15，12，14)，用堆排序方法从小到大排序，画出堆排序的初

态、建堆和重建堆的过程。

00

11. 写出对序列(28，16，32，12，60，2，5，72)进行2路归并排序的过程。

00

12. 给出如下关键字序列(321，156，057，046，028，007，331，033，034，063)，试按链

第十章 排序

一、名词解释

1.排序 2.内部排序 3.外部排序 4.堆 5.堆排序

二、填空

1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。

2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。

3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、________、________等四类。

4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价排序的另一个主要标准是执行算法所需要的________。

5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和________插入排序。

6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。

void straightsort(list r);

{for(i=___________;i<=n;i++)

{r[0]=r[i];j=i-1;

while(r[0].key

r[j+1]=_______;

}

}

7.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。

8.以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。

void bulbblesort(int n,list r)

/*flag为特征位，定义为布尔型*/

{for(i=1;i<=________;i++)

{_______________;

for(j=1;j<=_________;j++)

if(r[j+1].key

第10章 排序

一、选择题

1．某内排序方法的稳定性是指( D )。 【南京理工大学 1997 一、10（2分）】

A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录

C．平均时间为0（n log n）的排序方法 D．以上都不对

2．下面给出的四种排序法中( D )排序法是不稳定性排序法。【北京航空航天大学 1999 一、10 （2分）】

A. 插入 B. 冒泡 C. 二路归并 D. 堆积

3．下列排序算法中，其中（D ）是稳定的。 【福州大学 1998 一、3 (2分)】

A. 堆排序，冒泡排序 B. 快速排序，堆排序

C. 直接选择排序，归并排序 D. 归并排序，冒泡排序

4．稳定的排序方法是（ B ） 【北方交通大学 2000 二、3（2分）】

A．直接插入排序和快速排序 B．折半插入排序和起泡排序

C．简单选择排序和四路归并排序 D．树形选择排序和shell排序

5．下列排序方法中，哪一个是稳定的排序方法？（ B ） 【北方交通大学 2001 一、8（2分）】

A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序

6. 快速排序方法在（ D ）情况下最不利于发挥其长处。 【燕山大学 2001 一、3 （2分）】

A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值

C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序

7. 以下序列不是堆的是( D )。【西安电子科技大学 2001应用 一、5 （2分）】

A. (100,85,98,77,80,60,82,40,20,10,66) B. (100,98,85,82,80,77,66,60,40,20,10)