基于递归与分治的排序算法教学探究∗

张忠诚 鲁法明

（山东科技大学计算机科学与工程学院 青岛 266590）

1 引言

排序是生活中最为常用的一种算法，迄今为止，人类发明了各种各样的排序算法，有基于插入操作的插入类排序，有基于交换操作的冒泡排序，有基于选择操作的选择排序等。很多精妙的排序方法背后可能隐含着相同的算法设计策略。以直接插入排序［1，8］、简单选择排序［1］、冒泡排序［1］、快速排序［2～3］以及归并排序［4～5］为例，它们采用的基本操作和排序过程不同，但实际都可以由递归与分治策略得出。本文分析这些经典排序算法背后隐含的递归与分治原理，并从递归与分治的角度分析它们在排序原理、排序过程以及排序性能之间存在的异同，以便于学习者加深对排序算法以及递归与分治策略的理解。

2 递归与分治的基本原理

递归与分治［1，7］是一种经典的问题求解策略，其基本思想是:对于一个规模为N的问题，若该问题可以容易地解决（比如说规模N较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地求解这些子问题，然后将各子问题的解合并得到原问题的解。递归与分冶法在每一层递归时都有如下三大步骤:

1）将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

2）若子问题规模较小而容易被解决则直接解，否则递归地求解各个子问题；

3）将这些子问题的解合并成原问题的解。

分治是思想，递归是手段，二者相辅相成。要想求解分治问题，最常用的方法就是针对相应的分治问题设计递归函数。那么该如何设计一个递归函数呢？设计一个递归函数需要确定以下两个条件。首先要确定递归边界，即每个递归函数必须至少有一个递归边界，当满足这个边界条件时递归不再进行，即函数不再调用自身而是直接返回处理结果。其次要设计递归关系，即如何将规模较大的原问题的求解归结为规模较小的若干子问题的求解。

3 经典排序算法的递归原理

3.1 直接插入排序

3.1.1 直接插入排序过程及非递归实现

直接插入排序将待排序序列无序块和有序块，有序块在前，无序块灾后。通过比较和移动将无序块首元素插入有序块适当位置，使得有序块不断变长；如此重复，N-1趟则完成排序（N为序列长度）。插入类排序的基本操作是无序块首元素到左侧有序块的“插入”，故称之为“插入类排序”。

基于上述关于直接插入排序的过程描述，可得直接插入排序的非递归实现如图1所示，其中arr表示待排序数组，lengthOfArr表示待排序数组的长度，之后的所给出的程序中若无特殊说明，符号含义均是如此，同时假设题目要求是由小到大进行排序。

图1 直接插入排序的非递归实现

图2 直接插入排序的递归实现

3.1.2 直接插入排序的递归与分治原理及递归实现

分析直接插入排序的过程可见，一趟插入排序完成后，有序块长度增加1，待处理的无序块长度减小1。初始无序块长度为N-1，经过N-1趟直接插入排序后，无序块长度变为0。将该排序过程看作无序块的消除过程，则直接插入排序可以理解为如下一个递归的过程。

递归边界:无序块长度为1时自然有序，递归终止；

递归关系:无序块长度大于1时，首先消除无序块首元素，将其插入到左侧有序块的适当位置，使得左侧有序块长度增加1，同时无序块长度减小1，递归处理无序块。

根据上述递归解释，我们可以得到图3所示的插入排序原理图，相应的直接插入排序的递归函数代码见图2。

图3 直接插入排序图解

3.2 冒泡排序

3.2.1 冒泡排序过程及非递归实现

冒泡排序分为多轮，每轮对待排序序列进行遍历，遍历过程中对相邻的元素进行两两比较，如果它们的顺序错误则交换之。上述过程重复进行，最多N-1趟则不再有交换发生，排序终止。实际上，每一轮冒泡排序都会使得当前最大的元素沉到最底部，而小的元素不断的朝上冒，故形象地称之为冒泡排序。基于上述关于冒泡排序的过程描述，可得冒泡排序的非递归实现如图5所示。

3.2.2 冒泡排序的递归与分治原理及递归实现

冒泡排序的过程同样可以用递归与分治的思想来解释。待排序序列看作由有序块和无序块两部分组成，无序块在前，有序块在后。每一轮冒泡将无序块最大的元素都移动到有序块的最前部，此时有序块长度加1，无序块长度减1。将该排序过程看作无序块的消除过程，则冒泡排序可以理解为如下一个递归的过程。

递归边界:无序块长度为1时或者一轮冒泡排序没有发生交换时，排序终止；

递归关系:只要不满足递归边界的条件，就遍历当前无序块，从首元素开始两两比较，只要不满足大小顺序要求就交换，每次递归无序块长度减1，递归处理无序块；

根据上述递归解释可得图4所示冒泡排序的原理图，其对应的递归函数代码见图6。

图4 冒泡排序图解

图5 冒泡排序的非递归实现

图6 冒泡排序的递归实现

3.3 选择排序

3.3.1 选择排序过程及非递归实现

简单选择排序首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找当前最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。基于上述关于选择排序的过程描述我们可得选择排序的非递归实现如图8所示。

3.3.2 选择排序的递归与分治原理及递归实现

