归并排序和快速排序都用到了分治思想，非常巧妙。我们可以借鉴这个思想，来解决非排序的问题。
归并排序
归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好的两部分合并在一起，这样整个数组就都有序了。
归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
从我刚才的描述，你有没有感觉到，分治思想跟我们前面讲的递归思想很像。是的，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。
分治算法的思想我后面会有专门的一节来讲，现在不展开讨论，我们今天的重点还是排序算法。
前面我通过举例让你对归并有了一个感性的认识，又告诉你，归并排序用的是分治思想，可以用递归来实现。我们现在就来看看如何用递归代码来实现归并排序。
写递归代码的技巧就是，分析得出递推公式, 然后找到终止条件，最后将递推公式翻译成递归代码。所以，要想写出归并排序的代码，我们先写出归并排序的递推公式。
递推公式：
merge_sort(p…r) = (merge_sort(p…q), merge_sort(q+1…r))
终止条件：
p >= r 不用再继续分解
我来解释一下这个递推公式。
merge_ sort(...r) 表示，给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问题，merge_ sort(...q) 和merge_ sort(q+1...r), 其中下标q等于p和r的中间位置，也就是(p+r)/2。当下标从p到q和从q+1到r这两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样下标从p到r之间的数据就也排好序了。
有了递推公式，转化成代码就简单多了。
#pragma mark -
#pragma mark 归并排序
- (void)gly_mergeSort:(NSString *)propertyName result:(NSComparisonResult)result
{
[self gly_mergeSortPropertyName:propertyName result:result p:0 r:self.count - 1];
}
- (void)gly_mergeSortPropertyName:(NSString *)propertyName result:(NSComparisonResult)result p:(NSInteger)p r:(NSInteger)r
{
if (p >= r)
{
return;
}
NSInteger q = (p + r) / 2;
// 分治递归
[self gly_mergeSortPropertyName:propertyName result:result p:p r:q];
[self gly_mergeSortPropertyName:propertyName result:result p:q + 1 r:r];
// 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
[self gly_mergePropertyName:propertyName result:result p:p r:r];
}
你可能已经发现了，[self gly_mergePropertyName:propertyName result:result p:p r:r];这个函数的作用就是，将已经有序的A[p...q]和A[q+1...r] 合并成一个有序的数组，并且放入A[p...r]。 那这个过程具体该如何做呢?
如图所示，我们申请一-个临时数组tmp,大小与A[p...r] 相同。我们用两个游标i和j，分别指向A.p...q]和A[q+1...r] 的第一个元素。比较这两个元素A[i] 和A[j],如果A[i]<=A[j],我们就把A[i]放入到临时数组tmp,并且i后移-位，否则将A[j] 放入到数组tmp, j 后移-位。
继续上述比较过程，直到其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组tmp中的数据拷贝到原数组Ap..r]中。
下面是合并方法
- (void)gly_mergePropertyName:(NSString *)propertyName result:(NSComparisonResult)result p:(NSInteger)p r:(NSInteger)r
{
NSInteger q = (p + r) / 2;
NSInteger i = p;
NSInteger j = q + 1;
NSInteger k = 0;
NSMutableArray *tempArray = [NSMutableArray array];
while (i <= q && j <= r)
{
NSNumber *numberOne = [self[i] valueForKey:propertyName];
NSNumber *numberTwo = [self[j] valueForKey:propertyName];
if ([numberOne compare:numberTwo] == result)
{
[tempArray insertObject:self[j++] atIndex:k++];
}
else
{
[tempArray insertObject:self[i++] atIndex:k++];
}
}
// 判断哪个子数组中有剩余的数据
NSInteger start = i;
NSInteger end = q;
if (j <= r)
{
start = j;
end = r;
}
// 将剩余的数据拷贝到临时数组 tmp
while (start <= end)
{
[tempArray insertObject:self[start++] atIndex:k++];
}
// 将 tmp 中的数组拷贝回 A[p...r]
[self replaceObjectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(p, r - p + 1)] withObjects:tempArray];
}
归并排序的性能分析
这样跟着我一步一步分析，归并排序是不是没那么难啦?还记得上节课我们分析排序算法的三个问题吗?接下来，我们来看归并排序的三个问题。
第一，归并排序是稳定的排序算法吗?
结合我前面画的那张图和归并排序的伪代码，你应该能发现，归并排序稳不稳定关键要看merge()函数，也就是两个有序子数组合并成一个有序数组的那部分代码。
在合并的过程中，如果Ap...q]和A[+1...r]之间有值相同的元素,那我们可以像伪代码中那样,先把A[p...q]中的元素放入tmp数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。
第二，归并排序的时间复杂度是多少?
归并排序涉及递归，时间复杂度的分析稍微有点复杂。我们正好借此机会来学习一下，如何分析递归代码的时间复杂度。
在递归那一节我们讲过，递归的适用场景是，一个问题a可以分解为多个子问题b、c,那求解问题a就可以分解为求解问题b、c。问题b、c解决之后，我再把b、c的结果合并成a的结果。
如果我们定义求解问题a的时间是T(a),求解问题b、c的时间分别是T(b)和T( c),那我们就可以得到这样的递推关系式:
T(a) = T(b) + T(c) + K
其中K等于将两个子问题b、c的结果合并成问题a的结果所消耗的时间。
从刚刚的分析，我们可以得到一个重要的结论:不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。
套用这个公式，我们来分析一下归并排序的时间复杂度。
我们假设对n个元素进行归并排序需要的时间是T(n),那分解成两个子数组排序的时间都是T(n/2)。我们知道，merge() 函数合并两个有序子数组的时间杂度是O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是:
T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1
通过这个公式，如何来求解 T(n) 呢？还不够直观？那我们再进一步分解一下计算过程。
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......
= 2^k * T(n/2^k) + k * n
......
通过这样一步一步分解推导，我们可以得到T(n) = 2kT(n/2k)+kn。当T(n/2k)=T(1)时，也就是n/2k=1,我们得到k=log2n。我们将k值代入上面的公式，得到T(n)=Cn+nlog2n。如果我们用大0标记法来表示的话，T(n) 就等于O(nlogn)。所以归并排序的时间复杂度是O(nlogn)。
从我们的原理分析和伪代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是O(nlogn)。
第三，归并排序的空间复杂度是多少?
归并排序的时间复杂度任何情况下都是O(nlogn),看起来非常优秀。(待会儿你会发现， 即便是快速排序，最坏情况下，时间复杂度也是O(n2)。)但是，归并排序并没有像快排那样，应用厂泛，这是为什么呢?因为它有一个致命的“弱点”，那就是归并排序不是原地排序算法。
这是因为归并排序的合并函数，在合并两个有序数组为一一个有序数组时，需要借助额外的存储空间。这一点你应该很容易理解。那我现在问你，归并排序的空间复杂度到底是多少呢?是O(n),还是O(nlogn),应该如何分析呢?
如果我们继续按照分析递归时间复杂度的方法，通过递推公式来求解，那整个归并过程需要的空间复杂度就是O(nlogn)。不过，类似分析时间复杂度那样来分析空间复杂度，这个思路对吗?
实际上，递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最重要的一点，那就是，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过n个数据的大小，所以空间复杂度是O(n)。
快速排序
我们再来看快速排序算法(Quicksort) ，我们习惯性把它简称为“快排”。快排利用的也是分治思想。乍看起来，它有点像归并排序，但是思路其实完全不一-样。我们待会会讲两者的区别。现在，我们先来看下快排的核心思想。
快排的思想是这样的:如果要排序数组中下标从p到r之间的一-组数据，我们选择p到r之间的任意一个数据作为pivot (分区点)。
我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一-步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot,后面的q+1到r之间是大于pivot的。
根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。
如果我们用递推公式来将上面的过程写出来的话，就是这样：
递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
终止条件：
p >= r
我将递推公式转化成递归代码。
#pragma mark -
#pragma mark 快速排序
- (void)gly_quickSort:(NSString *)propertyName result:(NSComparisonResult)result
{
[self gly_quickSortPropertyName:propertyName result:result p:0 r:self.count - 1];
}
- (void)gly_quickSortPropertyName:(NSString *)propertyName result:(NSComparisonResult)result p:(NSInteger)p r:(NSInteger)r
{
if (p >= r)
{
return;
}
NSInteger q = [self gly_partitionPropertyName:propertyName result:result p:p r:r];
[self gly_quickSortPropertyName:propertyName result:result p:p r:q - 1];
[self gly_quickSortPropertyName:propertyName result:result p:q + 1 r:r];
}
归并排序中有一个[self gly_mergePropertyName:propertyName result:result p:p r:r]合并函数，我们这里有一个[self gly_partitionPropertyName:propertyName result:result p:p r:r]分区函数。分区函数实际上我们前面已经讲过了，就是随机选择一个元素作为pivot (一般情况下，可以选择p到r区间的最后一个元素)，然后对A[p...r] 分区，函数返回pivot的下标。
如果我们不考虑空间消耗的话，partition() 分区函数可以写得非常简单。我们申请两个临时数组X和Y,遍历Ap...r],将小于pivot的元素都拷贝到临时数组X，将大于pivot的元素都拷贝到临时数组Y,最后再将数组X和数组Y中数据顺序拷贝到A[p...r]。
但是，如果按照这种思路实现的话，分区函数就需要很多额外的内存空间，所以快排就不是原地排序算法了。如果我们希望快排是原地排序算法，那它的空间复杂度得是0(1)，那分区函数就不能占用太多额外的内存空间，我们就需要在A[p...r]的原地完成分区操作。
原地分区函数的实现思路非常巧妙，我们一起来看一下。
- (NSInteger)gly_partitionPropertyName:(NSString *)propertyName result:(NSComparisonResult)result p:(NSInteger)p r:(NSInteger)r
{
NSNumber *pivot = [self[r] valueForKey:propertyName];
NSInteger i = p;
for (NSInteger j = p; j < r; j++)
{
NSNumber *tempNumber = [self[j] valueForKey:propertyName];
if ([pivot compare:tempNumber] == result)
{
[self exchangeObjectAtIndex:i withObjectAtIndex:j];
i++;
}
}
[self exchangeObjectAtIndex:i withObjectAtIndex:r];
return i;
}
这里的处理有点类似选择排序。我们通过游标i把A[p...r-1]分成两部分。A[p...i-1] 的元素都是小于pivot的，我们暂且叫它“已处理区间”，A[..r-1] 是“未处理区间”。我们每次都从未处理的区间A.[...r-1]中取一-个元素A[j]，与pivot 对比，如果小于pivot,则将其加入到已处理区间的尾部，也就是A[i]的位置。
在数组某个位置插入元素，需要搬移数据，非常耗时。当时我们也讲了一种处理技巧，就是交换，在0(1)的时间复杂度内完成插入操作。这里我们也借助这个思想，只需要将A[i]与A[j]交换，就可以在0(1)时间复杂度内将A[j]放到下标为i的位置。
文字不如图直观，所以我画了一张图来展示分区的整个过程。
因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列6，8, 7, 6, 3, 5, 9,4，在经过第一-次分区操作之后，两个6的相对先后顺序就会改变。所以，快速排序并不是一-个稳定的排序算法。
到此，快速排序的原理你应该也掌握了。现在，我再来看另外-个问题:快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢?
可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由.上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为O(nlogn)的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法,主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
快速排序的性能分析
现在，我们来分析一下快速排序的性能。我在讲解快排的实现原理的时候，已经分析了稳定性和空间复杂度。快排是一-种原地、不稳定的排序算法。现在，我们集中精力来看快排的时间复杂度。
快排也是用递归来实现的。对于递归代码的时间复杂度，我前面总结的公式，这里也还是适用的。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，快排的时间复杂度也是O(nlogn)。
T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1
但是，公式成立的前提是每次分区操作，我们选择的pivot都很合适，正好能将大区间对等地一分为二。但实际上这种情况是很难实现的。
我举一个比较极端的例子。如果数组中的数据原来已经是有序的了，比如1, 3, 5, 6, 8。如果我们每次选择最后- -个元素作为pivot,那每次分区得到的两个区间都是不均等的。我们需要进行大约n次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约n/2个元素，这种情况下，快排的时间复杂度就从0(nlogn)退化成了0(n2)。
我们刚刚讲了两个极端情况下的时间复杂度，一个是分区极其均衡，一个是分区极其不均衡。它们分别对应快排的最好情况时间复杂度和最坏情况时间复杂度。那快排的平均情况时间复杂度是多少呢?
我们假设每次分区操作都将区间分成大小为9:1的两个小区间。我们继续套用递归时间复杂度的递推公式，就会变成这样:
T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = T(n/10) + T(9*n/10) + n； n>1
这个公式的递推求解的过程非常复杂，虽然可以求解，但我不推荐用这种方法。实际上，递归的时间复杂度的求解方法除了递推公式之外，还有递归树，在树那一节我再讲，这里暂时不说。我这里直接给你结论: T(n) 在大部分情况下的时间复杂度都可以做到O(nlogn),只有在极端情况下，才会退化到O(n2)。而且，我们也有很多方法将这个概率降到很低，如何来做?我们后面章节再讲。
最后：
自己写了一个NSMutableArray+GLYSort算法分类，只需1行代码，即可完成复杂排序操作。
