数据结构第10章-排序

数据结构第10章内部排序信息工程学院衷璐洁概述插入排序快速排序选择排序归并排序基数排序各种内部排序方法的比较讨论本讲主要内容一、排序的定义

假设含n个记录的序列为{R1,R2,…,Rn}其相应的关键字序列为{K1,K2,…,Kn}需确定1,2,…,n的一种排列p1,p2,…,pn，使其相应的关键字满足如下的非递减(或非递增)关系：

Kp1

≤

Kp2≤

…≤

Kpn即使序列{R1,R2,…,Rn}成为一个按关键字有序的序列{Rp1,Rp2,…,Rpn}这样一种操作称为排序

关键字Ki可以是记录Ri的主关键字【排序结果唯一】、次关键字或若干数据项的组合【排序结果不唯一】假设：(1)在待排序序列中存在两个(以上)关键字相等的记录Ri和Rj，即：Ki=Kj

(1≤i,j≤n，i≠j)

(2)在排序前的序列中Ri领先于Rj

(即：i<j)那么：若排序后Ri仍领先于Rj

，则称所用的排序方法是稳定的；否则，称所用的排序方法是不稳定的

【对不稳定的排序方法，只需举出一组关键字实例说明其不稳定性即可】二、排序方法的稳定性

按排序过程中涉及存储器的不同，可将排序方法分为两大类：内部排序：待排序记录存放在计算机随机存储器(内存)中进行的排序过程外部排序：待排序记录的数量很大，内存一次不能容纳全部记录，还需外存辅助的排序过程三、排序的分类按排序过程中依据的不同原则大致可分为：按内部排序过程所需的工作量分：插入排序交换排序选择排序归并排序基数排序(1)简单的排序方法——O(n2)(2)先进的排序方法——O(nlog2n)(3)基数排序——O(d·n)四、内部排序方法(1)比较：比较两个关键字的大小大多数排序都需要(2)移动：将记录从一个位置移到另一个位置可通过改变记录的存储方式避免五、大多数排序的两种基本操作排序时必须移动记录(2)静态链表存储——(链)表排序排序时不移动记录，仅需修改指针(3)顺序存储＋地址向量＝地址排序排序时不移动记录，而是移动地址向量中的“地址”排序结束后再按地址向量中的值调整记录的存储位置六、排序记录的存储方式(1)顺序存储待排记录的数据类型：#defineMAXSIZE20//顺序表的最大长度typedefintKeyType;//关键字类型typedefstruct{

KeyType

key;//关键字InfoTypeotherinfo;//其它数据项}RedType;//记录类型typedefstruct{

RedType

r[MAXSIZE+1];//r[0]闲置或用作哨兵单元intlength;//顺序表长度}SqList;//顺序表类型概述插入排序快速排序选择排序归并排序基数排序各种内部排序方法的比较讨论本讲主要内容一、直接插入排序方法：将一个记录插入到已排好序的有序表中，得到一个新的、记录数增1的有序表：（1）把序列(R(K1))看成是一个有序的子序列把R(K2)插入到该序列中,使插入后序列(R(K1),R(K2))有序（2）把R(K3)插入到(R(K1),R(K2))中，使插入后有序（3）重复（2），直到插入R(Kn)为止。10.2插入排序49，38，65，97，76，13，2749384938496538496597384965769713384965769713273849657697//对顺序表L作直接插入排序的算法voidInsertSort(SqList&L){//算法10.1for(i=2;i<=L.length;++i)

//"<"时，需将L.r[i]插入有序子表

if(LT(L.r[i].key,L.r[i-1].key)){

L.r[0]=L.r[i];//复制为哨兵

for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];

//记录后移

L.r[j+1]=L.r[0];

//插入到正确位置}}//InsertSort[576489]6某趟插入排序:复制为哨兵j89j64j7j6i直接插入排序的时间复杂度：O(n2)二、其它插入排序直接插入排序适合待排序数量n很小的情况，若n很大，则不宜采用为此，从减少“比较”和“移动”这两种操作的次数考虑，可有以下几种排序的方法：(1)折半插入排序(2)2-路插入排序(3)表插入排序(4)希尔排序(1)折半插入排序做法：用折半查找的方法找到插入位置

例：在序列{13，27，35，48，65，72}中插入20或603565132748722060//对顺序表L作折半插入排序voidBInsertSort(SqList&L){//算法10.2for(i=2;i<=L.length;++i){

