[C++]【超详细归并排序实现原理剖析】

超详细归并排序实现原理剖析

• 前言
• 引子
• 合并有序数组与虚拟指针
• • 图示合并过程
  • 核心代码
• 归并的实现与剖析
• • 图解归并过程
  • 核心代码以及代码解析
• LeetCode—912.排序数组

---

前言

   	献给正在寻找答案的我和你

引子

在正式的去了解归并排序的实现原理之前首先得知道归并排序它所能实现的功能，简单来说就是将一个数组按照某种逻辑顺序进行重组的过程。与此同时还应该认识到在进行顺序排序或者逆序排序的过程其实就是消除逆序对，或者顺序对的一个过程。归并排序总的来说就是一个递归的过程，只不过在去思考这个递归的时候，我们要去思考将大的模块拆分成什么样的子模块，在进行递这一个过程时，需要获得怎样的效果，在归的时候，需要怎样的动作来帮助我们去得到怎样的一个结果。这就是归并排序的一个核心思维，也是递归的思考方式。

合并有序数组与虚拟指针

在去思考归并之前，我们不妨来思考一下怎样去合并两个有序的数组？

1. 例如现在有两个数组一个叫nums1[ ]={0,1,2,3}; 一个叫nums2[ ]={4,5,6,7,8};我们怎么去将这两个有序数组合并成为一个新的有序数组tmp[ ]呢？

2. 既然这两个数组已经是有序的了，那么这两个数组的第一个元素一定分别为两个数组中最小的元素，那么将这两个首元素进行比较，将更小者保存在另外一个新的数组中，同时将其从原数组中扣掉，那么这个时候新数组所保存的那个元素就一定是这两个数组中最小者。并且我们将更小者从原数组扣掉后，会发现这两个数组的第一个元素依旧是这两个数组的最小元素。因此我们就可以重复以上步骤，一直将两个数组中的最小者放入新的数组中去，直到某个数组被放空。由于每一次放的都是两个数组的最小值那么因此可以得知剩余数组中的元素一定是两个数组中的更大的值，并且数组又是有序的，所以可以直接将剩余的元素放进新的数组中去，这样就能的得到一个合并后的有序数组。（过程可看图解）

虚拟指针

那么怎么去从数组中扣掉那第一个元素呢？当两个数组元素大小相同时怎么处理呢？

• 其实换句话来说就是，怎样能精准的去 *** 控数组中的元素呢？这里就将引入虚拟指针这个概念。什么是虚拟指针呢？虚拟指针和传统意义上的指针有什么区别呢？虚拟指针和传统指针不一样，它并不是直接的去指向那个元素所存储的物理位置，无论你怎样去 *** 作虚拟指针都不能直接的对指向的元素造成直接的影响。虚拟指针其实是我们独立去创造的一个变量，这个变量所存储的是一个位置，这个位置所指向的是当前数组的元素所对应的下标。所以回过来再看看我们怎样去扣掉那第一个元素呢？或者说真的去扣掉它了吗？很显然并没有，我们只是通过改变虚拟指针的大小来越过了数组中的第一个元素。这是什么意思呢？（可以结合图示来理解）我们通过这个例题来说一下，我们现在定义了三个虚拟指标i,j,k。它们的初始值都是0，表示的意思为目前i，j，k作为虚拟指针指向的位置是各个数组下标为0的位置以及在那个位置的元素，nums1[i]所指向的元素为‘0’，nums2[j]所指向的的元素为‘4’。这时候去执行刚才的思考过程，将nums1[i]和nums[j]去比大小，然后将小的那个元素放到tmp[ ]的第一个位置，也就是目前k所指向的那个位置tmp[k]。现在我们要做的就是去越过数组的第一个元素，让数组的第二个元素去比较大小，那么我们就可以通过去移动虚拟指针i，让i去前进一位（i++）去指向第二个元素的下标，同时我们要让虚拟指针k去前进一位（k++），这样就能使第二次比较大小所得的更小值，去存放在tmp[ ]数组中的第二位。然后循环往复，直到某个数组被拿空。之后再将剩余的数依次放在那个时候虚拟指针k所指向的下标的下一位。这样我们就完成了两个有序数组的合并。

