一、填充题
1、按排序操作中所涉及的存储器的不同，可以把排序分成和两大类。
内部排序外部排序
2、主关键字是可以地标识一个数据元素的关键字。
唯一
3、希尔排序是属于插入排序的一种类型，它又被称为排序。
缩小增量
4、次关键字是用以标识数据元素的关键字。
多个
5、按关键字与排序结果的关系，可以把排序方法分成和两类。
稳定排序非稳定排序
6、在直接插入排序、希尔排序、直接选择排序、堆排序、快速排序和基数排序中，需要内存量最大的是。
基数排序
7、在堆排序和快速排序中，如果数据元素的原始序列接近正序或反序，则选用最好，如果数据元素的原始序列无序，则最好选用。
堆排序快速排序
8、对于由n个数据元素构成的序列实施冒泡排序时，最少的比较次数是。冒泡排序的结束条件是。
n-1 刚做完的一趟排序没有交换元素
9、对于由n个数据元素构成的序列实施冒泡排序时，数据元素的最少交换次数是，此情况说明该数据元素序列是。
0 已按排序要求有序的
二、单选题（每题2分，共24分）
1、如果采用直接选择排序法来排序一个长度为5，且已按相反顺序排序的数组，共需的比较次数是。
A、1
B、15
C、8
D、10
D
2、有一组随机数25，84，21，47，15，27，68，35，20，现在采用某种算法对它们进行排序，
具体过程如下：
（1）25 84 21 47 15 27 68 35 20
（2）20 15 21 25 47 27 68 35 84
（3）15 20 21 25 35 27 47 68 84
（4）15 20 21 25 27 35 47 68 84
请根据以上情况，判断所用的排序方法是。
A、直接选择排序
B、快速排序
C、冒泡排序
D、Shall 排序
B
3、在所有学过的排序方法中，关键字比较次数与记录的初始排列次序无关的是。
A、冒泡排序
B、直接选择排序
C、直接插入排序
D、Shell排序
B
4、设有1000个无序的数据元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用的排序方法是。
A、冒泡排序
B、基数排序
C、堆排序
D、快速排序
C
5、在待排元素序列基本有序的前提下，下面给出的几种排序方法效率最高的是。
A、直接插入排序
B、直接选择排序
C、归并排序
D、快速排序
A
6、现有一待排序列为49，38，65，97，76，13，27，50，如果以第一个数据元素49为支撑元素，在经过一趟快速排序后的结果序列是。
A、27，38，65，97，76，13，49，50
B、27，38，49，97，76，13，65，50
C、27，38，13，49，76，97，65，50
D、27，38，13，97，76，49，65，50
C
7、在下面给出的几种排序方法中，从未排序之序列中依次取出元素与已经排好的序列（开始为空）中的元素进行比较以确定其在已排序列中的位置的排序方法是。
A、冒泡排序
B、希尔排序
C、快速排序
D、直接插入排序
D
8、在下面给出的几种排序方法中，从未排序之序列中挑选元素，并将其依次放入已经排好的序列（开始为空）的一端的排序方法是。
A、冒泡排序
B、希尔排序
C、直接选择排序
D、直接插入排序
C
9、在下面给出的几种排序方法中，要求辅存空间最大的排序方法是。
A、快速排序
B、归并排序
C、直接选择排序
D、直接插入排序
B
10、下面哪一种情况不利于发挥快速排序的优势。
A、待排序的数据量很大
B、待排序的数据相同率高
C、待排序的数据中有的数值很大
D、待排序的数据基本有序
D
11、下面哪一种情况不利于发挥堆排序的优势。
A、待排序的数据量很大
B、待排序的数据量小
C、待排序的数据中有的数值很大
D、待排序的数据相同率高
B
12、下面哪一种情况不利于发挥基数排序的优势。
A、待排序的数据量很大
B、待排序的数据基本有序
C、待排序的数据中有的数值很大
D、待排序的数据相同率高
C
13、在下面给出的几种排序方法中，要求辅存空间最小的排序方法是。
A、堆排序
B、基数排序
C、快速排序
D、归并排序
A
10.6 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。若A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。
(1) 这种排序方法结束的条件是什么？
(2) 写出奇偶交换排序的算法。
(3) 当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的排序码比较次数是多少？
【解答】
(1) 设有一个布尔变量exchange，判断在每一次做过一趟奇数项扫描和一趟偶数项扫描后是否有过交换。若exchange = 1，表示刚才有过交换，还需继续做下一趟奇数项扫描和一趟偶数项扫描；若exchange = 0，表示刚才没有交换，可以结束排序。
(2) 奇偶排序的算法
template void dataList :: odd-evenSort ( ) {
int i, exchange;
do {
exchange = 0;
for ( i = 1; i < CurrentSize; i += 2 ) //扫描所有奇数项
if ( Vector[i] > Vector[i+1] ) {//相邻两项比较, 发生逆序
exchange = 1; //作交换标记
swap ( Vector[i], Vector[i+1] ); //交换
}
for ( i = 0; i < CurrentSize; i += 2 ) //扫描所有偶数项
if ( Vector[i] > Vector[i+1] ) {//相邻两项比较, 发生逆序
exchange = 1; //作交换标记
swap ( Vector[i], Vector[i+1] ); //交换
}
} while ( exchange != 0 );
}
(3) 设待排序对象序列中总共有n个对象。序列中各个对象的序号从0开始。则当所有待排序对象序列中的对象按排序码从大到小初始排列时，执行m = ⎣(n+1)/2⎦趟奇偶排序。当所有待排序对象序列中的对象按排序码从小到大初始排列时，执行1趟奇偶排序。
在一趟奇偶排序过程中，对所有奇数项扫描一遍，排序码比较⎣(n-1)/2⎦次；对所有偶数项扫描一遍，排序码比较⎣n/2⎦次。所以每趟奇偶排序两遍扫描的结果，排序码总比较次数为⎣(n-1)/2⎦+ ⎣n/2⎦ = n-1。
10.23
void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法
{
