习题七 参考答案
一、选择题
1．内部排序算法的稳定性是指( D )。
A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对
2．下面给出的四种排序算法中，( B )是不稳定的排序。
A．插入排序 B．堆排序 C．二路归并排序 D．冒泡排序 3. 在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（ D ）。 A．直接插入排序 B．冒泡排序 C．快速排序 D．直接选择排序
4．关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟排序后的结果。
A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 5．下列排序方法中，( D )所需的辅助空间最大。
A．选择排序 B．希尔排序 C．快速排序 D．归并排序 6．一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为支点得到的一次划分结果为（ C ）。
A．(38,40,46,56,79,84) B．(40,38,46,79,56,84) C．(40,38,46,56,79,84) D．(40,38,46,84,56,79)
7．在对一组关键字序列{70，55，100，15，33，65，50，40，95}，进行直接插入排序时，把65插入，需要比较( A )次。
A. 2 B. 4 C. 6 D. 8
8.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为( B )。 A. 希尔排序 B. 直接选择排序 C. 冒泡排序 D. 快速排序 9．当待排序序列基本有序时，以下排序方法中，( B )最不利于其优势的发挥。 A. 直接选择排序 B. 快速排序 C.冒泡排序 D.直接插入排序 10．在待排序序列局部有序时，效率最高的排序算法是( B )。
A. 直接选择排序 B. 直接插入排序 C. 快速排序 D.归并排序 二、填空题
1. 执行排序操作时，根据使用的存储器可将排序算法分为 内排序 和 外排序 。
2. 在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表中时，为寻找插入位置需比较 3 次。
3. 在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用 直接插入排序 。 4. 在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录为 {50,70,60,95,80}。
5. n个记录的冒泡排序算法所需的最大移动次数为 3n(n-1)/2 ，最小移动次数为 0 。 6. 对n个结点进行快速排序，最大的比较次数是 n(n-1)/2 。
7. 对于堆排序和快速排序，若待排序记录基本有序，则选用 堆排序 。
8. 在归并排序中，若待排序记录的个数为20，则共需要进行 5 趟归并。
9. 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是 关键字的比较 和 数据元素的移动 。
10． 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是 快速排序 ，需要内存容量最多的是 基数排序 。 三、算法设计题
1． 试设计算法，用插入排序方法对单链表进行排序。 参考答案:
public static void insertSort(LinkList L) {
Node p, q, r, u;
p = L.getHead().getNext(); L.getHead().setNext(null);
//置空表，然后将原链表结点逐个插入到有序表中
while (p != null) { //当链表尚未到尾，p为工作指针 r = L.getHead();
q = L.getHead().getNext();
while (q != null && (Integer.parseInt((String) q.getData())) <= (Integer.parseInt((String) p.getData()))) {
//查P结点在链表中的插入位置，这时q是工作指针 r = q;
q = q.getNext(); }
u = p.getNext();
p.setNext(r.getNext()); r.setNext(p); p = u;
//将P结点链入链表中，r是q的前驱，u是下一个待插入结点的指针
} }
2． 试设计算法，用选择排序方法对单链表进行排序。 参考答案:
//单链表选择排序算法
public static void selectSort(LinkList L) {
//p为当前最小,r为此过程中最小,q为当前扫描接点 Node p, r, q;
Node newNode = new Node(); newNode.setNext(L.getHead()); L.setHead(newNode);
//制造一个最前面的节点newNode，解决第一个节点的没有前续节点需要单独语句的问题。 p = L.getHead();
while (p.getNext().getNext() != null) { r = p.getNext();
q = p.getNext().getNext(); while (q.getNext() != null) {
if (Integer.parseInt((String) q.getNext().getData()) <= (Integer.parseInt((String) r.getNext().getData()))) { r = q; }
q = q.getNext(); }
if (r != p) { //交换p与r Node swap = r.getNext();
r.setNext(r.getNext().getNext()); //r的next指向其后继的后继 swap.setNext(p.getNext());
p.setNext(swap); //p的后继为swap
}
p = p.getNext(); }//while p.setNext(null); }
3． 试设计算法，实现双向冒泡排序(即相邻两遍向相反方向冒泡)。 参考答案:
//产生随机数方法
public static int[] random(int n) { if (n > 0) {
int table[] = new int[n]; for (int i = 0; i < n; i++) {
table[i] = (int) (Math.random() * 100);
//产生一个0~100之间的随机数
}
return table; }
return null; }
//输出数组元素方法
public static void print(int[] table) {
if (table.length > 0) {
for (int i = 0; i < table.length; i++) { System.out.print(table[i] + \ }
System.out.println(); } }
//双向冒泡排序方法
public static void dbubblesort(int[] table) { int high = table.length; int left = 1;
int right = high - 1; int t = 0; do {
//正向部分
for (int i = right; i >= left; i--) { if (table[i] < table[i - 1]) { int temp = table[i]; table[i] = table[i - 1]; table[i - 1] = temp; t = i; } }
left = t + 1; //反向部分
for (int i = left; i < right + 1; i++) { if (table[i] < table[i - 1]) { int temp = table[i]; table[i] = table[i - 1]; table[i - 1] = temp; t = i; } }
right = t - 1;
} while (left <= right); }
4． 试设计算法，使用非递归方法实现快速排序。 参考答案:
public static void NonrecursiveQuickSort(int[] ary) { if (ary.length < 2) { return; }
//数组栈：记录着高位和低位的值
int[][] stack = new int[2][ary.length]; //栈顶部位置 int top = 0;
//低位，高位，循环变量，基准点 //将数组的高位和低位位置入栈 stack[1][top] = ary.length - 1; stack[0][top] = 0; top++;
//要是栈顶不空，那么继续 while (top != 0) { //将高位和低位出栈 //低位：排序开始的位置 top--;
int low = stack[0][top]; //高位：排序结束的位置
int high = stack[1][top]; //将高位作为基准位置 //基准位置
int pivot = high; int i = low;
for (int j = low; j < high; j++) {
if (ary[j] <= ary[pivot]) { int temp = ary[j]; ary[j] = ary[i]; ary[i] = temp; i++; } }
//如果i不是基准位，那么基准位选的就不是最大值