简单选择排序可以看作一种贪心算法，每趟排序都挑选出当前最小的元素放到无序块最前端（或者说有序块最后面）。同时，它也可以基于递归与分治的策略来解释。同样将待排序序列分为有序块和无序块两部分，有序块在前，无序块在后，每一趟选择排序都是将当前子序列的最小值添加到有序块的后面，有序块的长度加1，无序块的长度减1，这也是一个无序块逐步变小过程，基于此可以得到简单选择排序的递归描述如图7。

图7 选择排序图解

递归边界:长度为1的序列自然有序，递归终止；

递归关系:若长度大于1，则选择当前无序块的最小值，与当前无序块的首元素进行交换，即添加到有序块的后面。使得有序块的长度加1，无序块的长度减1，递归处理无序块。

The pore throat characteristics of narrow-channel tight sandstone gas reservoirs in the

可得图7所示冒泡排序的原理图，其对应的递归函数代码见图9。

图8 选择排序的非递归实现

图9 选择排序的递归实现

3.4 快速排序

快速排序直接使用递归与分治策略把一个待排序序列根据枢轴元素一分为二，左侧子序列元素值均小于或者等于枢轴元素，右侧均大于或等于枢轴元素。具体步骤如下:从序列中挑出一个元素（例如选择待处理序列最左侧元素），称为“枢轴”或者“基准”元素，通过一趟划分操作使得枢轴左侧的元素均小于或等于基准值，枢轴右侧的元素均大于或等于基准值；显然，一趟划分后，枢轴两侧待处理的子序列长度都比原始序列小，该过程不断重复，最终待处理的子序列长度为1或者0试停止划分，排序完成。根据上述快速排序的过程可得其递归原理如下:

递归边界:序列的长度为零或1时，无需划分，递归终止；

递归关系:当序列的长度大于1时，则按照一定规则选择一个值作为枢轴进行划分，使枢轴左边的值都小于或等于基准值，枢轴右边的值都大于等等于基准值大。之后递归处理枢轴左右两个子序列。

根据上述关于快速排序的递归解释，可得图10与图11所示的快速排序的递归原理与递归函数。

图10 快速排序图解

图11 快速排序的递归实现

3.5 归并排序

3.5.1 归并排序过程及非递归实现

图12 归并排序的非递归实现

3.5.2 归并排序的递归与分治原理及递归实现

归并排序同样可以从递归和分治的角度理解。当待排序序列长度为1时序列自然有序，此为递归边界；当待排序序列长度大于1时，将该序列从中间平均地一分为二，只要将左右两个子序列分别排序，接下来进行这两个子序列的有序归并即可，如此就将N个数的排序问题归结为了长度约为N/2的两个子序列的排序问题，此即递归关系。根据上述归并排序的递归与分治解释，可得其递归函数的实现以及递归原理如图13和图14所示。

图13 归并排序图解

图14 归并排序的递归实现

4 基于递归与分治的排序性能比较

由图3、图4以及图7所示插入排序、冒泡排序以及选择排序的递归原理可知，这三种排序算法虽然递归与分治的具体方法不同，但在递归的过程中，每次都是将原始长为N的序列的排序问题归结为长度为N-1序列排序问题，它们都需要递归N-1次才能最终到达递归边界，其时间复杂度都是O（N2）。

然而，由图10所示的快速排序的递归原理可见，快速排序一趟划分后，将长度为N的序列排序问题归结为两个长度不确定的子序列排序问题，从而其递归的次数也是不确定的。如果每次枢轴都能将待处理子序列等长的一分为二，则递归最多log2N趟到达递归边界，此时快速排序的时间复杂度最优，能达到O（N log2N）；如果每次划分都使得枢轴一侧子序列长度为0、另一侧子序列长度为N-1，则此时需要递归N-1趟方能达到递归边界，此时快速排序的时间复杂度最坏为O（N2）。

就归并排序而言，由图13所示的递归原理可知，归并排序每趟都将原序列的排序问题归结为长度大致相等的两个子序列的排序，此时最多log2N趟切分即可到达递归边界，所以其时间复杂度恒为O（N log2N）［9］。

综上所述，上述五种排序算法的背后都隐含着递归与分治的解题策略，但是由于递归次数的不同导致了算法性能的不同。在基于递归与分治策略求解问题时，设计的递归关系应使子问题的规模减小的尽量快，越快到达递归边界则算法性能越高。

5 结语

本文从递归与分治的求解策略出发，对直接插入排序、冒泡排序、选择排序、快速排序、归并排序等经典排序算法的排序原理进行了新的解读，由文中分析可见，上述排序算法虽然具体的排序过程以及采用的就排序基本操作不同，有的基于插入，有的基于交换，有的基于选择，有的基于归并，但它们背后都隐含了递归与分治的问题求解策略，而且这些排序算法性能上的不同也可以从递归次数的角度进行统一解释。实际上，现实世界中的问题多种多样，但通用的问题求解策略却往往没有多少，递归与分治就是其中最典型的一个，它不仅可以用于排序，在Strassen矩阵乘法、棋盘覆盖等其他经典问题中也有广泛应用。后续工作中，可以继续探究希尔排序［10～11］、堆排序［12～14］、基数排序［15］等经典排序算法背后隐含的其他问题求解策略。