CC++归并排序

最近在学数据结构，虽然很早之前就会写归并排序了，不过std::sort用多了，不怎么记得了，那我们今天就再讲讲归并排序

归并排序时间复杂度O(nlogn),空间复杂度O(n),稳定，是分治策略，序列一分为二O(1)，子序列递归排序2*T(n/2)，合并有序序列O(n)

 实现代码如下:

void merge(int arr[], int start, int end, int mid, int* temp) {
		int i_start = start;
		int i_end = mid;
		int j_start = mid + 1;
		int j_end = end;

		int Length = 0;
		while (i_start <= i_end && j_start <= j_end) {
			if (arr[i_start] < arr[j_start])
				temp[Length++] = arr[i_start++];
			else
				temp[Length++] = arr[j_start++];
		}
		while (i_start <= i_end) {
			temp[Length++] = arr[i_start++];
		}
		while (j_start <= j_end) {
			temp[Length++] = arr[j_start++];
		}
		for (int i = 0; i < Length; i++) {
			arr[start + i] = temp[i];
		}
	}
	void mergeSort(int arr[], int start, int end, int* temp) {
		if (start >= end) {
			return;
		}
		int mid = (start + end) / 2;
		mergeSort(arr, start, mid, temp);
		mergeSort(arr, mid + 1, end, temp);
		merge(arr, start, end, mid, temp);
	}

我们先看mergeSort这个函数，我们是调用它来进行归并排序

首先函数是一个void无反，参数是一个需要排序的数组arr，start数组开始位置，end数组结束位置，*temp是我们需要传入一个辅助空间

1、首先判断if(start>=end)那么就没必要计算，比如start是5，end也是5，或者start是6，end是5，就return;

2、创建mid，表示中间值，mid=(start+end)/2;

3、调用自身进行递归 mergeSort(arr, start, mid, temp);开始位置还是start，结束变为mid中，其他参数不变，先向左进行递归，也就是开头提到的序列一分为二，直到到递归基，分解成第一个图一样的时候，才可以进行下一步。如果对递归不熟悉的话，还请自行先了解

4、当第三步完成到递归基的时候，从最后一个也就是触发退出条件销栈的if(start>=end)，就会返回到上一个函数，那么也意味着从反方向开始调用第二个mergeSort(arr, mid + 1, end, temp);我们可以注意到第二个mergeSort对于第二和第三个参数是有变化的，用mid+1做start，end做end，也就是正常的对序列另一边做处理，就会和第三步一样进行递归的处理，直到触发结束的条件，就会从退到最后一个调用mergeSort(arr, mid + 1, end, temp);的函数，也就表示，前面两步的分解全部完成，就到了最后一步也就是代码表示最麻烦的一步。

5、调用merge函数进行合并，这是最后一步也是自己手动编写最为麻烦的一段，细看函数是一个void的无反函数，有着五个参数，为数组arr，start位置，end位置，mid位置，*temp辅助空间，先直接一股脑的传递参数即可merge(arr, start, end, mid, temp);

6、  int i_start = start;
        int i_end = mid;
        int j_start = mid + 1;
        int j_end = end;

        int Length = 0;

四个变量分别记录着两个序列的开头与结尾，i与j开头表示的不同的两个序列，Length长度。

while (i_start <= i_end && j_start <= j_end) {
            if (arr[i_start] < arr[j_start])
                temp[Length++] = arr[i_start++];
            else
                temp[Length++] = arr[j_start++];
        }

while循环条件要求要求左边序列i的start位置小于或等于end位置，右边序列j同理

进入循环:if (arr[i_start] < arr[j_start]) temp[Length++] = arr[i_start++];即如果数组arr[i序列的start位置]<数组arr[j序列的位置]，temp辅助空间的[Length++]被赋值为arr数组[i序列位置的开始++]的值，虽然听着有点绕，但是实际上就是i和j序列比大小，谁小谁赋值给temp(因为是升序)，++写在里面可以减少代码量，其实还有一句else。else temp[Length++] = arr[j_start++];相信也不需要我们再解释了。我们看第一张图的最后两行来理解这个循环的具体行为，以及如何退出。

7、在第一个循环的时候，i或者j序列有数据没有被放入temp，后面两个循环正是为了解决这个问题，也就是说为了处理数组为奇数的情况，我们再放一张图帮助大家理解

8、最后一个循环的作用是把辅助空间temp所排序好的数据赋值给数组，排序就完成了

大家要深入理解的有三个点，第一个点是分治的思想，第二个点是具体的两个递归如何实现的，第三个点就是合并的时候三个循环所起的作用

 这种分而策略如果第一次接触可能有些地方无法理解，这也正是算法的美妙之处，第一写排序方面的博客，如有错误还请见谅，归并排序看着要比快排等排序方式代码量要多，且复杂，不过理解了思想后，一切都是那么顺其自然。

 本人对于语法语言的掌握与算法数据结构级别不符，所以还得好好学算法，也是借助这篇博客好好回忆一下归并排序，萌新的话其实也可以尝试理解一下，辅助空间直接使用数组也行，所以理论上来说，刚学完数组的萌新，也可以学这些算法(理论上)。