各种经典排序算法

1、排排 序序本节基本内容与要求本节基本内容与要求o 基本内容基本内容n 顺序查找、二分查找、二叉树查找以及散列表上查找顺序查找、二分查找、二叉树查找以及散列表上查找 及算法思想及算法思想n 排序的基本概念以及选择、插入、交换和归并四类排排序的基本概念以及选择、插入、交换和归并四类排序的基本思想和算法序的基本思想和算法o 要求要求n 掌握线性表、树和散列表掌握线性表、树和散列表(或称哈希表或称哈希表)的查找方法及的查找方法及算法实现以及各种查找方法的应用算法实现以及各种查找方法的应用n 熟练掌握选择、插入、交换和归并四类排序的基本思熟练掌握选择、插入、交换和归并四类排序的基本思想和算法想和算法排排

2、 序序1.4 内部排序内部排序一、基本概念一、基本概念二、插入排序二、插入排序三、交换排序三、交换排序四、选择排序四、选择排序五、归并排序五、归并排序排排 序序一、基本概念一、基本概念1. 排序的功能排序的功能：将一个数据元素（或记录）：将一个数据元素（或记录）的的任意序列任意序列，重新排成一个按关键字，重新排成一个按关键字有有序序的序列。的序列。例如例如：下列是一组记录对应的关键字序列下列是一组记录对应的关键字序列(52, 49, 80, 36, 14, 58, 61, 23, 97, 75)调整为调整为(14, 23, 36, 49, 52, 58, 61 ,75, 80, 97)排排 序

3、序2. 排序的定义排序的定义假设含假设含n个记录的序列为个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系它们之间存在着这样一个关系 ： Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作的操作称作排序排序。排排 序序3、排序的基本操作、排序的基本操作o 排序的概念：排序的概念：就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。o 排序过程的组成

4、步骤排序过程的组成步骤：首先比较两个关键字的大小； 然后将记录从一个位置移动到另一个位置。n 对记录的关键字大小进行比较n 将记录从一个位置移动到另一个位置o 当待排序记录的关键字均不相同时，则排序结果是唯一的，否则排序的结果不一定唯一。排排 序序4、排序的稳定性、排序的稳定性若有：若有： R1 ,., Ri,.,Rj,.且关键字：且关键字： Ki=Kj ij排序后：排序后： Ri,Rj,.则称该排序结果具有稳定性。则称该排序结果具有稳定性。在待排序的文件中，若存在在待排序的文件中，若存在多个关键字相同的记录，经多个关键字相同的记录，经过排序后这些具有相同关键过排序后这些具有相同关键字的记录之

5、间的字的记录之间的相对次序相对次序保保持持不变不变，该排序方法是，该排序方法是稳定稳定的；的；若具有相同关键字的记录之若具有相同关键字的记录之间的间的相对次序相对次序发生发生变化变化，则，则称这种排序方法是称这种排序方法是不稳定不稳定的。的。排排 序序o 内部排序内部排序：是指在排序的整个过程中，：是指在排序的整个过程中，数据数据全部存放全部存放在计算机的在计算机的内存内存储器里，并且在内存储器里调整数据储器里，并且在内存储器里调整数据的位置；的位置；o 当文件很大以致内存不足以存放全部数据时，在排序当文件很大以致内存不足以存放全部数据时，在排序过程中需要对过程中需要对外存外存进行存取访问，称

6、这种借助于外存进行存取访问，称这种借助于外存储器进行排序的方法为储器进行排序的方法为外部排序外部排序。o 注意：注意：n 内排序适用于记录个数不很多的小文件内排序适用于记录个数不很多的小文件n 外排序则适用于记录个数太多，不能一次将其外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。全部记录放入内存的大文件。5、排序的分类、排序的分类排排 序序 o 每次将一个待排序的记录，按其关键字大小插入到前面每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入已经排好序的子文件中的适当位置，直到全部记录插入完成为止。完成为止。o 把新元素（未排序

7、的元素的关键字）逐个插入正在增长把新元素（未排序的元素的关键字）逐个插入正在增长的顺序表中。的顺序表中。o 寻找插入位置的方法寻找插入位置的方法：n 线性插入排序线性插入排序n 对半插入排序对半插入排序n 希尔排序希尔排序二、插入排序二、插入排序排排 序序有序序列L.r1.i-1L.ri无序序列 L.ri.n有序序列L.r1.i无序序列 L.ri+1.n1、线性插入排序、线性插入排序o 基本思想：基本思想：每步将一个待排序的元素按其大小插入到前每步将一个待排序的元素按其大小插入到前面已排序的数据中的适当位置。面已排序的数据中的适当位置。重复该工作，直至有序重复该工作，直至有序区包含所有元素。区

