最近在学数据结构,虽然很早之前就会写归并排序了,不过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所排序好的数据赋值给数组,排序就完成了

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

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

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

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信