第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次交换和选择后，未排序记录为 。

5. n 个记录的冒泡排序算法所需的最大移动次数为，最小移动次数为。

6. 对n 个结点进行快速排序，最大的比较次数是

7. 对于堆排序和快速排序，若待排序记录基本有序，则选用。

8. 在归并排序中，若待排序记录的个数为20，则共需要进行趟归并。

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

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

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]

int temp = table[i];

table[i] = table[i - 1];

table[i - 1] = temp;

t = i;

}

}

left = t + 1;

//反向部分

for (int i = left; i

if (table[i]

int temp = table[i];

table[i] = table[i - 1];

table[i - 1] = temp;

t = i;

}

}

right = t - 1;

} while (left

}

4． 试设计算法，使用非递归方法实现快速排序。

参考答案:

public static void NonrecursiveQuickSort(int[] ary) {

if (ary.length

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

if (ary[j]

int temp = ary[j];

ary[j] = ary[i];

ary[i] = temp;

i++;

}

}

//如果i 不是基准位，那么基准位选的就不是最大值

//而i 的前面放的都是比基准位小的值，那么基准位

//的值应该放到i 所在的位置上

if (i != pivot) {

int temp = ary[i];

ary[i] = ary[pivot];

ary[pivot] = temp;

}

if (i - low > 1) {

//此时不排i 的原因是i 位置上的元素已经确定了，i 前面的都是比i 小的，i 后面的都是比i 大的

stack[1][top] = i - 1;

stack[0][top] = low;

top++;

}

//当high-i 小于等于1的时候，就不往栈中放了，这就是外层while 循环能结束的原因 //如果从i 到高位之间的元素个数多于一个，那么需要再次排序

if (high - i > 1) {

//此时不排i 的原因是i 位置上的元素已经确定了，i 前面的都是比i 小的，i 后面的都是比i 大的

stack[1][top] = high;

stack[0][top] = i + 1;

top++;

}

}

}

5． 试设计算法，判断完全二叉树是否为大顶堆。

参考答案:

boolean checkmax(BiTreeNode t) //判断完全二叉树是否为大顶堆

{

BiTreeNode p = t;

if (p.getLchild() == null && p.getRchild() == null) {

return true;

} else {

if (p.getLchild() != null && p.getRchild() != null) {

if ((((RecordNode)

p.getLchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey())

p.getData()).getKey())

return checkmax(p.getLchild()) && checkmax(p.getRchild());

} else

{

return false;

}

} else if (p.getLchild() != null && p.getRchild() == null) {

if ((((RecordNode)

p.getLchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey())

return checkmax(p.getLchild());

} else

{

return false;

}

} else if (p.getLchild() == null && p.getRchild() != null) {

if ((((RecordNode)

p.getRchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey())

return checkmax(p.getRchild());

} else

{

return false;

}

} else {

return false;

}

}

}