8、包含所有元素。排排 序序方法：方法：o 具体方法具体方法：先将第一个数据看成是一个有序的子序列，：先将第一个数据看成是一个有序的子序列，然后从第然后从第2个数据起逐个插入到这个有序的子序列中去，个数据起逐个插入到这个有序的子序列中去，相应的元素要移动。相应的元素要移动。3将将L.ri 插入插入到到L.rj+1的位置上。的位置上。2将将L.rj+1.i-1中的所有中的所有记录记录均均后移后移 一个位置；一个位置；1在在L.r1.i-1中中查找查找L.ri的插入位置，的插入位置， L.r1.j L.ri L.rj+1.i-1；排排 序序该算法适合于该算法适合于n n 较较小的情况，时间复小的情况，

9、时间复杂度为杂度为O(nO(n2 2).).待排元素序列：待排元素序列：5353 27 36 15 69 42 27 36 15 69 42第一次排序：第一次排序： 27 5327 53 36 15 69 42 36 15 69 42第二次排序：第二次排序： 27 36 5327 36 53 15 69 42 15 69 42第三次排序：第三次排序： 15 27 36 5315 27 36 53 69 42 69 42第四次排序：第四次排序： 15 27 36 53 6915 27 36 53 69 42 42第五次排序：第五次排序： 15 27 36 42 53 6915 27 36 42

10、53 69 线性插入排序示例线性插入排序示例对于有对于有n n个数个数据元素的待排据元素的待排序列，插入操序列，插入操作要进行作要进行n-1n-1次次例：例：排排 序序void insertSort(RedType L ,int n) int i ,j; for(i=2; i=n; i+) L0=Li; / 作为监视哨 for( j=i-1; L0.keyLj.key; j ) Lj+1=Lj; /记录后移 Lj+1=L0; / 插入 插入算法插入算法o 方法:Ki与Ki-1,K i-2,K1依次比较,直到找到应插入的位置。排排 序序哨兵哨兵( (监视哨监视哨) )o 哨兵(监视哨)有两个作用

11、n 作为临时变量存放Ri(当前要进行比较的关键字)的副本；n 在查找循环中用来监视下标变量j是否越界。R0 R1 R2 R3 R4 R5 6 206157315 62015737 6152073367152033671520直接插入排序的程序：直接插入排序的程序： #include stdio.h #define n 5 int arn; int c,t; void d_insort(a) int an; int i,j; for (i=2;i0) & (taj) aj+1=aj; j=j-1; aj+1=t; main() int i; printf(请输入数据请输入数据: ); f

12、or (i=1;i=n;i+) scanf(%d,&ari); d_insort(ar); printf(排序后的序列排序后的序列: ); for (i=1;i=n;i+) printf(%d |,ari); printf(n); 运行结果：运行结果：请输入数据请输入数据: 50 60 20 40 80排序后的序列排序后的序列: 20 |40 |50 |60 |80 |排排 序序性能分析性能分析最好情况（原始记录按关键字有序排列）：最好情况（原始记录按关键字有序排列）：O（n）“比较”的次数：最坏情况（原始记录按关键字逆序排列）：最坏情况（原始记录按关键字逆序排列）：O（n2）“比较”