L.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]low=1;high=i-1;while(low<=high){//在r[low..high]中折半查找有序插入的位置

m=(low+high)/2;//折半

if(LT(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];

//插入}}//BInsertSort[576489]246将L.r[i]暂存于L.r[0]89647low6mhigh折半插入排序的时间复杂度：O(n2)low(2)希尔排序又称“缩小增量排序”(DiminishingIncrementSort)希尔排序的基本思想：(1)先将整个待排记录序列分割成若干子序列(2)分别对这些子序列进行直接插入排序(3)待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序增量序列为：5，3，149

38

65

977613

27

4913

27

49

977649

386513

27

49

97

76

49

386513

27

49

38

65

49

97761327384949657697/*对顺序表L作一趟希尔插入排序。本算法对算法10.1作了以下修改：1.前后记录位置的增量是dk，而不是1；2.r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到*/voidShellInsert(SqList&L,intdk){//算法10.4for(i=dk+1;i<=L.length;++i)

//需将L.r[i]插入有序增量子表if(LT(L.r[i].key,L.r[i-dk].key)){

L.r[0]=L.r[i];//暂存在L.r[0]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];//插入}}//ShellInsert/*按增量序列dlta[0..t-1]对顺序表L作希尔排序*/voidShellSort(SqList&L,intdlta[],intt){//算法10.5

for(k=0;k<t;++k)ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序}//ShellSort希尔排序的时间是所取“增量”序列的函数，涉及一些数学上的尚未解决的难题概述插入排序快速排序选择排序归并排序基数排序各种内部排序方法的比较讨论本讲主要内容快速排序是一种借助“交换”进行排序的方法10.3快速排序一、起泡排序（BubbleSort)一趟排序voidBubbleSort(SqList&L){for(i=1;i<n;i++){change=FALSE;for(j=1;j<n-i+1;j++)if(L.r[j].key>L.r[j+1].key){change=TRUE;L.r[j]L.r[j+1];}

if(!change)return;}}共进行n-1趟排序，共进行n(n-1)/2次比较T(n)=O(n2)快速排序是对起泡排序的一种改进基本思想：通过一趟排序将待排记录分割成独立的两部分一部分记录的关键字均比另一部分记录的关键字小则再分别对这两部分的记录继续进行排序最后达到整个序列有序二、快速排序（QuickSort)假设待排序序列为{L.r[s]，L.r[s+1]，…，L.r[t]}首先任意选取一个记录(一般为第一个记录L.r[s])作为枢轴(或支点)(pivot)然后按下述原则重新排列其余记录：将所有关键字比它小的记录都安置在枢轴之前将所有关键字比它大的记录都安置在枢轴之后由此，以该“枢轴”记录最后所落的位置i作分界线，将序列{L.r[s]，L.r[s+1]，…，L.r[t]}分割成两个子序列：{L.r[s]，L.r[s+1]，…，L.r[i-1]}和{L.r[i+1]，L.r[i+2]，…，L.r[t]}这个过程称作一趟快速排序(或一次划分)4938659776132749i27386597761349

492738499776136549jiiijjijj2738139776496549iji2738134976976549ij27381376976549jj具体实现：

low=s;high=t;pivotkey=L.r[low].key;(1)从high开始往前找第一个关键字小于pivotkey的记录，与枢轴记录交换

(2)从low开始往后找第一个关键字大于pivotkey的记录，与枢轴记录交换

(3)重复（1）（2）直到low==high为止此时枢轴记录所在的位置i=low=high273813497697654913

27

384965

76

97/*算法10.6(a)交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位，并返回其所在位置，此时在它之前(后)的记录均不大(小)于它*/每交换一对记录需进行3次记录移动(赋值)操作！但对枢轴记录的赋值是多余的！只有在一趟排序结束low=high的位置才是枢轴的最后位置，改写该算法！intPartition(SqList&L,intlow,inthigh){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[low]←→L.r[high];//将比枢轴记录大的记录交换到高端}returnlow;//返回枢轴位置}//Partition//改进后的算法10.6(b)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;//返回枢轴位置}//Partition//对顺序表L作快速排序//递归形式的快速排序算法//对顺序表L的子序列L.r[low..high]作快速排序voidQSort(SqList&L,intlow,inthigh){if(low<high){

//长度大于1

//将L.r[low..high]一分为二

pivotloc=Partition(L,low,high);//pivotloc是枢轴位置

QSort(L,low,pivotloc-1);//对低子表递归排序

QSort(L,pivotloc+1,high);//对高子表递归排序

}}//QSortvoidQuickSort(SqList&L){

