©2020-2024 ioDraw All rights reserved,
Privacy Policy
最近在学数据结构，虽然很早之前就会写归并排序了，不过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所排序好的数据赋值给数组，排序就完成了
大家要深入理解的有三个点，第一个点是分治的思想，第二个点是具体的两个递归如何实现的，第三个点就是合并的时候三个循环所起的作用
这种分而策略如果第一次接触可能有些地方无法理解，这也正是算法的美妙之处，第一写排序方面的博客，如有错误还请见谅，归并排序看着要比快排等排序方式代码量要多，且复杂，不过理解了思想后，一切都是那么顺其自然。
本人对于语法语言的掌握与算法数据结构级别不符，所以还得好好学算法，也是借助这篇博客好好回忆一下归并排序，萌新的话其实也可以尝试理解一下，辅助空间直接使用数组也行，所以理论上来说，刚学完数组的萌新，也可以学这些算法(理论上)。