数据结构与算法7

第7章排序算法（4课时）排序，又称分类，是计算机进行数据处理时经常使用的一种重要操作。本章在介绍排序算法基本概念及对各种常见排序算法进行性能比较的基础上，重点讲解插入排序、选择排序、交换排序、归并排序和分配排序等常用排序算法的原理和实现方法。排序，是指将一个待排序元素集合按关键字递增（或递减）顺序整理为一个有序序列的过程。例如，对于一组具有关键字值{43,56,37,28,17,39,22,70}的数据元素集合{R1,R2,…,R8}，按关键字递增顺序的排序结果为{R5,R7,R4,R3,R6,R1,R2,R8}（对应的关键字值为{17,22,28,37,39,43,56,70}）。本教材以递增排序为例讲解排序算法。若任意两个待排序元素都具有不同的关键字值，则排序结果必然唯一；若多个待排序元素具有相同的关键字值，则排序结果可能不唯一。若采用某种排序算法对任一组元素进行排序，在排序前后，那些具有相同关键字值的元素之间的相对次序都保持不变，则将这种排序算法称为是稳定的，否则称为是不稳定的。例如，对于一组具有关键字值{43,56,37,28,17,37,22,70}的数据元素集合{R1,R2,…,R8}，若根据算法A得到的排序结果为{R5,R7,R4,R6,R3,R1,R2,R8}（对应的关键字值为{17,22,28,37,37,43,56,70}），则算法A是不稳定的。这里需要注意，不稳定的排序算法并不一定对每一组元素都会得到不稳定的排序结果，只要一种排序算法在某一组元素上得到不稳定的排序结果，则这种排序算法就是不稳定的。7.1排序算法及常见排序算法比较排序算法有很多，各有优缺点，一般从时间复杂度、空间复杂度、稳定性三个角度衡量算法优劣并结合实际应用条件选取适合的排序算法。其中，时间复杂度主要看排序时元素之间的比较次数和元素的移动次数；空间复杂度主要看排序时除了待排序元素所占据的空间外还需要多大的辅助空间。排序分为两类：内排序和外排序。内排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。外排序是指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。7.1排序算法及常见排序算法比较1.排序算法的适用范围直接插入排序、简单选择排序和冒泡排序都是简单排序算法，它们的时间复杂度和空间复杂度分别为O(n2)和O(1)。若待排序元素数量n较小，可以选用直接插入排序和冒泡排序。另外，当待排序元素基本有序时，也应选用直接插入排序和冒泡排序，此时时间复杂度都能达到O(n)。若元素本身数据量较大，元素移动操作代价较高，则应选用平均移动元素次数最少的简单选择排序。希尔排序是对直接插入排序算法的改进，大大降低了时间复杂度，但它是一种不稳定的排序算法。7.1排序算法及常见排序算法比较堆排序、快速排序和归并排序主要适用于待排序元素数量n较大的情况，当待排序元素数量n较小时，它们的性能有可能劣于简单排序算法。在所有平均时间复杂度为O(nlog2n)的算法中，尽管快速排序在最坏情况下时间复杂度较高，但它通常被认为是平均性能最好的一种算法。归并排序是一种稳定的排序算法，其时间性能一般要优于堆排序，但它所需要的辅助空间较多，堆排序所需的辅助空间最少，当可用空间非常有限时可以考虑使用。箱排序和基数排序的时间复杂度最低，但它们的空间复杂度最高。箱排序主要适用于待排序元素长度（即d值）较小的情况，在实际中应用不多；基数排序是箱排序的改进，主要适用于整数或字符串的排序，或者与其他排序算法结合进行实数的排序。7.1排序算法及常见排序算法比较2.排序算法的复杂度下面对各类排序算法的性能作一下比较。设待排序元素数目为n、待排序元素的长度为d、待排序元素每一位可能取值的个数为rd（例如，待排序元素为至多4位的整数，此时d=4、rd=10；再如，待排序元素为长度至多为20的字符串、每一字符取值为'a'~'z'，此时d=20、rd=26），则各排序算法的性能如表7-1所示。7.1排序算法及常见排序算法比较插入排序是指按关键字大小每次将一个待排序的元素插入到已排序的序列中，直至所有元素都插入完毕。插入排序有多种形式，下面主要介绍直接插入排序和希尔排序两种算法。7.2插入排序7.2插入排序7.2.1直接插入排序7.2.2希尔排序直接插入排序是一种简单排序算法，其具体步骤为：