QSort(L,1,L.length);}//QuickSortT(n)=O(nlog2n)快速排序的平均时间为Tavg=knlnn其中：n为待排序序列中记录的个数，k为某个常数就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法但是：若初始记录序列按关键字有序或基本有序时，快速排序蜕化为起泡排序，其时间复杂度为O(n2)从空间上看：之前讨论的各种方法，除2-路插入排序外，都只需要一个记录的附加空间，但快速排序需要一个栈空间来实现递归。概述插入排序快速排序选择排序归并排序基数排序各种内部排序方法的比较讨论本讲主要内容10.4选择排序251608254921490816252521212525160849162108一、简单选择排序（SelectSort)2516082549214925012345081625212549252116082525//对顺序表L作简单选择排序voidSelectSort(SqList&L){for(i=1;i<L.length;++i){//选择第i小的记录，并交换到位j=SelectMinKey(L,i);//在L.r[i..L.length]中选择key最小的记录if(i!=j)L.r[i]←→L.r[j];//与第i个记录交换}}//SelectSortintSelectMinKey(SqListL,intk){//在L.r[k..L.length]中选择key最小的记录并返回它的位置

min=L.r[k].key;minp=k;for(i=k+1;i<=L.length;i++)if(L.r[i].key<min){min=L.r[i].key;minp=i;}returnminp;}共进行n-1趟排序，n(n-1)/2次比较时间复杂度O(n2)TreeSelectionSort，又称锦标赛排序(TournamentSort)该过程可用一棵有n个叶子结点的完全二叉树表示

将叶子结点中最小关键字改为MAXINT，然后该叶子与其左/右兄弟关键字比较依次修改从叶子到根的路径上各结点的关键字值则根结点为次小记录不断重复，直到叶子结点均为MAXINT为止。是一种按锦标赛的思想进行排序的方法首先对n个记录的关键字进行两两比较然后在其中个较小者之间再进行两两比较如此重复，直至选出最小关键字的记录为止二、树形选择排序082108086325212125492516086395a[0]a[1]1621161663252121254925166395a[2]212163632521212549256395a[3]2525636325252549256395a[4]252563632549256395a[5]4949636349496395a[6]6363636395a[7]95959595堆定义如下：

n个元素的序列{k1,k2,…,kn}当且仅当满足如下关系时，称之为堆ki≤k2i（或ki≥k2i）ki≤k2i+1（或ki≥k2i+1）

i=1,2,…,三、堆排序（HeapSort)

