《数据结构》排序》PPT课件.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语言描述的直接插入排序算法如下： typedef struct int key; /* 其他域 */ NODE; 算法9.1 直接插入排序算法。 void InsertSort (NODE array,int n) /* 对存放在数组array中，长度为n的序列排序 */ int i,j; NODE x; 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 希尔排序算法。 void ShellSort(NODE array,int n) /* 对存放在数组array中，长度为n的序列希尔排序 */ int i,j,step; NODE x; 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 冒泡排序算法。 void BubbleSort (NODE array,int n) /* 对存放在数组array中，长度为n的序列冒泡排序 */ int i,j,flag; NODE temp; 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.keymid.key 时，arrayj和arrayi交换，i增1。 (2)i从所指的位置开始从前向后扫描，直到 arrayj.keymid.key 时，arrayj和arrayi交换，j减1。 (3)重复(1),(2)，直到i=j结束，将arrayi=mid。这时序列以arrayi分为二个子序列。,例如，有一组关键字序列为49,38,65,97,76,13,38,50，其进行一趟划分的过程如图9.4(a)所示，整个序列快速排序过程如图9.4(b)。,算法9.4 快速排序算法。 void Quick_Sort(NODE array,int start,int end) /* 对从arraystart到arrayend的记录快速排序 */ int i,j; NODE mid; if(start=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 直接选择排序算法。 void Select_Sort(NODE array,int n) /* 对array中n个记录进行选择排序 */ int i,j,min; NODE temp; 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=k2i 2i=2i+1 2i+1=n 为在C语言中设计算法方便，修改堆定义为：若关键值序列为(k0,k1,kn-1)，满足如下条件： ki=k2i 2i+1=n ki=k2i+2 2i+2=n 称之为堆。,图9.6 堆的示例,一维数组看作是一棵完全二叉树的顺序存储形式。则堆是：完全二叉树中所有的非终端结点的关键字均不大于(或不小于)其左右孩子结点的关键字。,若在输出堆顶具有最小关键字值的记录之后，使得剩余n-1记录的序列重又建成一个堆，则得到n个记录中关键字次小值。如此反复执行，直到得到一个有序序列，这个过程称为堆排序。由此，实现堆排序需要解决两个问题： 如何将一个待排序序列建成一个堆？ 如何在输出堆顶记录之后，调整剩余记录成一个新堆?,关键字序列13,38,27,49,76,65,49,97是一个堆，如图9.7(a)所示，在输出堆顶记录之后，以堆中最后一个元素替代之，如图9.7(b)所示。此时，根结点的左、右子树均为堆，则仅需自上而下进行调整即可。首先以堆顶元素和其左、右子树根结点的较小值27比较，因堆顶元素97大，所以二者交换。交换之后又破坏右子树“堆”，则需要进行和上述相同的调整，直至树叶(如图9.7(c)所示)或调整后子树的“堆”没有被破坏结束。,图9.7 输出堆顶元素并调整建成新堆的过程,称这个自堆顶至树叶的调整过程为“筛选”,现在讨论第一个问题，即将一个待排序序列建成一个堆的过程，该过程就是一个反复“筛选”的过程。此时将序列看成一个完全二叉树，并且树最后一个非终端结点是序列的第trunc(n/2)个元素，在该元素开始到序列第一个元素的区间里，依次以每一个元素作为堆顶进行一次“筛选”，可将待排序序列建成一个堆。 例如，有一组关键字序列为 49,38,65,97,76,13,27,49， 将这8个关键字建成一个堆的过程如图9.8所示。,称这个自堆顶至树叶的调整过程为“筛选”,图9.8 将待排序列建成堆的过程,算法9.6 堆排序算法。 void heapshift(NODE array,int i,int n) /* 对以arrayi为顶的堆，进行筛选，n为待排序列长度 */ NODE temp=arrayi; int j=2*i+1; /* j为结点i左孩子的下标 */ while(jarrayj+1.key) j+; /* j为结点i左右孩子中较小者的下标 */ if(temp.keyarrayj.key) arrayi=arrayj; i=j; j=2*i+1; else break; /* 筛选结束 */ arrayi=temp; /* arrayi是temp应在的位置 */ 未完结下一页,void heapsort(NODE array,int n) /* 对存放在array中，长度为n的序列进行对排序 */ int i; NODE temp; for(i=n/2-1;i=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)，它是一种不稳定的