初始已排序区为空，将第一个待排序的元素插入到已排序区中。将后继每一个待排序的元素依次取出，并按照关键字大小将其插入到已排序区中的适当位置，使该序列仍然有序。重复上一步骤直至将待排序的元素都插入到已排序序列中。7.2插入排序7.2.1直接插入排序直接插入排序的算法描述如下：【描述7-1】直接插入排序的算法描述。

分析：从图7-1中可见，已排序元素数目与待排序元素数目之和保持不变，因此，可以使用同一个数组的不同部分分别保存已排序序列和未排序元素集合。如定义一个一维数组R，在第i趟排序后R中下标为1到i+1的位置用于存放已排序序列、之后的位置用于存放未排序元素集合。7.2插入排序7.2.1直接插入排序7.2插入排序7.2.1直接插入排序

希尔排序，又称为“缩小增量排序”，其具体步骤为：令n为待排序元素数目，设置增量序列{d0,d1,…,dk}，其中n>d0>d1>…>dk=1。按增量di（i依次取值为0,1,…,k）将待排序元素分为di组，将所有下标距离为di的倍数的元素放在同一组中，即R[1],R[1+di],R[1+2*di],…在第一组中，R[2],R[2+di],R[2+2*di],…在第二组中，…，依此类推。然后分别在各组内进行直接插入排序。重复上一步骤直至最后以1为增量对所有待排序元素进行直接插入排序。7.2插入排序7.2.2希尔排序7.2插入排序7.2.2希尔排序提示：希尔排序的比较次数和移动次数依赖于增量序列，为了具有较好的性能，一般增量序列中的元素应避免互为倍数的情况。另外，增量序列中的最后一个元素必须是1。希尔排序算法的时间复杂度与使用的增量序列有关，但如何针对特定增量序列计算算法的时间复杂度以及如何选择增量序列使算法的时间复杂度最低仍是数学上尚未解决的难题。因此，这里仅给出定性的结论：当待排序元素数目n很大时，希尔排序算法的时间复杂度要远低于直接插入排序算法。与直接插入排序算法相同，希尔排序算法只需要一个监视哨的辅助空间，因此空间复杂度也为O(1)。从图7-2可以看出，希尔排序是不稳定的。7.2插入排序7.2.2希尔排序7.3选择排序选择排序是指每次从待排序的元素中选择具有最小（或最大）关键字的元素放到已排序序列的尾部（或头部），直至所有元素都排序完毕。选择排序有多种形式，下面主要介绍简单选择排序和堆排序两种。7.3选择排序7.3.1简单选择排序7.3.2堆排序7.3选择排序简单选择排序是一种简单排序算法，其具体步骤为：1）初始已排序区为空，待排序区包含所有待排序元素。2）从待排序区中选择具有最小关键字的元素，将其与待排序区的第一个元素交换位置，并将该位置加到已排序区中。3）重复上一步骤直至所有元素都排序完毕。7.3.1简单选择排序7.3选择排序7.3.1简单选择排序7.3选择排序在简单选择排序算法的每轮排序中，都需要对待排序区的所有元素进行比较，最后只有具有最小关键字的元素被取出，而其余待排序区中的元素在下一轮排序时需重新比较，这样就使得许多比较操作重复多次，增加了算法的时间复杂度。例如，对于图7-3所示的简单选择排序过程，在第1轮选择排序中，37和28已作过比较；而在第2轮和第3轮选择排序中，37和28会再作比较。堆排序是对简单选择排序算法的优化，它利用完全二叉树的顺序存储结构减少元素之间的重复比较。堆排序的过程实质上就是不断创建堆的过程，下面先给出堆的概念，然后再给出堆排序算法。7.3.2堆排序1.堆

对于包含n个元素的集合R={R[1],R[2],…,R[n]}，若满足：R[i]≤R[2*i]且R[i]≤R[2*i+1]（即R所表示的完全二叉树中每一棵子树的根结点的值均不大于其孩子结点的值）；或R[i]≥R[2*i]且R[i]≥R[2*i+1]（即R所表示的完全二叉树中每一棵子树的根结点的值均不小于其孩子结点的值）。

则称集合R为堆。若满足前一个条件则称R为小根堆，满足后一个条件则称R为大根堆。7.3选择排序7.3.2堆排序例如，{56,43,37,30,17,37,22,28}是一个大根堆，{17,28,22,30,56,37,37,43}是一个小根堆，它们所对应的完全二叉树表示分别如图7-4（a）和7-4（b）所示。7.3选择排序7.3.2堆排序2.建堆方法

建堆是指假设已存在一棵由元素关键字作为结点的完全二叉树，现在调整该二叉树中结点的值，使调整后的二叉树表示的元素集合是一个堆。