若用一个一维数组存放满足此关系的序列，把这个一维数组看成是一棵完全二叉树，则堆对应的完全二叉树中所有非终端结点的值均大于或均小于其左右孩子的值。小顶堆大顶堆大顶堆/大根堆堆排序（从小到大）方法：（1）由一个无序的序列建成一个堆（2）输出堆顶的最小值（3）剩余的元素建成一个新的堆（4）重复（2）（3）093811962783小顶堆/小根堆30854712243691534938659776132749输出13后,用序列中最后一个记录代替根结点筛选为小顶堆堆顶元素与它的左右子树根结点比较：（1）若右子树根<左子树根<堆顶根结点与右子树根交换（2）若左子树根<右子树根<堆顶根结点与左子树根交换这个调整过程称为筛选1338497697276549973849762765492738497649659749386597761327497627496538974913496538977649659749273813对一个无序序列建立堆也是筛选过程,筛选从第个记录开始（1）初建堆首先将序列表示成完全二叉树的形式从第个记录开始调整，假设要建大顶堆4997657649273813初建堆（大顶堆）完成499765764927381349386576492797134976654938279713（2）堆排序重新调整成堆第1趟堆排序完成将堆顶与序列中未排序的最后一个元素互换497665493827971349276549387697134965274938769713第2趟堆排序完成将堆顶与序列中未排序的最后一个元素互换重新调整成堆496527493876971349132749387697651349274938769765第3趟堆排序完成将堆顶与序列中未排序的最后一个元素互换重新调整成堆134927493876976549132749387697654949273813769765第4趟堆排序完成重新调整成堆将堆顶与序列中未排序的最后一个元素互换494927381376976549132738497697654938271349769765第5趟堆排序完成重新调整成堆将堆顶与序列中未排序的最后一个元素互换493827134976976549273813497697654913382749769765建大顶堆，排序结果为从小到大将堆顶与序列中未排序的最后一个元素互换无调整，第6趟堆排序完成无调整，第7趟堆排序完成/*已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数调整H.r[s]的关键字，使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言)*/typedefSqListHeapType;voidHeapAdjust(HeapType&H,ints,intm){rc=H.r[s];

for(j=2*s;j<=m;j*=2){//沿key较大的孩子结点向下筛选//j为key较大的记录的下标if(j<m&<(H.r[j].key,H.r[j+1].key))++j;if(!LT(rc.key,H.r[j].key))break;//rc应插入在位置s上H.r[s]=H.r[j];s=j;}H.r[s]=rc;//插入}//HeapAdjust从下标s处开始调整左侧“底座”j记住的是两个“底座”中值较大的那一个的下标如果rc大于H.r[j].key，那么无需调整（大顶堆），直接退出循环把H.r[j]放到H.r[s]中；s下移到j处，准备下一次可能的调整最终rc所放的位置/*对顺序表H进行堆排序*/voidHeapSort(HeapType&H){

for(i=H.length/2;i>0;--i)

//把H.r[1..H.length]建成大顶堆

HeapAdjust(H,i,H.length);

//将堆顶记录和当前未经排序子序列Hr[1..i]中最后一个记录相互交换for(i=H.length;i>1;--i)

{

H.r[1]←→H.r[i];

HeapAdjust(H,1,i-1);//将H.r[1..i-1]重新调整为大顶堆}}//HeapSort时间复杂度O(nlog2n)概述插入排序快速排序选择排序归并排序基数排序各种内部排序方法的比较讨论本讲主要内容10.5归并排序（MergingSort）将两个或两个以上的有序表组合成一个新的有序表2路归并：把初始含有n个记录的序列看成n个长度为1的有序子序列,采用两两合并的方法最终合并成一个序列21252593627208371654492521254962930872163754082125

254962729316375408162125

253749546272932125

254908627293163754//算法10.12将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){//将SR中记录由小到大地并入TRfor(j=m+1,k=i;i<=m&&j<=n;++k){if(LQ(SR[i].key,SR[j].key))TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=SR[i..m];//将剩余的SR[i..m]复制到TRif(j<=n)TR[k..n]=SR[j..n];//将剩余的SR[j..n]复制到TR}//Merge时间复杂度：O(nlog2n)//递归算法：将SR[s..t]归并排序为TR1[s..t]voidMSort(RcdTypeSR[],RcdType&TR1[],ints,intt){

if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//将SR[s..t]平分为SR[s..m]和SR[m+1,t]

MSort(SR,TR2,s,m);//递归地将SR[s..m]归并为有序的TR2[s..m]

MSort(SR,TR2,m+1,t);//递归地将SR[m+1..t]归并为有序的TR2[m+1..t]

Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]}}//MSort//对顺序表L作归并排序voidMergeSort(SqList&L){

MSort(L.r,L.r,1,L.length);}//MergeSort概述插入排序快速排序选择排序归并排序基数排序各种内部排序方法的比较讨论本讲主要内容与前述方法完全不同的一种排序方法！前面的排序方法主要通过关键字间的比较和移动记录来实现的！基数排序不需要进行关键字间的比较，它是一种借助多关键字的排序思想对单逻辑关键字进行排序的方法10.6基数排序（RadixSorting）最高位优先法MSD：先按关键字K0排序，将序列分成若干个子序列每个子序列记录的K0均相等然后在每个子序列中按K1排序按K1值把子序列分成更小的子序列

……………

直到最后按Kd-1排序后，整个序列有序一、多关键字排序(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(1,3),(2,4),(2,3),(3,2),(3,4),(4,4),(4,3)(1,1),(3,2),(1,3),(2,3),(4,3),(2,4),(3,4),(4,4)最低位优先法LSD：根据最次关键字Kd-1起对记录排序再根据Kd-2对记录排序。。。。。。根据K0对记录排序后，

整个序列有序(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(3,2),(1,3),(2,3),(4,3),(2,4),(4,4),(3,4)(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4)二、链式基数排序用分配和收集两种操作对单关键字进行排序某些单关键字可以看成是若干个关键字复合而成,如多位数可以看成是由多个数字复合而成的。“分配”：

按关键字把不同的记录送到不同的队列中“收集”：

按某种顺序把不同队列中的记录集中起来614921485637738101