13、的次数：112nni02) 1)(4() 1(2nnini“移动”的次数：“移动”的次数：2) 1n)(4n () 1i (n2i结论：适用原始数据基本有序或数据量不大的情况。排排 序序 希尔排序（希尔排序（Shells method）又称为）又称为“缩小增量排序缩小增量排序” ，本质上讲是插入排序，它是对线性插入排序的改进。本质上讲是插入排序，它是对线性插入排序的改进。其基本思想是：其基本思想是： 先取一个小于先取一个小于n的整数的整数d1并作为第一个增量，并作为第一个增量，将文件将文件的全部记录分成的全部记录分成d1个组，所有距离为个组，所有距离为d1倍数的记录放在同倍数的记录放在同一个组

14、中，在各组内进行直接插入排序；一个组中，在各组内进行直接插入排序； 然后取第二个增量然后取第二个增量d2d1，重复上述的分组和排序，重复上述的分组和排序，直至所取的增量直至所取的增量dt=1 (dtdt 1d2d1)为止，此时，所为止，此时，所有的记录放在同一组中进行直接插入排序。有的记录放在同一组中进行直接插入排序。 2 2 希尔插入排序希尔插入排序算法思想算法思想排排 序序o 如何选择增量序列才能产生最好的排序效果，这个问题如何选择增量序列才能产生最好的排序效果，这个问题至今没有得到解决。至今没有得到解决。o 希尔本人最初提出取希尔本人最初提出取n d1=d1= n/2n/2 ，n di+

15、1=di+1= di/2di/2 ，n dt=1dt=1，t=t= log2nlog2n 。排排 序序希尔插入排序希尔插入排序步骤步骤（1 1）首先选取一个整数）首先选取一个整数d d11n n（n n为待排序数据的个数），为待排序数据的个数），作为两个数据之间的作为两个数据之间的距离距离，这样把全部数据分成，这样把全部数据分成d d1 1个组，个组，凡是距离为凡是距离为d d1 1的数据放在一个组里，在各组内进行内部的数据放在一个组里，在各组内进行内部排序，直到各组排好序为止。排序，直到各组排好序为止。（2 2）从上述的结果序列出发，再选择）从上述的结果序列出发，再选择d d22d d1 1

16、，重复上面的，重复上面的分组与排序工作。分组与排序工作。（3 3）依次取）依次取didi+1+1didi，直到，直到dmdm=1=1（设一共需要（设一共需要m m次分组），次分组），即所有数据放在一组中排序为止。此时，全部数据便按即所有数据放在一组中排序为止。此时，全部数据便按次序排好了。次序排好了。设待排序共有设待排序共有10个记录，其关键字分别为个记录，其关键字分别为47, 33, 61, 82, 71, 11, 25, 47 , 57, 02，增量序列取值依次为，增量序列取值依次为5, 3, 1。 希尔插入排序希尔插入排序过程过程 排排 序序 希尔排序实质上还是一种插入排序，其主要特点是

17、：希尔排序实质上还是一种插入排序，其主要特点是：每一趟以不同的增量进行排序。每一趟以不同的增量进行排序。在每趟的插入排序中，记录在每趟的插入排序中，记录的关键字是和同一组中的前一个关键字进行比较，所以关键的关键字是和同一组中的前一个关键字进行比较，所以关键字较小的记录在排序过程中是作跳跃式的移动。字较小的记录在排序过程中是作跳跃式的移动。 另外，另外，由于开始时增量的取值较大，每组中记录较少，由于开始时增量的取值较大，每组中记录较少，故排序比较快，故排序比较快，随着增量值的逐步变小，每组中的记录逐渐随着增量值的逐步变小，每组中的记录逐渐变多，但由于此时记录已基本有序了，因次在进行最后一趟变多，

18、但由于此时记录已基本有序了，因次在进行最后一趟增量为增量为1的插入排序时，只需作少量的比较和移动便可完成的插入排序时，只需作少量的比较和移动便可完成排序，从而提高了排序速度。排序，从而提高了排序速度。 希尔插入排序希尔插入排序特点特点 排排 序序 希尔排序比直接插入排序的平均性能要好：希尔排序比直接插入排序的平均性能要好：l在在最好情况最好情况（原始记录按关键字有序排列）下，（原始记录按关键字有序排列）下，移动次数为移动次数为0，比较次数界于，比较次数界于n n2 之间。之间。l在在最坏情况最坏情况（原始记录按关键字逆序排列）下，（原始记录按关键字逆序排列）下，移动次数和比较次数接近移动次数和

19、比较次数接近n2。 l在在平均情况平均情况下下，移动次数和比较次数在移动次数和比较次数在O（n1.3）左右，好于直接插入排序。左右，好于直接插入排序。希尔插入排序希尔插入排序性能效率性能效率排排 序序例例1.19 希尔排序的程序希尔排序的程序 #include stdio.h #define max 10 int datamax+1; int indexmax+1; int i;排排 序序 void shell_sort(a) int amax+1; int i,j,n,m,skip; int alldone;for (i=1;i1) skip=skip/2; do alldone=1; fo

20、r (j=1;j=max-skip;j+) i=j+skip; n=indexi; m=indexj; if (anam) indexi=m; indexj=n; alldone=0; while (alldone=0); 排排 序序main() printf(请输入数据请输入数据: ); for (i=1;i=max;i+) scanf(%d,&datai); printf(n); for (i=1;i=max;i+) printf(%d ,datai); printf(n); shell_sort(data); for (i=1;i=max;i+) printf(%d ,datai

21、ndexi); printf(n); 排排 序序运行结果：运行结果： 请输入数据请输入数据: 19 41 11 17 47 43 13 37 31 23 19 41 11 17 47 43 13 37 31 23 11 13 17 19 23 31 37 41 43 47 希尔排序的分析较为复杂，因为它的时间是所取希尔排序的分析较为复杂，因为它的时间是所取“增量增量”序列的函数，这涉及到一些数学上尚未解决的序列的函数，这涉及到一些数学上尚未解决的难题。增量序列可以有各种取法，但需注意：应使增量难题。增量序列可以有各种取法，但需注意：应使增量序列中的值没有除序列中的值没有除1以外的公因子，并且最

22、后一个增量以外的公因子，并且最后一个增量值必须等于值必须等于1。2. 希尔排序希尔排序排排 序序 3.折半插入排序折半插入排序 当将待排序的记录当将待排序的记录Ri 插入到已排好序的记录子表插入到已排好序的记录子表R1i-1中时，由于中时，由于R1, R2 , Ri-1已排好序，则查找插入已排好序，则查找插入位置可以用位置可以用“折半查找折半查找”实现，则直接插入排序就变成为实现，则直接插入排序就变成为折半插入排序。折半插入排序。 算法实现算法实现void Binary_insert_sort(Sqlist *L) int i, j, low, high, mid ;for (i=2; ile

23、ngth; i+) L-R0=L-Ri; /* 设置哨兵设置哨兵 */排排 序序low=1 ; high=i-1 ; while (lowR0.key, L-Rmid.key) ) high=mid-1 ; else low=mid+1 ; /* 查找插入位置查找插入位置 */for (j=i-1; j=high+1; j-)L-Rj+1=L-Rj; L-Rhigh+1=L-R0; /* 插入到相应位置插入到相应位置 */排排 序序 从时间上比较，折半插入排序仅仅减少了关键字的比从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数，故时间复杂度仍然较次数，却没有减少记

24、录的移动次数，故时间复杂度仍然为为O(n2) 。 排序示例排序示例 设有一组关键字设有一组关键字30, 13, 70, 85, 39, 42, 6, 20，采用折半插入，采用折半插入排序方法排序的过程如图所示：排序方法排序的过程如图所示：排排 序序i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85) 20i=8 20 (6 13 30 39 42 70 85) 20lowhighmidi=8 20 (6 13 30 39 42 70 85) 20lowhighmidi=8 2