堆一般采用自底向上的构建方法，即在将以某一结点为根结点的二叉树构建成堆之前，先将其左子树和右子树构建成堆。以叶子结点为根的子树必然是堆，因此，对于由n个元素构成的完全二叉树，其对应的堆的构建过程从R[n/2]作为根结点的子树开始，依次对R[n/2-1]、R[n/2-2]、…、R[1]作为根结点的树进行堆的构建。例如，对于集合{30,22,37,17,28,37,56,43}，其对应的大根堆的构建过程如图7-5所示，在每一步处理时将虚线框中的子树整理为堆。7.3选择排序7.3.2堆排序7.3选择排序7.3.2堆排序在将一棵R[i]作为根结点的子树整理为堆时，只有根结点不满足堆的条件，因此，需将根结点与后继层中的结点依次比较并不断将根结点下移直至该子树满足堆的条件，这里以大根堆构建为例介绍其具体过程：若R[i]存在左孩子R[2*i]，则令j=2*i；若R[i]存在右孩子R[2*i+1]且R[2*i+1]>R[2*i]，则令j=2*i+1。将R[j]与R[i]比较，若R[i]较小，则将R[i]和R[j]交换，并令i=j。重复上述步骤直至R[i]无孩子结点或R[i]比其孩子结点都大，此时该子树即为堆。例如，对于图7-5所示的大根堆构建过程，图7-5（c）到图7-5（d）的作用是将整棵树整理为堆，其具体步骤为：将根结点R[1]与具有较大值的右孩子结点R[3]比较，有R[1]<R[3]，因此将R[1]和R[3]交换；将R[3]与左孩子结点R[6]比较（左右孩子同样大时以左孩子结点优先），有R[3]<R[6]，因此将R[3]和R[6]交换；R[6]无孩子结点，此时该树已整理为堆。7.3选择排序7.3.2堆排序3.堆排序算法下面给出堆排序的具体过程：采用自底向上的方法将包含n个元素的待排序集合R={R[1],R[2],…,R[n]}整理为大根堆，其元素数目i=n，初始时已排序集合R'为空集；将R[1]与R[i]交换，并将i算作已排序集合中的元素位置，更新待排序集合中最后一个元素的位置i=i-1，此时待排序集合R={R[1],R[2],…,R[i]}，已排序集合R'={R[i+1],R[i+2],…,R[n]}。显然，待排序集合R={R[1],R[2],…,R[i]}中只有根结点R[1]不满足大根堆的条件，通过下移R[1]重新将R整理为大根堆；重复上一步骤直至待排序集合R={R[1]}，此时直接将R[1]作为已排序集合R'中的元素，堆排序过程结束。7.3选择排序7.3.2堆排序例如，对于集合{30,22,37,17,28,37,56,43}，其堆排序过程如图7-6所示。可见，这里给出的堆排序选择元素的顺序与前面给出的简单选择排序正好相反，每轮堆排序从待排序集合中选择最大元素并将其放到已排序集合的头部。本书中给出的是常见实现方式，实际上可以利用小根堆实现堆排序使其选择元素的顺序与前面给出的简单选择排序相同，也可以更改前面给出的简单选择排序使其选择元素的顺序与这里给出的利用大根堆实现的堆排序相同。7.3选择排序7.3.2堆排序7.3选择排序7.3.2堆排序7.3选择排序7.3.2堆排序

堆排序算法的时间复杂度分析较为复杂，这里仅给出结论：堆排序算法在平均情况和最坏情况下所需的元素比较次数和元素移动次数的时间复杂度均为O(nlog2n)。堆排序算法只在整理堆和进行元素交换时需要一个辅助空间，因此空间复杂度为O(1)。从图7-6可以看出，堆排序是不稳定的。

