《数据结构》排序》PPT课件

1、第第9章章 排序排序9.1插入排序插入排序 9.2交换排序交换排序 9.3选择排序选择排序 9.4归并排序归并排序 习题习题 排序是针对记录的集合排序是针对记录的集合R1,R2,Rn，其相应的关键字，其相应的关键字序列为序列为K1,K2,Kn，重组记录之间的关系，使，重组记录之间的关系，使记录的记录的排列次序满足相应的排列次序满足相应的关键字关键字的的递增递增或或递减递减关系。记录的集关系。记录的集合也称为待排序合也称为待排序序列序列。若待排序。若待排序序列序列完全存放完全存放在内存在内存中，中，则该排序称为则该排序称为内部排序内部排序；若由于；若由于数据数据集合太大，在排序过集合太大，在排序

2、过程中，需对程中，需对外存外存进行访问，则该排序称为进行访问，则该排序称为外部排序外部排序。 有如下一组待排序序列有如下一组待排序序列(每个记录只列出关键字一项每个记录只列出关键字一项)： 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 则称所用的则称所用的排序方法排序方法是是稳定稳定的，反之，若三个等值记录的的，反之，若三个等值记录的排列顺序不是上述顺序，就称所用排序的方法是不稳定的排列顺序不是上

3、述顺序，就称所用排序的方法是不稳定的。9.1 插入排序插入排序9.1.1 直接插入排序直接插入排序 它的基本操作是在处理第i个记录时，前面1到i-1记录已排成有序，将第i个记录插入有序表中，得到一个新的有序表，表的长度加1。当表中只有一个记录时，该表已是有序表，所以，可以从第二个记录开始，逐个插入记录，直至处理完待排序序列的所有记录。 直接插入排序的时间复杂度为O(n2)，并且是一种稳定排序。当n较小时，排序的效率较高，是一种常用的排序方法 处理记录号 插入位置下标 0 1 2 3 4 5 6 i=1 j=091 67 35 62 29 72 46 i=2 j=067 91 35 62 29

4、72 46 i=3 j=035 67 91 62 29 72 46 i=4 j=135 62 67 91 29 72 46 i=5 j=029 35 62 67 91 72 46 i=6 j=429 35 62 67 72 91 46 i=7 j=229 35 46 62 67 72 91 图9.1 直接插入排序示例 例如，有一组关键字序列为91,67,35,62,29,72,46，直接插入排序过程如图9.1所示。用C语言描述的直接插入排序算法如下： typedef struct int key; /* 其他域 */ NODE; 算法算法9.1 直接插入排序算法。 void InsertSor

5、t (NODE array,int n) /* 对存放在数组array中，长度为n的序列排序 */ int i,j; NODE x; for(i=1;i=0 & x.keyd2dt，并且当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

6、=step/2) /* step不断变小，直至为1 */ for(i=step; i=0 & x.keyarrayj.key) arrayj+step=arrayj; j=j-step; arrayj+step=x; 希尔排序的分析是一个复杂的问题，但它的排序速度要比直接插入排序快，另外，它是一种不稳定排序 9.2 交换排序交换排序 交换排序基本思想：比较二个待排序记录的关键字，若为逆序，则交换位置，反之，保持原序。9.2.1 冒泡冒泡(简单交换排序简单交换排序) 冒泡排序的方法是：首先比较arrayn-1.key和arrayn-2. key，若为逆序则交换之，然后比较arrayn-2

7、.key和arrayn-3.key，依此类推，直到比较array1.key和array0.key，称为一趟“冒泡”，其结果是将具有最小关键字的记录排到序列的第1个位置上。然后再arrayn-1到array1之间进行一趟“冒泡”，将具有次小关键字的记录排到序列的第2个位置上。依此类推，直到第n-1趟，在arrayn-1和arrayn-2之间进行“冒泡”后，待排序序列已排成有序。 下一趟区间下标 0 1 2 3 4 5 6 初始关键字 6，091 67 35 62 29 72 46 第一趟冒泡后 6，1 2991 67 35 62 46 72 第二趟冒泡后 6，2 29 3591 67 46 62

