搜索
第9章排序9.1插入排序9.2交换排序9.3选择排序9.4归并排序习题•排序是针对记录的集合{R1,R2,…,Rn}，其相应的关键字序列为{K1,K2,…,Kn}，重组记录之间的关系，使记录的排列次序满足相应的关键字的递增或递减关系。记录的集合也称为待排序序列。若待排序序列完全存放在内存中，则该排序称为内部排序；若由于数据集合太大，在排序过程中，需对外存进行访问，则该排序称为外部排序。•有如下一组待排序序列(每个记录只列出关键字一项)：53,25,67(1),46,29,67(2),89,43,67(3),76括号里的数字代表等值记录的位置，若排序后为：25,29,43,46,53,67(1),67(2),67(3),76,89则称所用的排序方法是稳定的，反之，若三个等值记录的排列顺序不是上述顺序，就称所用排序的方法是不稳定的。9.1插入排序9.1.1直接插入排序它的基本操作是在处理第i个记录时，前面1到i-1记录已排成有序，将第i个记录插入有序表中，得到一个新的有序表，表的长度加1。当表中只有一个记录时，该表已是有序表，所以，可以从第二个记录开始，逐个插入记录，直至处理完待排序序列的所有记录。直接插入排序的时间复杂度为O(n2)，并且是一种稳定排序。当n较小时，排序的效率较高，是一种常用的排序方法处理记录号插入位置下标0123456i=1j=0[91]673562297246i=2j=0[6791]3562297246i=3j=0[356791]62297246i=4j=1[35626791]297246i=5j=0[2935626791]7246i=6j=4[293562677291]46i=7j=2[29354662677291]图9.1直接插入排序示例例如，有一组关键字序列为{91,67,35,62,29,72,46}，直接插入排序过程如图9.1所示。用C语言描述的直接插入排序算法如下：typedefstruct{intkey;…/*其他域*/}NODE;算法9.1直接插入排序算法。voidInsertSort(NODEarray[],intn)/*对存放在数组array[]中，长度为n的序列排序*/{inti,j;NODEx;for(i=1;in;i++){x=array[i];j=i-1;while(j=0&&x.keyarray[j].key){array[j+1]=array[j];j--;}array[j+1]=x;}}9.1.2希尔排序希尔排序是一种步长递减的插入排序，又称为“缩小增量排序”。该排序方法是，将直接插入分成插入步长由大到小不同的若干趟来进行。初始，步长较大，相当于把待排记录序列分成若干子序列，各子序列中记录的间隔为步长距离，由于子序列的长度小，所以子序列的插入排序的效率较高。以后各趟逐步减小步长，随着步长的减小，子序列的长度在增加，但子序列中包含了上一趟经过大的步长插入排序的结点，因此，已有部分结点有序，这样，在排序中记录移动的次数就少，排序的效率也就高。最后一趟是步长为1，即：对整个序列直接插入排序，但这时整个序列已基本有序，只要做少量记录移动，就可将该序列排成有序。图9.2希尔排序示例例如，有8个关键字序列为{91,67,35,62,29,72,46,57}，插入排序的步长序列为4,2,1。希尔插入排序过程如图9.2。步长序列的选择没有严格的规定，只要该序列{d1,d2,…,dt}满足d1d2…dt，并且当t≥1时，d1=1，该序列都可选作步长序列。一般采用步长序列为d1=n/2，di+1=di/2(n为待排序序列的长度)。用C语言描述的希尔排序算法如下：算法9.2希尔排序算法。voidShellSort(NODEarray[],intn)/*对存放在数组array[]中，长度为n的序列希尔排序*/{inti,j,step;NODEx;for(step=n/2;step0;step=step/2)/*step不断变小，直至为1*/{for(i=step;in;i++){x=array[i];j=i-step;while(j=0&&x.keyarray[j].key){array[j+step]=array[j];j=j-step;}array[j+step]=x;}}}希尔排序的分析是一个复杂的问题，但它的排序速度要比直接插入排序快，另外，它是一种不稳定排序9.2交换排序交换排序基本思想：比较二个待排序记录的关键字，若为逆序，则交换位置，反之，保持原序。9.2.1冒泡(简单交换排序)冒泡排序的方法是：首先比较array[n-1].key和array[n-2].key，若为逆序则交换之，然后比较array[n-2].key和array[n-3].key，依此类推，直到比较array[1].key和array[0].key，称为一趟“冒泡”，其结果是将具有最小关键字的记录排到序列的第1个位置上。然后再array[n-1]到array[1]之间进行一趟“冒泡”，将具有次小关键字的记录排到序列的第2个位置上。依此类推，直到第n-1趟，在array[n-1]和array[n-2]之间进行“冒泡”后，待排序序列已排成有序。下一趟区间下标0123456初始关键字[6，0][91673562297246]第一趟冒泡后[6，1]29[916735624672]第二趟冒泡后[6，2]2935[9167466272]第三趟冒泡后[6，3]293546[91676272]第四趟冒泡后[6，4]29354662[916772]第五趟冒泡后[6，5]2935466267[9172]第六趟冒泡后序列有序29354662677291图9.3冒泡排序示例例如，有一组关键字序列为{91,67,35,62,29,72,46}，冒泡排序过程如图9.3所示。用C语言描述的简单交换排序算法如下：算法9.3冒泡排序算法。voidBubbleSort(NODEarray[],intn)/*对存放在数组array[]中，长度为n的序列冒泡排序*/{inti,j,flag;NODEtemp;for(i=0;in-1;i++){flag=0;/*避免无交换的排序趟*/for(j=n-1;ji;j--)/*从后向前比较，小数向前交换，最小值到前位*/if(array[j].keyarray[j-1].key){temp=array[j];array[j]=array[j-1];array[j-1]=temp;flag=1;/*有逆序存在，flag为1*/}if(flag==0)break;/*若一趟“冒泡”中没有逆序，则序列已有序*/}}冒泡排序的时间复杂度为O(n2)，并且是一种稳定排序。9.2.2快速排序冒泡排序的一种改进。基本思想是：通过一趟排序后，大幅度减小排序序列的长度。在一趟排序后将某个记录根据其关键字，排到序列的中间位置，且左边所有记录的关键字都比它的关键字小，而右边所有记录的关键字都比它的关键字大，这样一趟排序后，不仅有一个记录已排到正确的位置上，如下标为i，而且待排序序列分裂成长度较小的两个待排序区间(array[0]到array[i-1]和array[i+1]到array[n-1])，将上述过程称为“划分”。一次划分得到两个小序列，再递归地对这两个小序列进行划分，直到序列的长度为1，这时待排序序列已排成有序。显然，一次划分的时间复杂度是O(n)，下面讨论划分的算法。对array[start]到array[end]序列进行划分，首先要确定一个划分标准，通常选取序列的第一个记录的关键字，用变量mid暂存，另附设两个指针i和j，其初值分别为start和end，划分的具体做法如下(i=start，j=end)：(1)j从所指的位置开始从后向前扫描，直到array[j].keymid.key时，array[j]和array[i]交换，i增1。(2)i从所指的位置开始从前向后扫描，直到array[j].key≥mid.key时，array[j]和array[i]交换，j减1。(3)重复(1),(2)，直到i=j结束，将array[i]=mid。这时序列以array[i]分为二个子序列。例如，有一组关键字序列为{49,38,65,97,76,13,38,50}，其进行一趟划分的过程如图9.4(a)所示，整个序列快速排序过程如图9.4(b)。下标01234567初始关键字4938659776133850i↑↑j←↑j第1次交换之后38386597761350i↑----→i↑↑j第2次交换之后38389776136550i↑↑j←↑j第3次交换之后38381397766550i↑→i↑↑j第4次交换之后38381376976550i↑↑j←---↑j完成一趟划分3838134976976549(a)一趟划分过程初始状态[4938659776132750]一次划分后[383813]49[76976550]分别进行划分[13]38[38]49[76976550]结束结束[5065]76[97]50[65]结束结束有序序列[1338384950657697](b)快速排序的全过程图9.4快速排序示例算法9.4快速排序算法。voidQuick_Sort(NODEarray[],intstart,intend)/*对从array[start]到array[end]的记录快速排序*/{inti,j;NODEmid;if(start=end)return;/*仅有一个记录*/i=start;j=end;mid=array[i];while(ij){while(ij&&array[j].keymid.key)j--;if(ij){array[i]=array[j];i++;}while(ij&&array[i].key=mid.key)i++;if(ij){array[j]=array[i];j--;}}array[i]=mid;/*一趟划分结束*/Quick_Sort(array,start,i-1);/*对start到i-1的记录进行划分*/Quick_Sort(array,i+1,end);/*对i+1到end的记录进行划分*/}平均时间复杂度为O(nlog2n)，最坏这时快速排序等同于冒泡排序，时间复杂度为O(n2)。快速排序是不稳定的排序。9.3选择排序选择排序的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)个记录中选关键字最小的记录作为有序序列中第i个记录。9.3.1直接选择排序直接选择排序又称为简单选择排序，其算法是：对n个记录排序，依次选出n-1个极值，置于相应目标位置。对array[0]到array[n-1]排序，需进行n-1趟扫描，第i趟扫描是从array[i]到array[n-1]中，经过n-i次比较，选出关键字最小的元素，置于array[i]位置中。算法9.5直接选择排序算法。voidSelect_Sort(NODEarray[],intn)/*对array[]中n个记录进行选择排序*/{inti,j,min;NODEtemp;for(i=0;in-1;i++){min=i;/*设min为第i趟中最小关键值记录的下标*/for(j=i+1;jn;j++)if(array[j].keyarray[min].key)min=j;/*找最小关键值的下标*/if(i!=min){temp=array[i];array[i]=array[min];array[min]=temp;}}}直接选择排序算法的时间复杂度为O(n2)，它是一个不稳定排序。9.3.2树形选择排序(1)简单树形选择排序简单树形选择排序的方法是：首先对待排序序列中n个记录的关键字进行两两比较，将其中关键字较小的n/2个记录取出，然后将这n/2个关键字再进行两两比较，选择出具有较小关键字的记录，如此重复，直到选出一个最小关键字的记录。这个过程可用一棵有n个叶子结点的完全二叉树表示。有一组关键字序列为