文档介绍：1
作者简介：汪晓阳(1989—)，男,安徽休宁县人，安徽中医学院本科生，09医软一班，学号：09713037；
基于分治和递归策略的排序算法及实现
汪晓阳
(安徽中医学院医药信息工程学院，安徽合肥230031)
摘要：对关键n)与其前两项的关系，我们称之为递归体。一般地，一个递归模型是由递归出口和递归体两部分构成的，前者确定递归到何时结束，后者确定递归的方式。递归设计是把一个不能或不好直接求解的“大问题”转化为一个或几个“小问题”，再把这些“小问题”进一步分解为更小的“小问题”来解决，即通过分解使问题的规模逐渐降低，直至每个小问题都可以直接解决(此时分解到递归出口)。当然，递归分解不是随意地分解，递归分解要保证“大问题”与“小问题”规模不同但模型相似。
4
作者简介：汪晓阳(1989—)，男,安徽休宁县人，安徽中医学院本科生，09医软一班，学号：09713037；
2
作者简介：汪晓阳(1989—)，男,安徽休宁县人，安徽中医学院本科生，09医软一班，学号：09713037；
6
任何一个可以用计算机求解的问题所需的求解时间都与其规模有关。问题的规模越小，解题所需的计算时间往往也越少，从而也更加容易处理。但有时候要想直接解决一个较大的问题，可能是比较困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的问题，分割出的各个小问题与原问题类型相同但规模较小，这样便于各个处理，分而治之。如果原问题可分割成k个子问题，1vkWn,且这些子问题都可解，并可以利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
1问题的提出
在实际问题中我们经常会遇到这样的情况，即要求排序的记录的关键字数量相对于记录数来说是较少的。例如，要对某次考试的考生按考试成绩排名，考试成绩按百分制，参加考试的考生可能有几百人甚至上千人或更多，这种情况下记录关键字的数量相对于记录数来说就非常有限。对于这种具有特殊性质的记录进行排序，用原有的一些经典的排序算法实现效率不一定高。对一些特殊问题的处理我们可以在经典排序算法的基础上进行改进并实现。
2算法分析
考虑到关键字的数量较少，而记录数较多的特殊情况，如果我们在排序交换时尽可能地做到使两条记录同时到位，则交换次数肯定会减少。
若要将序列排成非递减序列，关键字小的记录则最终应该处在序列的前半部分，而关键字大的记录最终应该处在序列的后半部分。我们先对待排序序列处理一遍，将整个序列分成两部分，即关键字小的记录都在第一部分中，关键字大的记录都在第二部分中，即将原序列分为两个较小的序列。这样，原序列经过分治处理后就变成了两个相似序列，而两个序列的规模都变小了，这一就可以对前后两部分进行递归处理。
为此，我们可以按如下方法进行排序：假设a[low„high]是一维数组,让变量mid=（low+high）/2；指针i、j作为控制搜索的变量，指针i用来在记录的前半部分搜索，指针j用来在记录的后半部分搜索；指针frontMax用来记录数组前半部分中关键字值最大的位置，每次搜索其初始值都为low，指向第一个记录位置；指针backMin用来记录数组后半部分中关键字值最小的位置，每次搜索时其初始值都为hig