8、 72 第三趟冒泡后 6，3 29 35 4691 67 62 72 第四趟冒泡后 6，4 29 35 46 6291 67 72 第五趟冒泡后 6，5 29 35 46 62 6791 72 第六趟冒泡后 序列有序 29 35 46 62 67 72 91 图9.3 冒泡排序示例 例如，有一组关键字序列为91,67,35,62,29,72,46，冒泡排序过程如图9.3所示。 用C语言描述的简单交换排序算法如下：算法算法9.3 冒泡排序算法。 void BubbleSort (NODE array,int n) /* 对存放在数组array中，长度为n的序列冒泡排序 */ int i,j,fl

9、ag; 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 快速排序快速排序 冒泡排序的一种改进。基本思想是：通过一趟排序后，大幅度减小排序序列的长度。在一趟排序后将某个记录根据其关键字，排到

10、序列的中间位置，且左边所有记录的关键字都比它的关键字小，而右边所有记录的关键字都比它的关键字大，这样一趟排序后，不仅有一个记录已排到正确的位置上，如下标为i，而且待排序序列分裂成长度较小的两个待排序区间(array0到arrayi-1和arrayi+1到arrayn-1)，将上述过程称为“划分”。一次划分得到两个小序列，再递归地对这两个小序列进行划分，直到序列的长度为1，这时待排序序列已排成有序。显然，一次划分的时间复杂度是O(n)，下面讨论划分的算法。 对arraystart到arrayend序列进行划分，首先要确定一个划分标准，通常选取序列的第一个记录的关键字，用变量mid暂存，另附设两个

11、指针i和j，其初值分别为start和end，划分的具体做法如下(i=start，j=end )： (1)j从所指的位置开始从后向前扫描，直到 arrayj.key=end) return; /* 仅有一个记录 */ i=start; j=end; mid=arrayi; while(ij) while(imid.key) j-; if(ij) arrayi=arrayj; i+; while(ij & arrayi.key=mid.key) i+; if(ij) arrayj=arrayi; j-; arrayi=mid; /* 一趟划分结束 */ Quick_Sort(array,s

12、tart,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个极值，置于相应目标位置。对array0到arrayn-1排序，

13、需进行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

14、=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(

15、a)所示。在输出最小关键字后，仅需将叶子结点中最小关键字(13)改为“最大值”，然后调整从树叶到根结点的路径上各结点的关键字，则根结点的关键字为次小关键字，如图9.5(b)所示。同理，可依次选出从小到大的所有关键字。图9.5 树形选择排序的示例 时间复杂度: O(nlog2n)缺点:是占用较多的存储空间来保存比较结果。 (2)堆排序堆排序 堆的定义：有n个记录的线性序列，其关键值序列为(k1,k2,kn)，满足如下条件： ki=k2i 2i=k2i 2i=n ki=k2i+1 2i+1=2i+1 2i+1=n 为在C语言中设计算法方便，修改堆定义为：若关键值序列为(k0,k1,kn-1)，满足

16、如下条件： 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

17、)所示，在输出堆顶记录之后，以堆中最后一个元素替代之，如图9.7(b)所示。此时，根结点的左、右子树均为堆，则仅需自上而下进行调整即可。首先以堆顶元素和其左、右子树根结点的较小值27比较，因堆顶元素97大，所以二者交换。交换之后又破坏右子树“堆”，则需要进行和上述相同的调整，直至树叶(如图9.7(c)所示)或调整后子树的“堆”没有被破坏结束。 图9.7 输出堆顶元素并调整建成新堆的过程 称这个自堆顶至树叶的调整过程为“筛选” 现在讨论第一个问题，即将一个待排序序列建成一个堆的过程，该过程就是一个反复“筛选”的过程。此时将序列看成一个完全二叉树，并且树最后一个非终端结点是序列的第trunc(n/

18、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(

19、jn) if(j+1arrayj+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开始