提示：要实现降序排序，只要在建立初始堆和整理堆时按照小根堆处理就行了。感兴趣的读者可以自己对程序进行修改。7.3选择排序7.3.2堆排序7.4交换排序交换排序是指从待排序的元素中选择两个次序相反的元素进行交换，直至任意两个元素的次序都正确。下面介绍冒泡排序和快速排序两种交换排序方法。7.4交换排序7.4.1冒泡排序7.4.2快速排序7.4.1冒泡排序7.4交换排序冒泡排序是一种简单排序算法，其具体步骤为：初始已排序区为空，待排序区包含所有待排序元素。在一轮排序中，对待排序区所有相邻元素从前至后进行两两比较，若相邻两个元素次序相反（即前一个元素的关键字值大于后一个元素的关键字值），则交换它们的位置。每轮排序后，待排序区中的最大元素会移到待排序区的尾部，将待排序区的最后一个元素放到已排序区的头部。重复上一步骤直至待排序区中只剩下一个元素或者在一轮排序中没有出现相邻元素交换的情况，此时直接将待排序区中的所有元素按原次序放到已排序区的头部，冒泡排序结束。7.4.1冒泡排序7.4交换排序7.4.1冒泡排序7.4交换排序7.4交换排序在冒泡排序算法中，仅对相邻元素进行比较和交换。通过每次交换，元素前移或后移一个位置。若排序前元素位置为i，排序后元素位置为j，则在排序过程中为了将该元素移到正确位置需要做|j-i|次交换操作。因此，冒泡排序所需要的元素比较和移动次数较多。快速排序是对冒泡排序算法的优化，它通过对待排序集合进行逐层划分，可以实现两个相距较远元素的比较和交换操作，从而大大减少了元素的比较和移动次数。快速排序的过程实质上就是不断对待排序集合进行划分的过程，因此，在介绍快速排序之前，先说明划分的作用和待排序集合划分的过程。划分是以指定元素x为基准将一个集合R分为两个子集R1和R2，其中R1中的元素都小于或等于x，R2中的元素都大于或等于x。例如，对于集合R={43,56,37,28,17,37,22,30}，以43为基准，可以将其划分为两个子集R1={30,22,37,28,17,37}和R2={56}。7.4.2快速排序7.4交换排序对于包含(high-low+1)个元素的待排序集合R={R[low],R[low+1],…,R[high]}，以R[k]（low≤k≤high）为基准对其进行划分的具体过程为：令i、j分别指向集合R的第一个元素和最后一个元素（即i=low、j=high），并将R[k]与R[i]交换（即初始基准元素在i所指向的位置，此时基准元素前面没有任何元素，下面对基准元素后面、位置在i+1到j之间的元素按照从后至前的顺序逐一检查其是否大于或等于基准元素）。7.4.2快速排序7.4交换排序若j!=i且R[j]≥R[i]，则令j=j-1，重复直至R[j]<R[i]或j==i。若j!=i则将R[j]与R[i]交换、i=i+1，并转到下一步（该步处理结束后，基准元素在j所指向的位置，此时基准元素后面的元素都大于或等于基准元素，而位置i前面的元素都小于或等于基准元素，下面对基准元素前面、位置在i到j-1之间的元素按照从前至后的顺序逐一检查其是否小于或等于基准元素）。若i!=j且R[i]≤R[j]，则令i=i+1，重复直至R[i]>R[j]或i==j。若i!=j则将R[i]与R[j]交换、j=j-1，并回到上一步（该步处理结束后，基准元素在i所指向的位置，此时基准元素前面的元素都小于或等于基准元素，而位置j后面的元素都大于或等于基准元素，下面继续对基准元素后面、位置在i+1到j之间的元素按照从后至前的顺序逐一检查其是否大于或等于基准元素）；否则集合划分操作结束。7.4.2快速排序7.4交换排序集合划分操作结束后，i和j所共同指向的位置即是基准元素所在的位置，子集合R1={R[low],…,R[i-1]}中的元素都小于或等于基准元素R[i]，子集合R2={R[i+1],…,R[high]}中的元素都大于或等于基准元素R[i]。例如，对于集合R={43,56,37,28,17,37,22,30}，以28为基准，其划分过程如图7-8所示。7.4.2快速排序7.4交换排序7.4.2快速排序7.4交换排序集合划分的算法描述如下：【描述7-6】集合划分的算法描述。分析：在算法实现时，为了减少基准元素的移动次数，可以用R[0]保存基准元素，每次将元素R[X]与基准元素比较时直接将R[X]与R[0]比较即可，而每次将元素R[X]与基准元素交换时只需将元素R[X]移入基准元素应在的位置即可。在最后找到基准元素的正确位置后，将R[0]移入该位置。7.4.2快速排序7.4交换排序7.4.2快速排序图7-8所对应的算法实现处理过程如图7-9所示。7.4交换排序快速排序就是对集合不断划分的过程：通过划分可以将一个集合分为两个子集合，若子集合中元素数目大于1则再对子集合分别进行划分，重复该过程直至最终每个子集合中元素数目都小于或等于1时快速排序结束。例如，对于集合R={37,43,26,30,17,37,22,28}，其快速排序过程如图7-10所示（这里假设每次将待划分集合中的第一个元素作为基准元素）。7.4.2快速排序7.4交换排序7.4.2快速排序7.4交换排序【描述7-8】快速排序非递归实现的算法描述。分析：非递归快速排序需要利用栈实现，栈顶元素是当前要划分的集合（由Range类对象表示集合，其中两个成员变量m_low和m_high分别保存待划分集合的起始位置和结束位置）。具体步骤为：（1）将初始待排序集合进栈；（2）取栈顶元素，若上一次出栈的是划分后的两个子集合中的后一个子集合，则表明其划分后得到的两个子集合也已划分完毕，将栈顶元素出栈；若上一次出栈的是划分后的两个子集合中的前一个子集合，则表明其划分后得到的两个子集合中还有一个子集合没有进行划分，将后一个子集合进栈；否则，表明对栈顶元素所表示的集合还没有进行划分，此时若栈顶集合长度大于1则对栈顶集合进行划分、并将划分后得到的前一个子集合进栈，若栈顶集合长度小于或等于1则不需进行划分、直接出栈即可；（3）重复步骤（2）直至栈为空。7.4.2快速排序K路归并排序是指每次将K（K≥2）个已排序的子序列组合在一起，形成一个有序的序列，重复该过程直至得到一个包含所有待排序元素的有序序列。这里以二路归并排序（下文简称归并排序）为例介绍归并排序的算法。归并排序的具体步骤为：对于包含n个元素的待排序集合，将其分为n个长度为1的子序列；将每两个相邻的子序列进行归并，得到n/2个长度为2的子序列和0或1个长度为1的子序列；在此基础上，再对每两个相邻的子序列进行归并，得到n/4个长度为4的子序列和0或1个长度小于4的子序列；重复该过程直至得到一个长度为n的有序序列为止。7.5归并排序7.5归并排序7.6分配排序前面介绍的排序算法都是通过对待排序集合中元素的比较和移动来实现排序的。分配排序则采用了一种截然不同的思想，它不需要对元素进行直接比较，而是根据元素本身所具有的值将各元素逐一映射到一组有序空间中，最后再依次从有序空间中将各元素取出即形成了排序结果。与前面学习的排序算法相比，分配排序一般有着更低的时间复杂度但更高的空间复杂度。下面介绍箱排序和基数排序两种分配排序方法。7.6.1箱排序7.6.2基数排序7.6分配排序箱排序，又称为桶排序，是指通过设置一些有序的箱子，将待排序集合中各元素根据它们的值逐一分配到各箱子中，最后再按箱子的顺序依次将各元素从箱子中取出从而形成排序结果的一种排序算法。在箱排序中，箱子的个数由元素的取值范围决定。例如，要将学生按其课程成绩（设取值范围为0~100之间的整数）排序，则需要设置101个箱子；要将学生按其学号（设学号为7位，取值范围为0000000~9999999）排序，则需要设置10000000个箱子。可见，箱排序适用于取值范围较小的情况。另外，在箱排序中，具有相同值的元素会放在同一个箱子里。例如，n名学生的课程成绩都是m，那么在按课程成绩排序时这n名学生对应的是同一个箱子。此时，可以考虑每个箱子用一个线性表来保存若干个具有相同值的元素，在具体实现时通常使用队列以保证排序过程是稳定的。7.6分配排序7.6.1箱排序箱排序的具体步骤为：假设待排序元素的取值范围为m~m+n-1，则箱子数量为n，设置包含n个元素的队列集合B={B[0],B[1],…,B[n-1]}代表n个箱子。依次取出每一个待排序元素，若其值为m+i（i=0,1,…,n-1），则通过入队操作将其放在箱子B[i]中。从B[0]开始，依次检查集合B中每一个队列所代表的箱子，若箱子不为空，则通过出队操作将箱子中的元素逐个取出并依次加到已排序集合中。7.6分配排序7.6.1箱排序7.6分配排序7.6.1箱排序对于包含n个元素的待排序集合，箱排序算法仅需进行n次装箱操作和n次出箱操作，因此箱排序在任何情况下的时间复杂度均为O(n)。箱排序的空间复杂度与待排序元素的长度有关系，若对d位数据组成的集合进行箱排序，且数据的每一位可能取的值的个数为rd，那么需要rdd个箱子（例如，要对由4位十进制整数组成的集合进行箱排序，需设置104=10000个箱子），另外还需要设置与待排序元素数量相同的辅助空间来存储装箱的元素，因此箱排序的空间复杂度为O(n+rdd)。箱排序用队列存储具有相同值的元素，位置靠前的同值元素装箱时先入队、出箱时先出队，保证了同值元素的相对次序不会改变，因此归并排序是