第7章排序习题参考答案

习题七 参考答案 一、选择题 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不是基准位，那么基准位选的就不是最大值