数据结构第十章内部排序

第10章内部排序10.1概述排序：将一组任意排列的数据元素序列，重新排列成一个按关键字有序（升序或降序）的序列排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、树型选择排序、堆排序归并排序：2-路归并排序基数排序稳定排序和不稳定排序待排序列的数据存储类型#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;InfoTypeotherinfo;}RedType;typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置intlength;}SqList;10.2插入排序4938659776132749012345678(49)3849)65)97)7697)133849657697)2797)76654938274997)7665

494938659776132749012345678(49)3849)3810.2插入排序基本思想：将一个记录插入到已排好序的有序表中，得到新的表依然有序。实现：将序列中第1个记录看成是一个有序子序列，从第2个记录开始到第n个记录，逐个进行插入，直至整个序列有序4938659776132749例：voidInsertSort(SqList&L){for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i–1].key){L.r[0]=L.r[i];L.r[i]=L.r[i-1];for(j=i–2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}1、直接插入排序算法评价：总比较次数：最小值：Cmin=n-1≈n(正序)最大值：Cmax=(逆序)n∑i

i=2(n+2)(n-1)2

=≈n22总移动次数：最小值：Mmin=0(正序)最大值：Mmax=(逆序)n∑(i+1)

i=2≈n22平均比较次数：12

(+n)n22≈n24平均移动次数：12

(+0)n22≈n24时间复杂度：O(n2)空间复杂度：O(1)1个辅助空间稳定排序2、其它插入排序在有序表中查找插入位置时，可采用折半查找方法。折半插入排序4938659776132749012345678271338496576972749lowhighmid271338496576974927移动次数不变，查找位置时比较次数可能减少。2、其它插入排序折半插入排序voidBInsertSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i–1;while(low<=high){m=(low+high)/2;ifLT(L.r[0].key,L.r[m].key)high=m–1;elselow=m+1;}for(j=i–1;j>=high+1;--j)L.r[j+1]=L.r[j];L.r[high+1]=L.r[0];}}时间复杂度：O(n2)空间复杂度：O(1)1个辅助空间

2-路插入排序为减少移动次数，增加n个辅助空间空间复杂度为O(n)但当首关键字为最大或最小时失去意义493865977613274901234567849386597977613132749657697表插入排序为减少移动次数，先连成一个有序链，再调整成有序序列存储结构：

#defineSIZE100typedefstruct{RcdTyperc;intnext;}SLNode;typedefstruct{SLNoder[SIZE];intlength;}SlinkListType;增加n个辅助空间n个指针域MAXINT49386597761327490123456780112030445262738(已排序表中元素个数)总比较次数最大值：Cmax=n-1∑i

i=1n(n-1)2

=≈n22移动次数为0空间复杂度为：O(n)另外需重排Cmin=Cmax=i1最小值Cmin=n-1≈n分析：一趟排序：增加n个辅助空间n个指针域MAXINT49386597761327490123456780112030445262738P=6,i=1---SL.length-1循环134987P=7(6)i=2273821P=2(7)i=3P=7386551P=1i=4(7)P=6974908P=8i=5(6)764943P=3(8)i=6P=7976505P=5(7)i=7P=8977604表插入排序重排记录算法voidArrange(SLinkListType&SL){p=SL.r[0].next;for(i=1;i<SL.length;++i){while(p<i)p=SL.r[p].next;q=SL.r[p].next;if(p!=i){SL.r[p]←→SL.r[i];SL.r[i].next=p;}p=q;}}希尔排序直接插入排序的时间复杂度为O(n2)，但若待排记录为正序时，则时间复杂度为O(n)，若“基本有序”，则可提高效率。另外在n较小时，算法效率较高且简单。取d3=1三趟分组：1327485544938659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分组：49

38

65

97

76

13

27

48

55

4取d2=3二趟分组：13

27

48

55

4

49

38

65

97

76增量的选择voidShellInsert(SqList&L,intdk){for(i=dk+1;i<=L.length;++i)ifLT(L.r[i].key,L.r[i–dk].key){L.r[0]=L.r[i];for(j=i–dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];L.r[j+dk]=L.r[0];}}voidShellSort(SqList&L,intdlta[],intt){for(k=0;k<t;++k)ShellInsert(L,dlta[k]);}效率：统计数据，比较次数和移动次数约为n1.310.3快速排序1、冒泡排序基本思想：对n个记录，依次比较相邻两个关键字，不满足条件，则交换-----一趟冒泡排序对前n-1个记录作第二趟排序重复共作n-1趟。voidsort(SqList&L){for(i=1;i<=L.length-1;i++){flag=FALSE;for(j=1;j<=L.length–i;j++){if(L.r[j].key>L.r[j+1].key){L.r[j]<-->L.r[j+1];flag=TRUE;}}if(!flag)break;}}算法评价：初始正序：移动次数为：0比较次数为：n-1初始逆序：n-1∑(n–i)=

i=1比较次数：12

n(n-1)移动次数：12

