排序算法--归并排序

排序步骤分析

归并排序的思想：将两个有序的数组合并成一个有序的数组。

第一步：将数组进行分解，当分解成单个元素为一组的时候，才是组内有序的。

第二步：将两两有序的数组进行合并，将两个有序的数组合并成一个有序数组。重复第二步，直至排序完成。

合并的步骤：先申请两个数组合并后那么大小的空间，然后将两个排好序的数组逐一进行比较，往申请空间里面放。

---

合并思想练习

给定两个大小分别为m和n的正序数组nums1和nums2，找中位数并返回。

函数声明：int findMidNum(vector<int>& nums1,vector<int>& nums2)

范围确定：m=nums1.size();n=nums2.size(); 

声明新数组vector<int> ans(m+n);

int findMidNum(vector<int>& nums1,vector<int>& nums2){
    int m=nums1.size();
    int n=nums2.size();
    vector<int> ans(m+n);
    
    int idx=0;//结果数组的下标从0开始
    int lf=0,rt=0;
    //lf(left)左子数组的开始下标，rt(right)右子数组的开始下标
    while(lf<m&&rt<n){
        if(nums1[lf]<=nums2[rt]) ans[idx++]=nums1[lf++];
        else ans[idx++]=nums2[rt++];
    }
    while(lf<m) ans[idx++]=nums1[lf++];//如果左子数组没有放完剩下的就全放进去
    while(rt<n) ans[idx++]=nums2[rt++];//如果右子数组没有放完剩下的就全放进去
    //因为本来两个数组就有序
    
    if((m+n)%2==0) return ans[(m+n)/2]+ans[(m+n)/2 + 1];
    else return ans[(m+n)/2];
}

---

代码过程分析

确定传入的参数：

1.待排序的数组

2.排序的左边界在数组中的绝对位置

3.排序的右边界在数组中的绝对位置

void MergeSort(vector<int>& v,int left,int right)

首先是寻找基线条件：当数组元素个数为1时，有序，开始合并，否则分解

if(left==right)return;

没有返回：到达该步，找到中间值，开始分解

int mid=(right-left)/2+left;

MergeSort(v,left,mid);

MergeSort(v,mid+1,right);

分解完了，一 一合并

merg(v,left,mid,right);

合并代码实现

	void merg(vector<int>& v, int left, int mid, int right) {
 
		int len = right - left + 1;//确定合并数组总长度
		vector<int> tmp(len);//开辟合并数组
 
		int i = left; int j = mid + 1;//两个子数组的开始下标
		int index = 0;//合并数组的当前下标
		while (i <= mid && j <= right) {//如果两个子数组均有值
			if (v[i] <= v[j]) tmp[index++] = v[i++];
			else if (v[i] > v[j]) tmp[index++] = v[j++];
		}
		while (i <= mid) {
			tmp[index++] = v[i++];
		}//如果第一个子数组有剩余，将剩余的数据全部放入
		while (j <= right) {
			tmp[index++] = v[j++];
		}//如果第二个子数组有剩余，将剩余的数据全部放入
 
		index = left;//原始数组从合并操作的左边界开始被赋值
        //这样的话，一个个子区间都是确定有序的
        //直到最后一次合并，全部有序
		for (int i = 0; i < len; i++) {
			v[index++] = tmp[i];
		}
	}

算法分析

时间复杂度：O(nlogn)

稳定性：稳定

---

感谢大家！