25、0 (6 13 30 39 42 70 85) 20mid highlowi=8 20 (6 13 20 30 39 42 70 85)排排 序序 4 2-路插入排序路插入排序 是对折半插入排序的改进，以减少排序过程中移动记录是对折半插入排序的改进，以减少排序过程中移动记录的次数。附加的次数。附加n个记录的辅助空间，方法是：个记录的辅助空间，方法是： 另设一个和另设一个和L-R同类型的数组同类型的数组d，L-R1赋给赋给d1，将，将d1看成是排好序的序列中中间位置的记录；看成是排好序的序列中中间位置的记录； 分别将分别将L-R 中的第中的第i个记录依次插入到个记录依次插入到d1之前或之前或之后

26、的有序序列中，具体方法：之后的有序序列中，具体方法： L-Ri.keyRi插入到插入到d1之前的之前的有序表中；有序表中； L-Ri.keyd1.key： L-Ri插入到插入到d1之后的之后的有序表中；有序表中；排排 序序关键点关键点：实现时将向量：实现时将向量d看成是循环向量，并设两个指针看成是循环向量，并设两个指针first和和final分别指示排序过程中得到的有序序列中的第一个分别指示排序过程中得到的有序序列中的第一个和最后一个记录。和最后一个记录。排序示例排序示例设有初始关键字集合设有初始关键字集合49, 38, 65, 13, 97, 27, 76 ，采用，采用2-路插路插入排序的过

27、程如右图入排序的过程如右图10-3所示。所示。 在在2-路插入排序中，移动记录的次数约为路插入排序中，移动记录的次数约为n2/8 。但当。但当L-R1是待排序记录中关键字最大或最小的记录时，是待排序记录中关键字最大或最小的记录时，2-路插路插入排序就完全失去了优越性。入排序就完全失去了优越性。排排 序序2776d49firstfirstfirstfirstfinalfinalfinalfinal6538979713132-路插入排序过程路插入排序过程排排 序序ovoid CInsertionSort:Path2Insertion(void)oo /元素0是哨兵。o const int coun

28、t = 9, length = count -1;o int Lcount = 0, 49, 38, 65, 97, 76, 13, 27, 49;o /对顺序表L作2-路插入排序。o int dlength = 0 ;o d0 = L1;/L中D的第一个记录为d中排好序的记录。o int first = 0, final = 0;/first、final分别指示d中排好序的记录的第1个和最后1个记录的位置。o for (int i = 2; i = length; +i)/依次将L的第2个最后一个记录插入d中。o o if (Li dfinal)/待插入记录大于d中最小值，插入到dfinal

29、之后（不需移动d数组的元素）。o o final = final + 1;o dfinal = Li;o o else/待插入记录大于d中最小值，小于d中最大值，插入到d的中间（需要移动d数组的元素）。o o int j = final +;/移动d尾部元素以便按序插入记录。o while (Li dj)o o d(j + 1) % length = dj;o j = (j - 1 + length) % length;o o dj + 1 = Li;o o 排排 序序o for (int i = 1; i = length; i +)/循环把d赋给L。o o Li = d(i + first

30、 - 1) % length;/线性关系。o o /打印排序结果。o for (int i = 0; i = length; + i)o o cout Li t;o o cout endl;o排排 序序前面的插入排序不可避免地要移动记录，若不移动记录就前面的插入排序不可避免地要移动记录，若不移动记录就需要改变数据结构。附加需要改变数据结构。附加n个记录的辅助空间，记录类型修个记录的辅助空间，记录类型修改为：改为：5 表插入排序表插入排序排排 序序38p 表插入排序的思想 (1)目的是为了减少在排序过程中进行的 “移动”记录的操作； (2)利用静态链表进行排序，排序中只改为指针； (3)在排序完

