第十章-排序(new)数据结构

第十章内部排序熟练掌握若干排序方法：插入排序快速排序堆及选择排序归并排序基数排序法；了解最好、最坏、平均排序的时间复杂性分析方法。10.1概述排序(sorting)：将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。在许多算法中都要利用到排序。排序的定义：假设含n个记录的序列为{R1,R2,…,Rn

}其相应的关键字序列为{K1，K2，…，Kn

}需确定1，2，…，n的一种排列p1，p2，…，pn，使其相应的关键字满足如下的非递减（或非递增）关系Kp1≤Kp2≤…≤Kpn。即使初始的的序列成为一个按关键字有序的序列{Rp1，Rp2，…，Rpn}这样一种操作称为排序。排序：无序有序性质：稳定排序/不稳定排序分类：内部排序，外部排序内部排序：常用内部排序：插入排序、希尔排序、快速排序、选择排序、堆排序、归并排序、基数排序各种排序平均时间要求：按照算法思想定出排序序列。插入排序的思想：将一个元素插入到一个有序表中。 根据寻找插入位置的方法不同分为：直接插入、折半插入、2路插入、表插入等。直接插入排序：最简单的排序方法思想：将一个元素向一个有序序列插入做法：0位监测哨，从一个元素逐步扩大有序序列。举例10.2插入排序49386597761327490直接插入排序算法：voidInsertSort(SqList&L){//对顺序表L作直接插入排序

for(i=2;i<L.length;++i) if(L.r[i].key<L.r[i-1].key){ L.r[0]=L.r[i]; for(j=i-1;L[0].key<L[j].key;--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; }}折半插入排序查找过程用折半查找方法。

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; if(L.r[0].key<L.r[m].key)high=m-1; elselow=m+1; }//while for(j=i-1;j<=high+1;--j)L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; }//for}//BInsertSort493865977613274902-路插入排序减少直接插入法的移动元素的个数，分成2路子有序序列 需要n个记录的辅助空间表插入排序：对静态链表作插入排序。希尔排序：缩小增量排序，属于插入排序算法思想：先将整个待排序记录分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再进行一次全体记录的插入排序。具体操作：49386597761327495504491338276549760413274955044938659776

1355387627046549

4997第一次分组49和13是有缘千里来相会！Yeah!是有规律的，专业的说法是“增量”!这就是第一趟排序结果第二趟的“增量”就要缩小了！Isee希尔排序算法:voidShellInsert(SqList&L,int

dk){//对顺序表L作一趟希尔排序。

for(i=dk+1;i<=L.length;++i) if(L.r[i].key<L.r[i-dk].key){ L.r[0]=L.r[i]; for(j=k-dkl;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]; }}//shelinsertvoidShellSort(SqList&L,int

dlta[],intt){//按增量序列dlta[0..t-1]对顺序表L作希尔排序

for(k=0;k<t;++k)ShellInsert(L,dlta[k]);}10.3快速排序冒泡排序：具体做法：依次比较第i个关键字和第i+1个关键字，大者排后，一趟得到最大值。（i=1,2,3,4,---n-1)493865977613274938496597761327493849657697132749384965761397274938496576132797

4938496576132749

97冒泡排序算法voidBubbleSort(SqList&L){ for(k=L.length-1;k>=1;k--) for(i=0;i<=k-1;k++) if(L.r[i].key>L.r[i+1].key){交换两个记录}}时间复杂度：O(n2)快速排序：思想：一趟排序将序列分成两个部分，前者小于某个值，后者大于某个值。之后再次分别快速排序。4938659776132749lowhigh27386597761349

49lowhigh2738139776496549lowhigh2738499776136549lowhigh273813497697

6549lowhigh4938659776132749lowhigh273865977613

49lowhigh2738139776

6549lowhigh2738

9776136549lowhigh273813

7697

6549lowhigh改进的算法快速排序算法：IntPartition(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;}//平均时间：K为常数因子。就平均时间而言快速排序是目前被认为最好的一种内部排序方法。10.4选择排序选择排序基本思想：每一趟在n-i+1(i=1,2,···,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。简单选择排序：VoidSelectSort(SqList&L){for(i=1;i<L.length;++i){ j=SelectMinKey(L,i);//从L.r[i..L.length]中选择key最小的记录

if(i!=j)L.r[i]L.r[j]; }}堆排序堆的定义：n个元素的序列{k1,k2,,kn}当且仅当满足下列关系时，称为堆：思想：每趟选取最小关键字、次小关键字、次次小关键字---。做法：建立一个完全二叉树，任何非终端结点的值均不大于其左、右孩子结点的值。输出堆顶，将其余的元素建立新的堆。ki≤k2iki≤k2i+1ki≥k2iki≥k2i+1493865977613274997493865271376494949386527137697493865497613279749381349766527974938

134976652797494938132765769749133827657697堆排序算法：voidHeapAdjust(HeaplType&H,ints,intm){//H.r[s..m]中记录的关键字处H.r[s].key外，均为堆，调整，使其成为堆。

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(!(rc.key<H.r[j].key))break;H.r[s]=H.r[j];s=j; }//forH.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);}}10.5归并排序思想：将两个或两个以上的有序表组合成一个新的有序表。具体做法：以两路归并示例[49][38][65][97][76][13][27]

n个记录看成n个有序的序列[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){ if(SR[i].key<=SR[j].key)TR[k]=SR[i++]; elseTR[k]=SR[j++]; } if(i<=m)TR[k..n]=S