分治策略在《数据结构》排序中的应用分析
关键词：分治；策略；排序
引言
分治策略是将一个难以直接解决的、复杂的问题分解成多个简单的小问题，进而分而治之，从而达到解决问题的目的，因其实用性受到人们的青睐。在《数据结构》课程的经典排序中，很多排序算法都用到了分治思想，在此分别对直接插入排序、选择排序、快速排序和归并排序四种排序算法，用分治思想进行排序的对比分析，使学习者更深刻的理解分治策略的思想，熟练地把分治策略进行拓展应用。
1、分治策略设计思想
1.1分解
将要解决的比较复杂的原问题，按某种方法分解为若干个规模较小，但与原问题类型相同的子问题[1]。比如，全国诗词大赛，要在全国范围内直接把全国总冠军选拔出来比较困难，于是就用该策略，先分出不同赛区，进行选拔。
1.2求解
若分解出来的子问题还不能直接求解，还需要把子问题按照同样的分治策略继续分解下去，直到分解出来的子问题小到可以独立求解，然后可用简单的方法求解[1]。比如，在不同赛区进行诗词大赛的选拔比赛时，是通过参赛选手的层层选拔，再求解出某个赛区的冠军。
1.3合并
根据原问题的要求，利用计算机不怕重复的特性，将各个子问题自底向上，逐层合并求解出原问题的解[2]。如，将选拔出来的各个赛区的冠军，再进行最后的总决赛，全国总冠军就被选拔出来了。
2、分治策略在排序中的应用
2.1直接插入排序
直接插入排序的思想是将待排序表分成左、右两部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的关键字逐个取出，并插入到左边有序区中的适当位置，以构成新的有序区，直到右边的记录全部插入完为止[3]。用分治策略分析直接插入排序的整个排序过程如下：
（1）分解
将待排序数组A中的n个数据元素分解成两个子表A1和A2，其中把数组A中的第一个数据元素放到子表A1中，把剩下的2～n个数据元素放到子表A2中。
（2）求解
子表A1中因为只放有一个数据元素，所以它已经有序，而子表A2有n-1个数据元素，需要对子表A2按直接插入排序的原则进行不断的分解，直到子表A2中的数据元素分解完为止。
（3）合并
在对子表A2进行不断的分解过程中，就把分解出来的数据元素排列到子表A1表中，因此，合并自然完成。
2.2选择排序
选择排序的思想是，第一次在n个待排序的数据元素中，选择最小关键字与第一个数据元素交换，然后在剩下的n-1个数据元素中选择最小关键字与第二个数据元素交换，依次重复，每次总是在剩下数据元素中选一个最小关键字与第i（i表示排序的趟数）个数据元素交换，直到所有数据排列完成为止[3]。用分治策略分析选择排序的整个排序过程如下：
（1）分解
将待排序数组A中的n个数据元素分解成两个子表A1和A2，开始时A1为空，A2存放待排序的n个数据元素。
（2）求解
分解A2子表，依次将A2子表中最小的关键字找出来放到A1子表中，直到A2子表为空为止。
（3）合并
在对子表A2进行不断的分解过程中，就把分解出来的数据元素排列到子表A1表中，因此，合并自然完成，没有必要再通过合并完成整个排序。
2.3快速排序
快速排序的思想是：首先从待排序列中任选取一个记录作为枢轴，又叫基准值（比如，第一个记录），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键字均小于或等于基准值，后一部分记录的关键字均大于或等于基准值，然后分别对这两部分重复上述操作，直到整个序列有序为止[3]。用分治策略分析快速排序的整个排序过程如下：
（1）分解
在待排序数组A中的n个数据元素，以第一个数据元素为基准元素，将数组A分解成两个子表A1[1..r]和A2[r+1..n]两个子序列，并且要求A1[1..r]的数据元素小于或等于基准值，A2[r+1.. n]中的数据元素大于基准值。快速排序的分解过程也可用如图1所示的示意图表示，其中阴影部分的数据表示第几趟排序时选用的基准值。
（2）求解
调用递归算法，分别对子序列A1和A2进行分解，也就是分别对A1子表和A2子表按上述过程进行不断的分解过程。
（3）合并
由于每个子序列在求解的时候就已经排序完成，没有必要再通过合并完成整个排序。如图1所示，快速排序注重合并，在分解的时候就把相应的数据存放在对应的位置上，因此，省去了合并操作。
2.4归并排序
归并排序思想是：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，……，直至得到一个长度为n的有序序列为止[3]。用分治策略分析归并排序的整个排序过程如下：
（1）分解
将一个具有n个待排序记录的序列分解成规模大致为n/2的两个子序列A1和A2[4]。分解过程用如图2所示的示意图表示。
（2）求解
分别对上述的两个子序列A1和A2进行递归的分解，直到分解到每个子序列的长度为1为止。
（3）合并
因为上面分解和求解两个步骤没有把待排序的数据元素排序出来，还需要在合并中按自底向上进行合并排序，将长度为1的子序列进行两两比较，形成一个长度为2的子序列，然后再将长度为2的子序列两两比较形成长度为4的子序列，如此重复，直到合并为n个长度的序列为止。其合并过程可用如图3所示的示意图表示。
3、四种排序算法对比分析
3.1分解子序列的规模大致相同，排序效率高
使用分治策略进行数据元素排序时，最好使分解的子序列的规模大致相同。比如，直接插入排序和简单的选择排序就是因为所分解的两个子序列不均衡，使得排序算法的时间复杂度为O(n2)，而快速排序和归并排序因所分解的两个子序列比较均衡，排序算法的时间复杂度为O(nlong2n)，排序的效率提高了很多。
3.2注重分解
快速排序属于“吃苦在前享受在后”的思维[1]，特别注重分解过程，在分解子序列时就按元素的大小进行分解，当子序列分解到规模很小的时候，能够自然合并为有序序列，而省去了合并这个过程，提高了排序的效率。
3.3注重合并
归并排序则属于“先享受后吃苦”的理念[1]，特别注重合并的过程，归并排序在分解子序列时，只是形式上将问题规模化小，一下子就把子序列化为长度为1，而没有实质性的排序，因为只是简单的分解，剩下未吃的苦，需要在合并的时候补上，因此，合并的时候需要自底向上进行两两比较排序，直到最终形成有序序列为止。
4、小结
通过分治策略在四种排序算法进行排序过程的详细分析，深刻理解分治策略分而治之的含义，更好的把握分治策略的特性。使用分治策略进行数据元素排序时，最好把子序列分解为大致相同的规模，提高排序效率。在相同效率的快速排序和归并排序算法中，快速排序注重分解，省去了合并过程，而归并排序注重合并，分解只做象征性的处理。
参考文献：
[1]邹恒明.算法之道[M].机械工业出版社.北京：2012:173-178
[2]张铭，赵海燕，王腾蛟，宋国杰.数据结构与算法试验教程[M].高等教育出版社.北京：2011:197-200
[3]杨智明.数据结构（C语言版）[M].北京理工大学出版社.北京：2016:262-278
[4]李六杏.分治策略在归并排序中的算法设计[J].赤峰学院学报（自然科学版），2015(8):21-23
作者简介：杨智明，保山学院信息学院，副教授,硕士，研究方向为计算机教育研究。