归并排序算法

本次我们来谈一下排序算法中的归并排序算法

首先我们来了解一下归并排序的思想：分治法；

分治即分而治之，当我们面对一个较大规模的问题时，想要对这个问题直接求解，发现十分困难，我们发现，这个大问题能分解成若干个很容易求解的小问题，而这些小问题在被解决的同时，原问题也得以求解。我们将一个较大规模问题逐步分解成若干个小问题求解的思想，就是分治法，同时也是递归思想。

归并排序算法就是利用了这种思想。

image.png

例如：有一列无序数据集，我们想要对该数据集进行排序，显然我们似乎无法找到一种很显而易见的方式做到，尤其是当数据规模很大时，问题就变得更为困难。我们理想中的解决方式是如果能直接观察就能得到结果，那就再好不过了。显然，我们做不到这一点，根本原因是数据太多。我们的想法是，若数据少一点，是不是会好很多呢？于是我们将数据集尝试性的一分为二来看看。

image-20200430211807744.png

如上图，我们得到了两个原来数据的规模一半的数据集，如果这两个数据集都是有序该多好啊。如下图：

image-20200430213050359.png

因为如果是这样，则原问题就转换成了将两个有序的数据集合并成一个有序的数据集的问题。我们发现对于这个问题，我们还是很容易做到的。这就好比我们平常玩的扑克牌，举个例子：桌子上有两副有序的牌，我们想要将它合并成一副有序的牌，我们该怎么做呢？很简单，假设两副牌都是小到大的排放，小的在上面，首先，我们从两副牌的顶端，各取一个，然后比较谁大谁小，我们将较小的留在手里，而大的放回原位置不动，然后重复此过程，直到其中的一副牌全部比完，或者两副牌同时比完。如果其中的一副牌先比完了，则剩下的另一副牌也就没不用比了，直接全部放入手中就行了。此时，手中的牌就是合并好后的有序的牌了。

代码实现如下：

void merge(vector<int> &array1, vector<int> &array2, vector<int> &tmp) {
    int leftIndex = 0, rightIndex = 0, tmpIndex = 0;
    while (leftIndex < array1.size() && rightIndex < array2.size()) {
        if (array1[leftIndex] < array2[rightIndex]) {
            tmp[tmpIndex++] = array1[leftIndex++];
        } else {
            tmp[tmpIndex++] = array2[leftIndex++];
        }
    }
    while (leftIndex < array1.size()) {
        tmp[tmpIndex++] = array1[leftIndex++];
    }
    while (rightIndex <= array2.size()) {
        tmp[tmpIndex++] = array2[rightIndex++];
    }
}

这个问题解决了，我们似乎还有一个比较头疼的问题，那就是这两个数据集有序，是我们假设的条件，那么我们进一步的问题就变成了如何将这两个子数据集进行排序的问题。我们发现，这个问题和原问题相比似乎没啥分别，只不过是数据规模小了一半而已。是不是可以尝试将这两个数据集各自再一分为二，拆分成更小的数据集，如果我们运气比较好，这些子数据集刚好是有序的，那么问题不就解决了吗？是的，确实存在这种可能，但是我们不能将问题的解决方式寄托于运气，我们可以一直拆分下去，但是我们始终要面临的一个问题是:拆分到什么程度才能直接确定这些数据集的有序性？答案显而易见，当数据集中只有一个数时，则该数据集肯定是有序的。

image.png

看到上图的图示，我们应该豁然开朗了很多，直接上代码了

void mergeSort(vector<int> &nums, vector<int> &tmp, int left, int right) {
  if (left == right)
    return;
  int mid = (left + right) / 2;
  mergeSort(nums, tmp, left, mid);
  mergeSort(nums, tmp, mid, right);
  merge(nums, tmp, left, mid, right);
}

void merge(vector<int> &nums, vector<int> &tmp, int left, int mid, int right) {
  int leftIndex = left;
  int rightIndex = mid + 1;
  int tmpIndex = 0;
  if (leftIndex <= mid && rightIndex <= right) {
    if (nums[leftIndex] < nums[rightIndex]) {
      tmp[tmpIndex++] = nums[leftIndex++];
    } else {
      tmp[tmpIndex++] = nums[leftIndex++];
    }
  }
  while (leftIndex <= mid) {
    tmp[tmpIndex++] = nums[leftIndex++];
  }
  while (rightIndex <= right) {
    tmp[tmpIndex++] = nums[rightIndex++];
  }
  tmpIndex = 0;
  while (left <= right) {
    nums[left++] = tmp[tmpIndex++];
  }
}