n(n-1)3时间复杂度为O(n2)稳定排序2、快速排序基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序例初始关键字：4938659776132750ijPivotkey=49ji完成一趟排序：(273813)49(76976550)分别进行快速排序：(13)27(38)49(5065)76(97)快速排序结束：13273849

506576974927ijijij4965ji1349ij4997ij初始关键字：4938659776132750971365ijPivotkey=49ji27ijijijjiij49ijintPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];pivotkey=L.r[low].key;while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];}L.r[low]=L.r[0];returnlow;}voidQsort(SqList&L,intlow,inthigh){if(low<high){pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc–1);Qsort(L,pivotloc+1,high);}}算法评价：递归过程，需使用栈最好情况：log2n+1最坏情况：O(n)时间：有序情况最坏，每趟比较后放在原来位置上总比较次数：n-1∑(n–i)=

i=112

n(n-1)≈n22另外每次调用正好在中间位置比较次数：C(n)≤n+2C(n/2)≤2n+4C(n/4)≤3n+8C(n/8)≤kn+2kC(n/2k)令n=2k=n•log2n+nC(1)O(n•log2n)可证明平均比较次数O(n•log2n)而移动次数小于比较次数，所以总时间为O(n•log2n)不稳定排序例：55110.4选择排序1、简单选择排序基本思想：每一趟在n-i+1(i=1,2…,n-1)个记录中选择关键字最小的记录作为有序序列中第i个记录。49386597761327490123456781349273838654997497665977697排序过程第1趟：通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第1个记录交换第2趟：通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第2个记录交换第i趟：通过n-i次比较，从剩余的n-i+1个记录中找出关键字次小的记录，将它与第i个记录交换重复，i由1..n-1共进行n-1趟排序后，排序结束简单选择排序算法voidSelectSort(SqList&L){for(i=1;i<L.length;++i){j=SelectMinKey(L,i);if(i!=j)L.r[i]←→L.r[j];}}算法评价：总比较次数：n-1∑(n–i)=

i=112

n(n-1)移动次数：当有序时为0最坏每次交换3(n-1)总时间复杂度：O(n2)空间复杂度为：O(1)交换用1个空间稳定性例221不稳定排序49386597761327490123456782、树形选择排序974938761365274913381338651327∞762727∞132749493838∞4949492、树形选择排序比较次数：第一次n-1次以后每次log2n次总比较次数：(n-1)+(n-1)log2n≈n•log2n移动次数不超过比较次数所以时间复杂度为O(n•log2n)空间增加了n-1个结点保存比较结果另外排序结果需另开辟n个空间所以共需n+n-1个空间不稳定排序3、堆排序堆的定义：n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1例（96，83，27，38，11，9）例（13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第二个问题解决方法——筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13273849502765769713输出：13276549502738769713输出：132738279797274965502738769713输出：1327387665502738499713输出：132738495065762738499713输出：132738499765762738495013输出：13273849506597762738495013输出：13273849509765762738495013输出：1327384950657665972738495013输出：1327384950659765762738495013输出：132738495065769765762738495013输出：1327384950657697第一个问题解决方法方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例含8个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097typedefSqListHeapType;

voidHeapAdjust(HeapType&H,ints,intm){rc=H.r[s];for(j=2*s;j<=m;j*=2){if(j<m&<(H.r[j].key,H.r[j+1].key))++j;if(!LT(rc.key,H.r[j].key))break;H.r[s]=H.r[j];s=j;}H.r[s]=rc;}

voidHeapSort(HeapType&H){for(i=H.length/2;i>0;--i)HeapAdjust(H,i,H.length);for(i=H.length;i>1;--i){H.r[1]←→H.r[i];HeapAdjust(H,1,i–1);}}算法评价：比较次数同树形选择排序时间为O(n•log2n)不稳定排序10.5归并排序归并:将两个或两个以上的有序表组合成一个新的有序表2-路归并排序排序过程设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1两两合并，得到「n/2︳个长度为2或1的有序子序列再两两合并，……如此重复，直至得到一个长度为n的有序序列为止例初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){for(j=m+1,k=i;i<=m&&j<=n;++k){ifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=SR[i..m];if(j<=n)TR[k..n]=SR[j..n];}

voidMSort(RcdTypeSR[],RcdType&TR1[],ints,intt){if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;MSort(SR,TR2,s,m);MSort(SR,TR2,m+1,t);Merge(TR2,TR1,s,m,t);}voidMergeSort(SqList&L){MSort(L.r,L.r,1,L.length);}算法评价：2路归并：第1趟归并后有序子序列长度为2第2趟归并后有序子序列长度为4第i趟归并后有序子序列长度为2i若序列中共有n个元素设n=2i则需作i趟归并即需作log2n趟归并而每趟归并所用时间为O(n)所以时间复杂度为O(n•log2n)空间需要和待排记录等量的辅助空间即空间复杂度为O(n)稳定排序…………10.6基数排序例对52张扑克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A两个关键字：花色（<<<）

面值（2<3<……<A）并且“花色”地位高于“面值”多关键字排序多关键字排序方法最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列链式基数排序初始状态：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二