31、成之后，一次性地调整各个记录相互之间的位置。 5表插入排序排排 序序例：例：设有关键字集合设有关键字集合49, 38, 65, 97, 76, 13, 27, 49 ，采用表，采用表插入排序的过程如下图所示。插入排序的过程如下图所示。 0 1 2 3 4 5 6 7 8key域域next域域MAXINT 49 38 65 13 97 27 76 49 1 0 - - - - - - -i=2MAXINT 49 38 65 13 97 27 76 49 2 0 1 - - - - - -i=3MAXINT 49 38 65 13 97 27 76 49 2 3 1 0 - - - - -i=4M

32、AXINT 49 38 65 13 97 27 76 49 4 3 1 0 2 - - - -i=5MAXINT 49 38 65 13 97 27 76 49 4 3 1 5 2 0 - - -排排 序序i=6MAXINT 49 38 65 13 97 27 76 49 4 3 1 5 6 0 2 - -i=7MAXINT 49 38 65 13 97 27 76 49 4 3 1 7 6 0 2 5 -i=8MAXINT 49 38 65 13 97 27 76 49 4 8 1 7 6 0 2 5 3排排 序序表插入排序算法分析： 时间开销：无需移动记录，只需修改2n次指针值。但由于比较

33、次数没有减少，故时间效率仍为O(n2) 。 空间开销：空间效率肯定低，因为增开了指针分量。 稳定性：49和49*排序前后次序未变，稳定。排排 序序o/静态链表otypedef structooint key;/关键字oint next;/指向下一个关键字的下标oNode,*PNode;o/表插入排序ovoid tableInsertSort(PNode list,int n)ooint p,head;oint i;o/初始化olist0.next=1;olist1.next=0;o o 排排 序序/逐个插入for(i=2;i=n;i+)head=0;p=list0.next;/遍历链表，寻找插

34、入位置while(p!=0 & listp.keylength;i1;-i) for (j=1;jrj+1rj) Swap(L-rj,L-rj+1); 时间性能分析：时间性能分析：比较次数比较次数:最坏最坏(n-1)+(n-2)+.+1; 最好：最好： n-1 移动次数移动次数:最坏：最坏：3(n-1)+(n-2)+.+1)；最好：；最好：0 7.3.1 冒泡排序冒泡排序算法和性能分析算法和性能分析排排 序序23 38 22 45 23 67 31 15 41初始关键字序列初始关键字序列:第一趟排序后第一趟排序后:23 22 38 23 45 31 15 41 67第二趟排序后第二趟排

35、序后:22 23 23 38 31 15 41 45 67第三趟排序后第三趟排序后:22 23 23 31 15 38 41 45 67第四趟排序后第四趟排序后:22 23 23 15 31 38 41 45 67第五趟排序后第五趟排序后:22 23 15 23 31 38 41 45 67第六趟排序后第六趟排序后:22 15 23 23 31 38 41 45 67第七趟排序后第七趟排序后:15 22 23 23 31 38 41 45 672 排序示排序示例例 设有设有9个待排序的记录个待排序的记录，关键字分别为，关键字分别为23, 38, 22, 45, 23, 67, 31, 15,

36、41，冒泡排序的过程如图，冒泡排序的过程如图所示所示。排排 序序523197825531579 89i=7i=6for (j = 1; j rj+1 rj) 13i=27.3.1 冒泡排序冒泡排序改进改进排排 序序void BubbleSort(SqList *L) i=L-length; while (i1) /定位第定位第i个位置的记录个位置的记录 lastExchangeIndex=1; for (j=1;jrj+1rj) Swap(L-rj,L-rj+1); lastExchangeIndex=j; i=lastExchangeIndex; 7.3.1 冒泡排序冒泡排序改进算法改进算法

