归并排序（Merge Sort）是速度仅次于快速排序的稳定算法(关于稳定性上文希尔排序有解释)，是一个很常用的O(nlogn)级别的算法。
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序的名字已经把它的中心思想表达出来了，回归再合并。
假如说现在有两个已经排好序了的数组。现在想把它俩合并成一个数组。该怎么做？
01.png
首先，我们再创建一个数组，长度等于两个数组长度之和。然后我们使用3个标记。红色标记代表我们要比较的两个元素，绿色标记代表比较后要放的位置。
02.png
标记的初始位置都为数组的第一个元素。两个红色标记元素比较后，发现第一个数组的的元素比较小，所以将它赋值给新创建的绿色数组的绿色标记处。
03.png
赋值完成后，将绿色标记自增1。左侧红色标记自增1。
04.png
然后继续比较两个数组红色标记处的元素。此时右侧数组元素小，所以将右侧数组标记处元素赋值给绿色数组的绿色标记处。
05.png
然后将绿色标记自增1后。再将右侧红色标记自增1。
06.png
不断重复上边的步骤，直到将两个数组中某一个数组，遍历完成。
如图：
07.png
左侧数组已经全部遍历完成，此时如果右侧数组有剩余元素没有遍历完，则将他们全部赋值到绿色数组尾部。
08.png
此时两个有序数组合并成一个有序数组的操作就完成了。
我们已经会将两个有序数组合并成一个有序数组了，其实这就是归并排序的中心思想，但由于在合并时多使用了一个副本数组，所以归并排序相比其他排序，在空间复杂度上要大，为O(n)。但是在这个内存不值钱的年代，我们更关心的是速度的快慢，时间才是金钱。所以多占点内存也就不要计较了。
那么对一个无序的数组进行归并排序时具体怎么操作呢？
首先我们将一个很长的数组，分成两半。
09.png
得到左右两个数组，再将它俩分半，得到四个数组。
10.png
以此类推，不断的进行二分操作，直到每个分组里都只有一个元素。所以此时我们就得到了若干个有序数组。(此时你可能会说：废话，每个数组里就一个元素，当然每个都是有序数组)
11.png
然后将每两个有序数组，不断的向上回归合并成一个数组。
12.png
13.png
14.png
整个数组就排序完成了。
好好好，道理你都懂。那接下来，我们用OC的代码来实现一下归并排序。
NSMutableArray * array = [NSMutableArray arrayWithObjects:@8,@7,@6,@5,@4,@3,@2,@1, nil];
//调用排序
[self mergeSortArray:array];
- (void)mergeSortArray:(NSMutableArray *)array {
//创建一个副本数组
NSMutableArray * auxiliaryArray = [[NSMutableArray alloc]initWithCapacity:array.count];
//对数组进行第一次二分，初始范围为0到array.count-1
[self mergeSort:array auxiliary:auxiliaryArray low:0 high:array.count-1];
}
- (void)mergeSort:(NSMutableArray *)array auxiliary:(NSMutableArray *)auxiliaryArray low:(int)low high:(int)high {
//递归跳出判断
if (low>=high) {
return;
}
//对分组进行二分
int middle = (high - low)/2 + low;
//对左侧的分组进行递归二分 low为第一个元素索引，middle为最后一个元素索引
[self mergeSort:array auxiliary:auxiliaryArray low:low high:middle];
//对右侧的分组进行递归二分 middle+1为第一个元素的索引，high为最后一个元素的索引
[self mergeSort:array auxiliary:auxiliaryArray low:middle + 1 high:high];
//对每个有序数组进行回归合并
[self merge:array auxiliary:auxiliaryArray low:low middel:middle high:high];
}
- (void)merge:(NSMutableArray *)array auxiliary:(NSMutableArray *)auxiliaryArray low:(int)low middel:(int)middle high:(int)high {
//将数组元素复制到副本
for (int i=low; i<=high; i++) {
auxiliaryArray[i] = array[i];
}
//左侧数组标记
int leftIndex = low;
//右侧数组标记
int rightIndex = middle + 1;
//比较完成后比较小的元素要放的位置标记
int currentIndex = low;
while (leftIndex <= middle && rightIndex <= high) {
//此处是使用NSNumber进行的比较，你也可以转成NSInteger再比较
if ([auxiliaryArray[leftIndex] compare:auxiliaryArray[rightIndex]]!=NSOrderedDescending) {
//左侧标记的元素小于等于右侧标记的元素
array[currentIndex] = auxiliaryArray[leftIndex];
currentIndex++;
leftIndex++;
}else{
//右侧标记的元素小于左侧标记的元素
array[currentIndex] = auxiliaryArray[rightIndex];
currentIndex++;
rightIndex++;
}
}
//如果完成后左侧数组有剩余
if (leftIndex <= middle) {
for (int i = 0; i<=middle - leftIndex; i++) {
array[currentIndex +i] = auxiliaryArray[leftIndex +i ];
}
}
}
如果觉得作者对哪里的理解有偏差或者其他的优化，希望不吝赐教，留言指正。谢谢支持~
网友评论