数据结构复习题

设待排序序列为 {10, 18, 4, 3, 6,

12, 1, 9, 15, 8},请给出用希尔排序每一趟的结果。增量序列取为5, 3, 2, 1。

算法题 试以L.r[k+1]作为监视哨改写教科书10.2.1 节中给出的直接插入排序算法，其中 L.r[1..k]为待排序记录且k<MAXSIZE 编写一个双向起泡的排序算法，即相邻两遍

向相反方向起泡

void Insert_Sort1(SqList &L)//监视哨设 在高下标端的插入排序算法 { k=L.length; for(i=k-1;i;--i) //从后向前逐个插入排序 if(L.r[i].key>L.r[i+1].key) { L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 } }//Insert_Sort1

void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算 法 { low=0;high=n-1; //冒泡的上下界 change=1; while(low<high&&change) { change=0; for(i=low;i<high;i++) //从上向下起泡 if(a[i]>a[i+1]) { a[i]<->a[i+1]; change=1; } high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i]<a[i-1]) { a[i]<->a[i-1]; change=1; } low++; //修改下界 }//while }//Bubble_Sort2

如下改写教科书10.3节中所述起泡排序 算法：将1.4.3节的算法中用以起控制作 用的布尔变量change改为一个整型变量，

指示每一趟排序中进行交换的最后一个记录的位置，并以它作为下一趟起泡排 序循环终止的控制值

void Bubble_Sort1(int a[ ],int n)//对包含n个元素 的数组a进行改进的冒泡排序 {change=n-1; //change指示上一趟冒泡中最后发生 交换的元素 while(change) { for(c=0,i=0;i<change;i++) if(a[i]>a[i+1]) { a[i]<->a[i+1]; c=i+1; //c指示这一趟冒泡中发生交换的元素 } change=c; }//while }//Bubble_Sort1

设待排序的关键字序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序 方法每趟排序后的结果。(由小至大有序) (1)直接插入排序 (2) 希尔排序(增量为5,2,1)

(3) 起泡排序(先产生最小的)(4) 快速排序 (5) 直接选择排序 (6) 堆排序(大顶堆，输出由大至小有序) (7) 二路归并排序

【解答】 (1) 直接插入排序

(3) 起泡排序