37、排排 序序最好情况（记录按关键字有序排列）：只需进行一趟冒泡最好情况（记录按关键字有序排列）：只需进行一趟冒泡“比较”的次数：最坏情况（记录按关键字逆序排列）：需进行最坏情况（记录按关键字逆序排列）：需进行n-1趟冒泡趟冒泡“比较”的次数：0“移动”的次数：“移动”的次数：n-12) 1() 1(2nnini2) 1(3) 1(32nnini7.3.1 冒泡排序冒泡排序性能分析性能分析排排 序序 首先对无序的记录序列进行首先对无序的记录序列进行“一次划分一次划分”，通过一趟排序通过一趟排序将待排序列将待排序列分成两部分分成两部分，使其中，使其中一部分记录一部分记录的关键字均比的关键字均比另另一

38、部分小一部分小，再，再分别分别对这两部分排序，以达到整个序列有序。对这两部分排序，以达到整个序列有序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序7.3.2 快速排序快速排序基本思想基本思想排排 序序快速排序快速排序 目标目标o 找一个记录，找一个记录，以它的关键字作为以它的关键字作为“枢轴枢轴”，凡凡其其关键字小于枢轴关键字小于枢轴的记录的记录移至该记录之前，移至该记录之前，反反之，之，移至该记录之后。移至该记录之后。o 一趟排序一趟排序之后，无序序列之后，无序序列L.r low.

39、high将被将被分割成两个部分分割成两个部分：L.rlow.i-1和和L.r i+1.high 且且 L.r j L.r i L.r j (lowji-1) 枢轴枢轴 (i+1jhigh)。排排 序序快速排序快速排序 方法方法o 关键字通常取第一个记录的值为基准值。关键字通常取第一个记录的值为基准值。o 方法：附设两个指针方法：附设两个指针i i和和j j ，初值分别指向，初值分别指向第一第一个记录个记录和和最后一个记录最后一个记录，设关键字为，设关键字为 key key ，首，首先从先从 j j所指位置起所指位置起向前向前搜索，找到第一个搜索，找到第一个小于小于基准值的记录与基准记录交换，然

40、后从基准值的记录与基准记录交换，然后从i i 所指所指位置起位置起向后向后搜索，找到第一个搜索，找到第一个大于大于基准值的记基准值的记录与基准记录交换，重复这两步直至录与基准记录交换，重复这两步直至i=ji=j为止。为止。初始值初始值 46 55 13 42 94 5 17 70快速排序一趟算法快速排序一趟算法初始值初始值 46 55 13 42 94 5 17 70ij17 55 13 42 94 5 17 7017 55 13 42 94 5 55 70基准X=4617 5 13 42 94 5 55 70移动jij移动ij移动jiii17 5 13 42 94 94 55 7017 5

41、13 42 94 94 55 7046i jiiii排排 序序第一趟第一趟 13 5 17 42 46 94 55 70快速排序例快速排序例初始值初始值 46 55 13 42 94 5 17 70第二趟第二趟 5 13 17 42 46 70 55 94第三趟第三趟 5 13 17 42 46 55 70 94第四趟第四趟 5 13 17 42 46 55 70 94快速排序快速排序步骤步骤(1)(1)令指针令指针L L1 1 ，R Rn n ，即分别指向，即分别指向A A1 1和和AnAn；(2)(2)自尾端开始进行比较：将自尾端开始进行比较：将ARAR与与ALAL比较，若比较，若ALAL

42、ARAR，则数，则数据就不交换，此时固定据就不交换，此时固定L L（即（即L L指针不动），调整尾指针，指针不动），调整尾指针，使使R RR R-1-1。继续比较，直至。继续比较，直至ALALARAR时为止，将时为止，将ARAR与与ALAL交换位置，并修改左指针，使交换位置，并修改左指针，使L LL L+1+1；(3)(3)将将ALAL与与ARAR比较，若比较，若ALALARAR，则调整左指针，使，则调整左指针，使L LL L+1+1，R R指针不动。继续比较，直至指针不动。继续比较，直至ALALARAR时为止，将时为止，将ALAL与与ARAR交换位置，并修改右指针交换位置，并修改右指针R R

43、，使，使R RR R-1-1；(4)(4)重复重复(2)(3)(2)(3)步骤，直到从两边开始的扫描在中间相遇，步骤，直到从两边开始的扫描在中间相遇，即即L L、R R指针重合于中间某一个元素，此时该元素即在排指针重合于中间某一个元素，此时该元素即在排序的序列中找到了自己合适的位置，并且此元素将原序序的序列中找到了自己合适的位置，并且此元素将原序列分成了前后两个子集。虽然此时这两个子集还是无序列分成了前后两个子集。虽然此时这两个子集还是无序的，但前一个子集的所有元素均小于后一个子集的所有的，但前一个子集的所有元素均小于后一个子集的所有元素。这称为一趟。元素。这称为一趟。排排 序序设设 L.rl

44、ow=46为枢轴为枢轴，在调整过程中，设立两个指针：在调整过程中，设立两个指针： low 和和high，之后，之后逐渐减小逐渐减小 high或或增加增加 low，并保证：，并保证：将将 L.rhigh和枢轴的关键字进行比较，要求和枢轴的关键字进行比较，要求L.rhigh枢枢轴的关键字轴的关键字将将 L.rlow和枢轴的关键字进行比较，要求和枢轴的关键字进行比较，要求L.rlow枢轴枢轴的关键字的关键字 L.rhigh枢轴枢轴且且L.rlow枢轴枢轴, ,否则进行记录的否则进行记录的“交换交换”。快速排序算法快速排序算法void quicksort(int r ,int left,int rig

45、ht)int i=left, j=right;int x=ri;while (i=x) & (ji) ) j=j-1; /向前比较向前比较 ri=rj; /比比x小的元素左移小的元素左移 while ( (rii) ) i=i+1; /向后比较向后比较 rj=ri; /比比x大的元素右移大的元素右移ri=x; /基准值基准值x归位归位quicksort(r,left,i-1); /递归调用左子区间递归调用左子区间quicksort(r,i+1,right); /递归调用右子区间递归调用右子区间leftrighti排排 序序快速排序的时间主要耗费在划分操作上，对长度为快速排序的时间主要耗

