iOS/OC:归并排序的图解和实现

归并排序（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 ];
    }
  }
 }

如果觉得作者对哪里的理解有偏差或者其他的优化，希望不吝赐教，留言指正。谢谢支持~