图示合并过程

核心代码

	  int mid=nums1.size();//求数组的长度
	  int r=nums2.size();
	while (i < mid+1 && j <r+1) {//判断是否又有数组被拿空
		if (arr[i] <= arr[j]) 
			tmp[k++] = arr[i++];//通过 *** 作虚拟指针去填补tmp[]
		else tmp[k++] = arr[j++];
	}
	while (i < mid+1) tmp[k++] = arr[i++];//将剩余的数补入tmp[]
	while (j < r+1) tmp[k++] = arr[j++];

归并的实现与剖析

归并排序就是完成递归的一个过程

通过刚才对合并两个有序数组的了解，可以得知两个有序的数组可以合并为一个有序的数组。那么如果现在有一个无序的数组nums[ ]={1,4,3,6,9,2,6}，我们能否通过将其拆分成两个无序的数组，然后将其进行排序最后在重新组合成为一个有序的数组nums[ ]={1,2,3,4,6,6,9}呢？

- 归并的实现主要分为三个部分：

1. 通过递的过程去将一个数组拆分成无数个小的数组，重复的对数组进行二分分解，将一个数组分解为两个数组，直到所分解得到的每一个数组中都只有一个元素为止。这样我们就不用考虑数组是否有序，因为当两个数组都只有一个元素的话就可以直接去做合并排序然后将得到的结果保存在一个新的数组tmp[ ]中去，此时的tmp[ ]中所保存的元素就一定是有序的了。那么怎么去实现将一个数组去拆分成这样符合要求的小数组呢？通过观察图解可以看出，每一次二分我们都能得到以中点为界左右两个数组，然后再去对每个数组进行二分，区别只是二分的左右节点不一样。 那么我们可以去设计一个函数让他每次完成了二分之后再去调用那个函数再去二分，只不过每一次二分所传入的参数不同，直到当前数组的长度为1的时候截止。
2. 在归的过程中将拆分好的元素按照某种逻辑进行重组排序（例如顺序，或者逆序）。当我们发现当前数组长度为1时，我们便结束当前函数，返回到你调用函数的地方，去执行之后的语句。那么现在我们已经获得了两个有序的数组，现在我们只需要对这个有序的数字组合并放在tmp[ ]中去。
3. -将已经排好序的新的数组去替换原数组，然后层层返回直到第一次调用函数的地方去。

图解归并过程

核心代码以及代码解析

void merge_sort(int l,int r) {//传入原数组的左右下标
	int len = r - l + 1;//求当前递归区间长度 
	int mid = l + (r - l) / 2;//二分节点 
	if (len=1) return;//递归边界 
	merge_sort(l, mid);//递归左半边 
	merge_sort(mid + 1, r);//递归右半边 
	int i = l, j = mid+1, k = 0;
	int tmp[len];
	while (i < mid+1 && j <r+1) {//合并有序数组
		if (arr[i] <= arr[j]) 
			tmp[k++] = arr[i++];
		else tmp[k++] = arr[j++];
	}
	while (i < mid+1) tmp[k++] = arr[i++];
	while (j < r+1) tmp[k++] = arr[j++];
	for (int i = 0; i < len; i++) arr[i + l] = tmp[i];//将排序好的tmp覆盖原arr数组 
}

LeetCode—912.排序数组

class Solution {
public:
    int n;
    vector<int> arr;
    void merge_sort(int l, int r)
    {
        int len=r-l+1;
        int mid=l+(r-l)/2;
        if(len>1){
            merge_sort(l,mid);
            merge_sort(mid+1,r);
        }
        else return;
        int tmp[len];
        int k=0;
        int i=l;
        int j=mid+1;
        while(i<=mid && j<=r){
            if(arr[i]<=arr[j])  tmp[k++]=arr[i++];
            else    tmp[k++]=arr[j++];
        }   
        while(i<=mid) tmp[k++]=arr[i++];
        while(j<=r) tmp[k++]=arr[j++];
        for(i=0; i<len; i++) arr[i+l]=tmp[i];
    }
    vector<int> sortArray(vector<int>& nums) {
        n=nums.size();
        arr=nums;
        merge_sort(0,n-1);
        return arr;
    }
};