46、费在划分操作上，对长度为k k的区的区间进行划分，共需间进行划分，共需k-1k-1次关键字的比较。次关键字的比较。最坏情况最坏情况是每次划分选取的基准都是当前无序区中是每次划分选取的基准都是当前无序区中关键字关键字最小最小( (或最大或最大) )的记录的记录，划分的结果是基准左边的子区间为，划分的结果是基准左边的子区间为空空( (或右边的子区间为空或右边的子区间为空) )，而划分所得的另一个非空的子，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做一个。因此，快速排序必须做n-1n-1次划分

47、，第次划分，第i i次划分开始次划分开始时区间长度为时区间长度为n-i+1n-i+1，所需的比较次数为，所需的比较次数为n-in-i(1in-1)(1in-1)，故总的比较次数达到最大值：故总的比较次数达到最大值： n(n-1)/2=O(nn(n-1)/2=O(n2 2) )快速排序快速排序时间分析时间分析排排 序序在在最好情况最好情况下，每次划分所取的基准都是当前无序区的下，每次划分所取的基准都是当前无序区的“中值中值”记录记录，划分的结果是基准的左、右两个无序子区，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：间的长度大致相等。总的关键字比较次数： O(nlog

48、n)因为快速排序的因为快速排序的记录移动次数不大于比较的次数记录移动次数不大于比较的次数，所以快，所以快速排序：速排序： 最坏最坏时间复杂度应为时间复杂度应为O (n2) 最好最好时间复杂度为时间复杂度为O(nlogn) 平均平均时间复杂度为时间复杂度为O(nlogn)快速排序快速排序时间分析时间分析排排 序序 快速排序在系统内部需要一个栈来实现递归。若每次划分快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为较为均匀，则其递归树的高度为O(logn)，故递归后需栈空，故递归后需栈空间为间为O(logn)。最坏情况下，递归树的高度为。最坏情况下，递归树的高度为O(n

49、)，所需的，所需的栈空间为栈空间为O(n)。因为快速排序的因为快速排序的划分次数在划分次数在lognn之间之间，所以快速排序的：，所以快速排序的： 最坏最坏空间复杂度应为空间复杂度应为O (n) 最好最好空间复杂度为空间复杂度为O(logn) 平均平均空间复杂度为空间复杂度为O(logn)快速排序快速排序空间分析空间分析排排 序序若待排记录的初始状态为按关键字有序时，快速排序若待排记录的初始状态为按关键字有序时，快速排序将退化为冒泡排序将退化为冒泡排序，其时间复杂度为，其时间复杂度为O(n2)。因此，快速排序适用于原始数据杂乱无章的倾向。因此，快速排序适用于原始数据杂乱无章的倾向。辅助空间数量

50、为递归调用所开辟的栈空间。辅助空间数量为递归调用所开辟的栈空间。7.3.2 快速排序快速排序适用范围适用范围结论结论: 快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)且适用于且适用于原始数据杂乱无章的情况。快速排序是非稳定的。原始数据杂乱无章的情况。快速排序是非稳定的。 快速排序的程序：快速排序的程序： #include stdio.h #define n 10 int arn+1; int i,l1; int quick1(a,l,r) int an+1; int l,r; /* 指针指针 */ int l1; int r1,w; l1=l; r1=r; w=al1; do w

51、hile (ar1=w) & (l1r1) r1=r1-1; if (l1r1) al1=ar1; l1=l1+1; while (al1=w) & (l1r1) l1=l1+1; if (l1r1) ar1=al1; r1=r1-1; while(l1!=r1); al1=w; return(l1); 排排 序序void q_sort(a,l,r) int an+1; int l,r;int l1; if (lr) l1=quick1(a,l,r); q_sort(a,l,l1-1); q_sort(a,l1+1,r); main() printf(请输入数据请输入数据: n

52、); for (i=1;i=n;i+) scanf(%d,&ari); q_sort(ar,1,n); printf(排序后的序列排序后的序列:n); for (i=1;i=n;i+) printf(%d ,ari); if (i % 5=0) printf(n); 运行结果：运行结果：请输入数据请输入数据: 42 23 74 11 65 58 94 36 99 87排序后的序列排序后的序列:11 23 36 42 58 65 74 87 94 99 排排 序序完成一趟排序：初始关键词：排排 序序完成二趟排序：排排 序序完成三趟排序：完成四趟排序：排排 序序23, 10, 20, 36

53、, 40, 13, 27, 1111, 10, 20, 13, 23, 40, 27, 3610, 11, 20, 13, 23, 40, 27, 3610, 11, 13, 20, 23, 40, 27, 3610, 11, 13, 20, 23, 36, 27, 4010, 11, 13, 20, 23, 27, 36, 4010, 11, 20, 13, 23, 40, 27, 3610, 11, 13, 20, 23, 40, 27, 367.3.2 快速排序快速排序过程过程排排 序序7.4 选择选择 排排 序序简单选择排序简单选择排序堆堆 排排 序序排排 序序假设排序过程中，待排记录

