C++学习记录算法篇—归并排序

C++学习记录算法篇—归并排序

一、归并排序：

归并排序利用了分治思想，即把大问题先拆分为小问题，对小问题进行求解，最后合并成大问题的解。在归并排序中体现为：先把数组拆分为许多小数组，对小数组进行排序，再把有序的小数组合并成有序的大数组。

二、归并排序的实现：

1. 首先是归并排序的入口，在这个入口创建临时数组，并进行划分，最后在排序完成后删除临时数组

   void merge_sort(int arr[],int n)
   {
   	//首先分配辅助数组
   	int* tempArr = new int[n];
   	//分配完，进行数组的划分
   	msort(arr, tempArr, 0, n - 1);
   	//排序完后，删除临时数组
   	delete tempArr;
   	return;
   }

2. 接下来是数组的划分，传入的参数为：

   1. 欲划分的数组
   2. 临时数组
   3. 划分的起点（最开始是0）
   4. 划分的终点（最开始是n-1）

   首先一直划分数组，直到每个小数组只有一个元素，这是一个递归的过程

   划分数组后，进入合并阶段

   void msort(int arr[], int tempArr[], int left, int right)
   {
   	//如果数组只有一个元素，那么就不需要划分，因为一个元素的数组一定是有序的,只需要被归并
   	if (left < right)
   	{
   		//首先找到中间点
   		int mid = (left + right) / 2;
   		//然后以中间点为界，左右继续划分，这是一个递归的过程
   		msort(arr, tempArr, left, mid);
   		msort(arr, tempArr, mid + 1, right);
   		//接下来是合并阶段，传入左边的下标，中间点和右边的下标
   		merge(arr, tempArr, left, mid, right);
   	}
   	else return;
   }

3. 合并阶段：传入的参数为：

   1. 欲排序的数组
   2. 临时数组
   3. 合并的起点
   4. 合并的中间点（因为划分为了左右两段）
   5. 合并的终点

   void merge(int arr[], int tempArr[], int left, int mid, int right)
   {
   	//标记左半区第一个未排序的元素
   	int lpos = left;
   	//标记右半区第一个未排序的元素
   	int rpos = mid + 1;
   	//标记临时数组的下标
   	int temPos = left;
   
   	//下面开始合并
   	while (lpos <= mid && rpos <= right)
   	{
   		if (arr[lpos] <= arr[rpos])//如果左边更小，先放左边
   		{
   			tempArr[temPos++] = arr[lpos++];
   		}
   		else//右边更小同理
   		{
   			tempArr[temPos++] = arr[rpos++];
   		}
   	}
   	//合并左半区剩余的元素
   	while (lpos <= mid)
   	{
   		tempArr[temPos++] = arr[lpos++];
   	}
   	//合并右半区剩余的元素
   	while (rpos <= right)
   	{
   		tempArr[temPos++] = arr[rpos++];
   	}
   	//把合并后的元素拷贝到原来的数组
   	while (left <= right)
   	{
   		arr[left] = tempArr[left];
   		left++;
   	}
   
   	return;
   }

三、归并排序的时间复杂度为O（nlog2n【以2为底，n的对数】）

​ 空间复杂度为：O（n）（因为开了临时数组）

​ 在此文档中，合并的判断条件使用了<=,因此这里的归并排序是稳定的