数据结构chap009

10.1概述10.2插入排序10.3快速排序10.4堆排序10.5归并排序10.6基数排序10.7各种排序方法的综合比较10.8外部排序10.1概述一、排序的定义二、内部排序和外部排序三、内部排序方法的分类一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97一般情况下，假设含n个记录的序列为{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。二、内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类其它方法待排记录的数据类型定义如下:#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置intlength;//顺序表长度}SqList;//顺序表类型1.插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。2.交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。3.选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。4.归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。5.其它方法10.2插入排序有序序列R[1..i-1]R[i]无序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]无序序列R[i+1..n]实现“一趟插入排序”可分三步进行：3．将R[i]插入(复制)到R[j+1]的位置上。2．将R[j+1..i-1]中的所有记录均后移一个位置；1．在R[1..i-1]中查找R[i]的插入位置，R[1..j].keyR[i].keyR[j+1..i-1].key；直接插入排序（基于顺序查找）表插入排序（基于链表存储）不同的具体实现方法导致不同的算法描述折半插入排序（基于折半查找）希尔排序（基于逐趟缩小增量）一、直接插入排序利用“顺序查找”实现“在R[1..i-1]中查找R[i]的插入位置”算法的实现要点：从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；R[0]=R[i];//设置“哨兵”循环结束表明R[i]的插入位置为j+1R[0]jR[i]for(j=i-1;R[0].keyR[j].key;--j);//从后往前找j=i-1插入位置对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；for(j=i-1;R[0].keyR[j].key;--j);R[j+1]=R[j]R[0]jR[i]j=i-1上述循环结束后可以直接进行“插入”插入位置令i=2，3，…,n,实现整个序列的排序。for(i=2;i=n;++i)if(R[i].keyR[i-1].key){在R[1..i-1]中查找R[i]的插入位置;插入R[i];}voidInsertionSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i=L.length;++i)if(L.r[i].keyL.r[i-1].key){}}//InsertSortL.r[0]=L.r[i];//复制为监视哨for(j=i-1;L.r[0].keyL.r[j].key;--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：112nni02)1)(4()1(2nnini“移动”的次数：“移动”的次数：2)1)(4()1(2nnini因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。二、折半插入排序voidBiInsertionSort(SqList&L){}//BInsertSort在L.r[1..i-1]中折半查找插入位置；for(i=2;i=L.length;++i){}//forL.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]for(j=i-1;j=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入low=1;high=i-1;while(low=high){}m=(low+high)/2;//折半if(L.r[0].keyL.r[m].key)high=m-1;//插入点在低半区elselow=m+1;//插入点在高半区14364952805861239775ilowhighmmlowlowmhigh14364952586180239775ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r三、表插入排序为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。voidLInsertionSort(ElemSL[]，intn){//对记录序列SL[1..n]作表插入排序SL[0].key=MAXINT;SL[0].next=1;SL[1].next=0;for(i=2;i=n;++i)for(j=0,k=SL[0].next;SL[k].key=SL[i].key;j=k,k=SL[k].next){SL[j].next=i;SL[i].next=k;}//结点i插入在结点j和结点k之间}//LinsertionSort算法中使用了三个指针：其中：p指示第i个记录的当前位置i指示第i个记录应在的位置q指示第i+1个记录的当前位置如何在排序之后调整记录序列？voidArrange(ElemSL[],intn){p=SL[0].next;//p指示第一个记录的当前位置for(i=1;in;++i){while(pi)p=SL[p].next;q=SL[p].next;//q指示尚未调整的表尾if(p!=i){SL[p]←→SL[i];//交换记录，使第i个记录到位SL[i].next=p;//指向被移走的记录}p=q;//p指示尚未调整的表尾，//为找第i+1个记录作准备}}//Arrange四、希尔排序（又称缩小增量排序）基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：将记录序列分成若干子序列，分别对每个子序列进行插入排序。其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将n个记录分成d个子序列：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}例如：162512304711233691831第一趟希尔排序，设增量d=5112312918162536304731第二趟希尔排序，设增量d=3918121123162531304736第三趟希尔排序，设增量d=1911121618232530313647voidShellInsert(SqList&L,intdk){for(i=dk+1;i=n;++i)if(L.r[i].keyL.r[i-dk].key){L.r[0]=L.r[i];//暂存在R[0]for(j=i-dk;j0&&(L.r[0].keyL.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//记录后移，查找插入位置L.r[j+dk]=L.r[0];//插入}//if}//ShellInsertvoidShellSort(SqList&L,intdlta[],intt){//增量为dlta[]的希尔排序for(k=0;kt;++t)ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序}//ShellSort10.3快速排序一、起泡排序二、一趟快速排序三、快速排序四、快速排序的时间分析一、起泡排序假设在排序过程中，记录序列R[1..n]的状态为：第i趟起泡排序无序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1无序序列R[1..n-i]有序序列R[n-i+1..n]比较相邻记录，将关键字最大的记录交换到n-i+1的位置上voidBubbleSort(ElemR[],intn){while(i1){}//while}//BubbleSorti=n;i=lastExchangeIndex;//本趟进行过交换的//最后一个记录的位置if(R[j+1].keyR[j].key){Swap(R[j],R[j+1]);lastExchangeIndex=j;//记下进行交换的记录位置}//iffor(j=1;ji;j++)lastExchangeIndex=1;注意:2.一般情况下，每经过一趟“起泡”，“i减一”，但并不是每趟都如此。例如:52319782553157989i=7i=6for(j=1;ji;j++)if(R[j+1].keyR[j].key)…13i=21.起泡排序的结束条件为，最后一趟没有进行“交换记录”。时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡“比较”的次数：0“移动”的次数：“移动”的次数：n-12)1()1(2nnini2)1(3)1(32nnini二、一趟快速排序（一次划分）目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且R[j].key≤R[i].key≤R[j].key(s≤j≤i-1)枢轴(i+1≤j≤t)。52498036145861972375stlowhigh设R[s]=52为枢轴将R[high].key和枢轴的关键字进行比较，要求R[high].key≥枢轴的关键字将R[low].key和枢轴的关键字进行比较，要求R[low].key≤枢轴的关键字high23low80high14low52例如R[0]52lowhighhighhighlow可见，经过“一次划分”，将关键字序列5