《数据结构》排序》（课堂PPT）

第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较小时，排序的效率较高，是一种常用的排序方法,例如，有一组关键字序列为91,67,35,62,29,72,46，直接插入排序过程如图9.1所示。,用C语言描述的直接插入排序算法如下：typedefstructintkey;/*其他域*/NODE;算法9.1直接插入排序算法。voidInsertSort(NODEarray,intn)/*对存放在数组array中，长度为n的序列排序*/inti,j;NODEx;for(i=1;i=0,9.1.2希尔排序希尔排序是一种步长递减的插入排序，又称为“缩小增量排序”。该排序方法是，将直接插入分成插入步长由大到小不同的若干趟来进行。初始，步长较大，相当于把待排记录序列分成若干子序列，各子序列中记录的间隔为步长距离，由于子序列的长度小，所以子序列的插入排序的效率较高。以后各趟逐步减小步长，随着步长的减小，子序列的长度在增加，但子序列中包含了上一趟经过大的步长插入排序的结点，因此，已有部分结点有序，这样，在排序中记录移动的次数就少，排序的效率也就高。最后一趟是步长为1，即：对整个序列直接插入排序，但这时整个序列已基本有序，只要做少量记录移动，就可将该序列排成有序。,图9.2希尔排序示例,例如，有8个关键字序列为91,67,35,62,29,72,46,57，插入排序的步长序列为4,2,1。希尔插入排序过程如图9.2。,步长序列的选择没有严格的规定，只要该序列d1,d2,dt满足d1d2dt，并且当t1时，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;i=0,希尔排序的分析是一个复杂的问题，但它的排序速度要比直接插入排序快，另外，它是一种不稳定排序,9.2交换排序,交换排序基本思想：比较二个待排序记录的关键字，若为逆序，则交换位置，反之，保持原序。,9.2.1冒泡(简单交换排序)冒泡排序的方法是：首先比较arrayn-1.key和arrayn-2.key，若为逆序则交换之，然后比较arrayn-2.key和arrayn-3.key，依此类推，直到比较array1.key和array0.key，称为一趟“冒泡”，其结果是将具有最小关键字的记录排到序列的第1个位置上。然后再arrayn-1到array1之间进行一趟“冒泡”，将具有次小关键字的记录排到序列的第2个位置上。依此类推，直到第n-1趟，在arrayn-1和arrayn-2之间进行“冒泡”后，待排序序列已排成有序。,例如，有一组关键字序列为91,67,35,62,29,72,46，冒泡排序过程如图9.3所示。,用C语言描述的简单交换排序算法如下：算法9.3冒泡排序算法。voidBubbleSort(NODEarray,intn)/*对存放在数组array中，长度为n的序列冒泡排序*/inti,j,flag;NODEtemp;for(i=0;ii;j-)/*从后向前比较，小数向前交换，最小值到前位*/if(arrayj.keyarrayj-1.key)temp=arrayj;arrayj=arrayj-1;arrayj-1=temp;flag=1;/*有逆序存在，flag为1*/if(flag=0)break;/*若一趟“冒泡”中没有逆序，则序列已有序*/,冒泡排序的时间复杂度为O(n2)，并且是一种稳定排序。,9.2.2快速排序冒泡排序的一种改进。基本思想是：通过一趟排序后，大幅度减小排序序列的长度。在一趟排序后将某个记录根据其关键字，排到序列的中间位置，且左边所有记录的关键字都比它的关键字小，而右边所有记录的关键字都比它的关键字大，这样一趟排序后，不仅有一个记录已排到正确的位置上，如下标为i，而且待排序序列分裂成长度较小的两个待排序区间(array0到arrayi-1和arrayi+1到arrayn-1)，将上述过程称为“划分”。一次划分得到两个小序列，再递归地对这两个小序列进行划分，直到序列的长度为1，这时待排序序列已排成有序。显然，一次划分的时间复杂度是O(n)，下面讨论划分的算法。,对arraystart到arrayend序列进行划分，首先要确定一个划分标准，通常选取序列的第一个记录的关键字，用变量mid暂存，另附设两个指针i和j，其初值分别为start和end，划分的具体做法如下(i=start，j=end)：(1)j从所指的位置开始从后向前扫描，直到arrayj.key=end)return;/*仅有一个记录*/i=start;j=end;mid=arrayi;while(imid.key)j-;if(ij)arrayi=arrayj;i+;while(ij/*对i+1到end的记录进行划分*/,平均时间复杂度为O(nlog2n)，最坏这时快速排序等同于冒泡排序，时间复杂度为O(n2)。快速排序是不稳定的排序。,9.3选择排序,选择排序的基本思想是：每一趟在n-i+1(i=1,2,n-1)个记录中选关键字最小的记录作为有序序列中第i个记录。,9.3.1直接选择排序直接选择排序又称为简单选择排序，其算法是：对n个记录排序，依次选出n-1个极值，置于相应目标位置。对array0到arrayn-1排序，需进行n-1趟扫描，第i趟扫描是从arrayi到arrayn-1中，经过n-i次比较，选出关键字最小的元素，置于arrayi位置中。,算法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(arrayj.keyarraymin.key)min=j;/*找最小关键值的下标*/if(i!=min)temp=arrayi;arrayi=arraymin;arraymin=temp;,直接选择排序算法的时间复杂度为O(n2)，它是一个不稳定排序。,9.3.2树形选择排序(1)简单树形选择排序简单树形选择排序的方法是：首先对待排序序列中n个记录的关键字进行两两比较，将其中关键字较小的n/2个记录取出，然后将这n/2个关键字再进行两两比较，选择出具有较小关键字的记录，如此重复，直到选出一个最小关键字的记录。这个过程可用一棵有n个叶子结点的完全二叉树表示。,有一组关键字序列为49,38,65,97,76,13,27,49，在这8个关键字中选出最小关键字的过程如图9.5(a)所示。在输出最小关键字后，仅需将叶子结点中最小关键字(13)改为“最大值”，然后调整从树叶到根结点的路径上各结点的关键字，则根结点的关键字为次小关键字，如图9.5(b)所示。同理，可依次选出从小到大的所有关键字。,图9.5树形选择排序的示例,时间复杂度:O(nlog2n)缺点:是占用较多的存储空间来保存比较结果。,(2)堆排序堆的定义：有n个记录的线性序列，其关键值序列为(k1,k2,kn)，满足如下条件：ki=k2i2i=2i+12i+1=n为在C语言中设计算法方便，修改堆定义为：若关键值序列为(k0,k1,kn-1)，满足如下条件：ki=k2i2i+1=nki=0;i-)heapshift(array,i,n);/*以每一个非终端结点为堆顶，筛选建立堆*/for(i=n-1;i0;i-)temp=array0;array0=ai;ai=temp;/*将最小值交换至数组末尾*/*从array0开始在array0到arrayi-1之间筛选*/heapshift(a,0,i);堆排序的时间复杂度O(nlog2n)，它是一种不稳定的排序方法。,9.4归并排序,归并是将两个有序序列归并为一个有序序列。将2-路归并的思想用于有n个记录的待排序列中，就得到归并排序。首先，把n个记录看成是长度为1