54、序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列有序序列L.r 1.i-1无序序列无序序列 L.r i.n 第第 i 趟趟简单选择排序简单选择排序从中选出从中选出关键字最小的记录关键字最小的记录有序序列有序序列L.r1.i无序序列无序序列 L.ri+1.n7.4.1 简单选择排序简单选择排序基本思想和过程基本思想和过程排排 序序四、选择排序四、选择排序o直接选择排序直接选择排序n又称为简单选择排序，是一种简单直观的排序方法。n从待排序的所有记录中，选取关键字最小的记录，并将它与原始序列中的第一个记录交换，然后从去掉了关键字最小记录的剩余记录中选择关键字最小的记录将它与原始记录序列的

55、第二个记录交换位置，以此类推，直到序列中全部记录排序完毕。排排 序序待排序序列6457892018172445第一趟5647892018172445第二趟5764892018172445第三趟5717892018642445第四趟5717182089642445第五趟5717182089642445第六趟5717182024648945第七趟5717182024458964第八趟5717182024456489结果5717182024456489排排 序序o 算法：算法：/对记录序列对记录序列x0 xn-1进行直接选择排序进行直接选择排序void selectsort(elemtype x,i

56、nt n) int i,j,small;elemtype swap;for(i=0;in-1;i+) small=i; for(j=i+1;jn;j+) if(xj.keyxsmall.key) small=j; if(small!=i) swap=xi; Xi=xsmall; Xsmall=swap; 排排 序序对对 n 个记录进行简单选择排序，所需进行的个记录进行简单选择排序，所需进行的 关键字间的比较次数关键字间的比较次数 总计为：总计为：移动记录的次数移动记录的次数，最小值为最小值为 0, 最大值为最大值为3(n-1) 。2) 1()(11nninni7.4.1 简单选择排序简单选择排

57、序算法时间性能分析算法时间性能分析排排 序序o 堆就是一个关键字序列堆就是一个关键字序列：并且这并且这n个关键字的序个关键字的序列列K1,K2.Kn要满足以下性质要满足以下性质(堆性质堆性质)，就是，就是: KiK2i且且KiK2i+1 或者或者 KiK2i且且KiK2i+1 2、堆排序、堆排序堆的定义堆的定义(正堆正堆)(逆堆逆堆)12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49 是正堆是正堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49 不是堆不是堆1 2 3 4 5 6 7 8 9 10 11排排 序序o 当把这个

58、序列存入一个向量并把它看作是一棵完全二当把这个序列存入一个向量并把它看作是一棵完全二叉树的存储结构时，堆就是这样一棵二叉树：叉树的存储结构时，堆就是这样一棵二叉树：任一非任一非叶结点的关键字均不小于叶结点的关键字均不小于( (或不大于或不大于) )其左右孩子结点其左右孩子结点的关键字。的关键字。2、堆排序、堆排序1236276549817355403498是堆是堆14不不排排 序序94701746550513421 2 3 4 5 6 7 89470174642550513堆堆最大值排排 序序897624331510112536497856a) 堆顶元素取最大值堆顶元素取最大值大根堆大根堆b)

59、 堆顶元素取最小值堆顶元素取最小值小根堆小根堆排排 序序堆排序基本思想堆排序基本思想o因为堆顶是最大的数，所以当把一个关键字序列排成一个大根堆时，就很容易地找到最大的数，它就在序列的第一个位置上o然后把这个最大的数与最后一个记录交换，这时，最后一个记录就是关键字最大的记录了。o对于剩下的关键字序列，我们仍然把它排成一个大根堆，然后再把第一个记录(当前堆中的堆顶)与当前堆的最后一个记录交换。这时，在整个序列后面就有了两个有序的关键字(从小到大)。o重复这样的过程，就可以把有序区不断扩大直到全部关键字都进入有序区。直到排序完成。947017464255 0513初始堆初始堆427017469455

60、 0513135517469442 0570排排 序序堆的构造堆的构造o 无序序列无序序列r1：n构成的完全二叉树。构成的完全二叉树。o 从它最后一个非叶子结点（第从它最后一个非叶子结点（第n/2个元素）开始直到根个元素）开始直到根结点为止，逐步进行结点为止，逐步进行调整调整即可将此完全二叉树构成堆。即可将此完全二叉树构成堆。o 调整：调整：与其左右子树根结点值比较，取其中大的进行交与其左右子树根结点值比较，取其中大的进行交换。换。排排 序序堆的构造例堆的构造例465513427094 051746 55 13 42 94 05 17 707017594421355461 2 3 4 5 6 7 81 2 3 4 5 6 7 8排排 序序465513704294