第七章排序习题参考解析.doc

习题七 参考答案 一、选择题 　　1．内排序法的稳定性是指( )。 　　A．该排序算法不允许有相同的关键字记录 　　B．该排序算法允许有相同的关键字记录 　　C．平均时间为0（n log n）的排序方法 　　D．以上都不对 2．下面给出的四种排序中( B )是不稳定排序。　　 A．插入?? B．堆??? C．二路归并? ?? D．冒泡在下列排序算法中哪一算法的时间复杂度与初始排序无关（ ）。　　 A．直接插入排序 B．泡排序? C．快速排序? D．直接选择排序 ．序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( )的两趟排序后的结果。 　　A．选择排序??? B.冒泡排序???? C.插入排序??? D.堆排序 ．。 　　A．选择B．C．快速 D．6．一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为得到的一次划分结果为（ ）。 　　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)二、题 }。 n个记录的冒泡排序算法所需的最大移动次数为 3n(n-1)/2 ，最小移动次数为 0 。 对n个结点进行快速排序，最大的比较次数是 n(n-1)/2 。 对于堆排序和快速排序，若待排序记录基本有序，则选用 堆排序 。 在归并排序中，若待排序记录的个数为20，则共需要进行 5 趟归并。 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是 关键字的比较 和 数据元素的移动 。 10． 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是 快速排序 ，需要内存容量最多的是 基数排序 。 三、题 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是下一个待插入结点的指针 } } 试设计算法，用选择排序方法对单链表进行排序。 参考答案: //单链表选择排序算法 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.parse