第九章 习题.pptVIP

第九章 排 序 9-1 9-5 9-7 9-10 9-28 9-1 设文件(R1，R2，…，Rn)以单链表方式表示，指针变量FIRST指向表头结点，且表中的结点结构为：其中KEY为该结点的关键词域，LINK为链接域. 请给出这种线性表的直接插入排序算法，并要求算法的时间复杂性为O(n2 )，且算法是稳定的. 基本概念 稳定性:当Kρ(i)=Kρ(j)并且ij时，总有ρ(i)ρ(j)，这里1≤i，j≤n，则我们就称该排序过程具有稳定性. 插入排序:假设1＜j≤n，且记录R1，R2，…，Rj–1已经排序，即有K1≤K2≤…≤Kj–1 。所谓插入，是将一个待排序的记录Rj插入到上述序列中的适当位置，使得新序列正好排序.期望复杂性为 O(n2 )， 9-1 InsertSort (first) IS1[逐一排序] q ← first.　　//q是ｐ的前驱 p ← link (first). While (p≠null) ( k ← key( p). if (key(first)k) //将p插first前 (link (q)← link (p). link (p) ←first. first ← p. p ← link (q). ) 9-1 else ( temp ←first. //从头开始找p的正确位置 while((key(link(temp)) =k) and (link(temp)≠p)) temp ← link (temp). if (link(temp)≠p) (//先删除后把p插入temp之后 link (q)← link( p). link (p)← link (temp). link(temp) ← p.) //p q指针移动 q ← link( q). p ← link (q). )). ▌ 9-5 讨论冒泡排序算法的稳定性. 冒泡排序算法的思想：记录交换的方法是从左到右比较相邻记录的关键词Kj和Kj+1 ．若Kj＞Kj+1，则互换Rj和Rj+1 ． 冒泡排序算法 算法BSort ( R，n ) // 冒泡排序算法，该算法对n个记录R1，R2，…，Rn进行排序 BS1 [冒泡过程] FOR i = n TO 2 STEP –1 DO FOR j = 1 TO i–1 DO IF Kj Kj+1 THEN ( Rj?Rj+1 ) ▌ 由算法的执行过程可知，该算法是稳定的算法。 9-7 奇偶交换排序算法的基本思想描述如下：排序过程通过对文件x[i](l≤i≤n)的若干次扫描来完成，第奇数次扫描，对所有下标为奇数的记录x[i]与其后面的记录x[i+1](l≤ i≤ n–1)相比较，若x[i].KEY(记录x[i]的关键饲)＞x[i+1].KEY，则交换x[i]和x[i+1]的内容；第偶数次扫描，对所有下标为偶数的记录x[i]与其后面的记录x[i+1](2≤i≤n–1)相比较，若 x[i].KEY＞x[i+1].KEY，则交换x[i]和x[i+1]之内容，重复上述过程直到排序完成为止. 9-7 (l)排序的终止条件是什么？ (2)完成该算法的具体设计. (3)分析该算法的平均运行时间(最好/最坏). 9-7 算法Sort(X,n) S1[一趟扫描过程中，均没有记录交换则算法终止] change ← 1. while (change) (change ← 0. for i=1 to n step 2 if (X[i].keyX[i+1].key) ( X[i] ? X[i+1]. change ← 1.) for i=0 to n step 2 if (X[i].keyX[i+1].key) ( X[i] ? X[i+1]. change ← 1.) ) １）最好情况下，比较一趟．每趟中奇交换比较n/2次．偶交换比较（n-1）