10内部排序
- 格式：docx
- 大小：17.34 KB
- 文档页数：5
第10章内部排序10.1以关键码序列(503, 087, 512, 061, 908, 170, 897, 275, 653, 426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：(1)直接插入排序(2) 希尔排序(d[1]=5, d[2]=3, d[3]=1) (3) 快速排序(第一个记录为基准记录) (4) 堆排序(5) 归并排序(6) 基数排序解答：（1）直接插入排序：第一趟：087,503, 512, 061, 908, 170, 897, 275, 653, 426第二趟：087,503, 512, 061, 908, 170, 897, 275, 653, 426第三趟：061,087,503, 512, 908, 170, 897, 275, 653, 426第四趟：061,087,503, 512, 908, 170, 897, 275, 653, 426第五趟：061,087, 170, 503, 512, 908, 897, 275, 653, 426第六趟：061,087, 170, 275, 503, 512, 897, 908, 653, 426第八趟：061,087, 170, 275, 503, 512, 653, 897, 908, 426第九趟：061,087, 170, 275, 426, 503, 512, 653, 897, 908（2）希尔排序(d[1]=5, d[2]=3, d[3]=1)第一趟：170,087, 275, 061, 426, 503, 897, 512, 653, 908第二趟：061,087, 275, 170, 426, 503, 897, 512, 653, 908第三趟：061,087, 170, 275, 426, 503, 512, 653, 897, 908(3) 快速排序(第一个记录为基准记录)第一趟：(426,087,275,061,170) 503(897,908,653,512)第二趟：(170, 087,275,061)426, 503(512,653)897(908)第三趟：(061,087)170(275) 426, 503,512(653) 897, 908第四趟：061,087, 170, 275, 426, 503, 512, 653, 897, 908(4) 堆排序（小根堆为例）建堆：061, 087, 170, 275, 426,512, 897, 503, 653, 908第一趟：（输出061）087, 275, 170, 503, 426,512,897,653第二趟：（输出087）170, 275, 512, 503, 426, 653, 897,9 08第三趟：（输出170）275, 406, 512, 503, 908, 653, 897第四趟：（输出275）406, 503, 512, 897, 908, 653第五趟：（输出406）503, 653, 512, 897, 908第六趟：（输出503）512, 653, 908, 897第七趟：（输出512）653, 897, 908第八趟：（输出653）897, 908第九趟：（输出897）908(5) 归并排序第一趟：(087, 503)(061, 512)(170, 908)(275, 897)(426, 653)第二趟：(061, 087, 503, 512)(170, 275, 897, 908)(426, 653)第三趟：(061, 087, 170, 275, 503, 512, 897, 908) (426, 653)第四趟：061,087, 170, 275, 426, 503, 512, 653, 897, 908(6)简单选择排序第一趟：061,087,512,503,908,170,897,275,653,426第二趟：061,087,512,503,908,170,897,275,653,426第三趟：061,087,170,503,908,512,897,275,653,426第四趟061,087,170,275,908,512,897,503,653,426第五趟061,087,170,275,426,512,897,503,653,908第六趟061,087,170,275,426,503,897,512,653,908第七趟061,087,170,275,426,503,512,653,897,90810.7不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。
（1）n=7时在最好情况下需进行多少次比较？请说明理由。
（2）对n=7给出一个最好情况的初始排列实例。
解：最好的情况是每次都能均匀的划分序列.例如 4,1,3,2,6,5,7,每次使用序列的第一个元素做枢轴.比较总次数为10次,交换3次,具体如下：第一次枢轴为4,序列划分为{2,1,3},4,{6,5,7}比较6次（4与每个元素比较一次）,交换1次（4与2交换）第二次的两个序列枢轴分别为2和6,此时划分序列得{1},2,{3},4,{5},6,{7} 比较4次（两个序列各比较两次）,交换两次（1和2,6和5）第三次由于各个序列的元素都为1,因此排序完成得1,2,3,4,5,6,710.12判别以下序列是否为堆（大顶堆或小顶堆）。
如果不是，则把它调整为堆（要求记录交换的次数最少）。
（1）（100,86,48,73,35,39,42,57,66,21）；（2）（12,70,33,65,24,56,48,92,86,33）；（3）（103,97,56,38,66,23,42,12,30,52,06,20）；（4）（05,56,20,23,40,38,29,61,35,76,28,100）。
（1）大顶堆；（2）否。
调整为小顶堆如下：（12，24，33，65，33，56，48，92，86，70）（3）大顶堆；（4）否。
调整为小顶堆如下：（05，23，20，35，28，38，29，61，56，76，40，100）10.23 试以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_Sort110.26如下述改写教科书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; //c指示这一趟冒泡中发生交换的元素}change=c;}//while}//Bubble_Sort110.31编写算法,对n个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录排在关键字为非负值的记录之前,要求: (1) 采用顺序存储结构,至多使用一个记录的辅助存储空间 (2) 算法的时间复杂度 (3) 讨论算法中记录的最大移动次数.void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前{low=0;high=n-1;while(low<high){while(low<high&&a[high]>=0) high--; //以0作为虚拟的枢轴记录a[low]<->a[high];while(low<high&&a[low]<0) low++;a[low]<->a[high];}}//Divide时间复杂度为O（n）最大移动次数为n/210.33 试以单链表为存储结构实现简单排序的算法。
void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法{for(p=L;p->next->next;p=p->next){q=p->next;x=q->data;for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点if(r->next->data<x){x=r->next->data;s=r;}if(s!=q) //找到了值比q->data更小的最小结点s->next {p->next=s->next;s->next=q;q->next=p->next->next;t=s->next;t->next= s->next->next;} //交换q和s->next两个结点}//for}//LinkedList_Select_Sort。
