【算法学习笔记/C语言】归并排序
（初学算法，希望得到各位的指正）# 归并排序的主要思想
**归**——将数组分成两部分，分别进行排序。
**并**——将已经排序的两个数组合并起来。
“并”的部分对于我而言有点难以理解，接下来的重点会放在“并”上面。
# 代码实现——步骤一
第一步就是使用递归将数组二分，关键在于利用下标实现二分操作。
```c
void merge_sort(int arr[], int left, int right){
// left right are index
if(left >= right){
return;
}else{
int mid = (right+left)/2;
merge_sort(arr, left, mid);
merge_sort(arr, mid+1, right);
msort(arr, left, right, mid);
}
}
```
## 代码解释
递归需要终止条件，当长度为1，利用下标表示就是left>=right，此时递归结束，返回上一级。
接着将二分的索引作为参数（就是新二分出来数组的left，right），进行递归操作，实现原数组的对半分。
分割操作之后是msort，稍后讲解。
注意：**整个过程中arr本身的长度都是不变的**！而且arr的索引还是从0开始到结束，也就是说，我们并不是真的将数组分割成了一个一个新数组，**我们都是在原数组上进行操作**，我们所有操作都是通过下标实现的。
# 代码实现——步骤二
对于一次并，示意图如下：
1. 我们假设有两个**已排序**的数组（假设已排序，这样就能先解决将两数组合并的问题）
2. 这两个数组被拼成了一个数组，下标如图所示
3. 对这么一个数组进行排序，只需要一次遍历操作
我们引入两个类似指针的变量**i, j**，一个指向这个数组的开头，一个指向中间，那么我们就能通过比较**i, j**索引对应的值来进行排序。
如果只有这一个数组，排序有些困难，于是我们选择引入新的数组（即复制一遍原数组），然后**把排序结果保存回原数组**。
注意：我们这里加入了**left、right、mid**变量来获取这个数组的开头、结尾与中间，其中这三个变量都是索引值。
```c
int tmp_arr;
for(int i = left; i <= right; i++){
// copy to a temp arr
tmp_arr = arr;
}
int i = left, j = mid+1;
for(int k = left; k <= right; k++){
if(i > mid){
arr = tmp_arr;
continue;
}else
if(j > right){
arr = tmp_arr;
continue;
}
if(tmp_arr < tmp_arr){
arr = tmp_arr;
}else
if(tmp_arr >= tmp_arr){
arr = tmp_arr;
}
}
```
## 代码解释
在自行实现归并排序的过程中，最纠结的就是如何规定数组的长度，但实际上长度并不重要，因为最后都可以按照其索引值将结果复制回原数组。
在分成单个数组时，回到了上一步两个数组的状态，而这两个数组长度一定小于等于2，由于msort的过程中一次只能处理一个数组，因此实际上，msort是先分别排序了这两个数组，它们混合进了arr[]，然后再进入msort进行排序。
# 补充
在面对元素较少的数组时，可以考虑其它排序方法。
# 总结
其实我认为“将数组分割再合并”的说法非常令人费解，因为这样就会让人有“把两个数组传进一个函数，这个函数去把这两个数组首尾相接拼起来”的感觉，这种操作如何用递归实现？我还没有探索过。
实际上可以理解成，含n个元素的一个数组arr，我们先是有n个指针指着各个元素，然后两个两个比较大小/对调元素，接下来指针减半（两个指针之间间隔一个位置），然后4个一组，每组有两个指针，进行比大小与对换元素的操作，然后指针再减半，以此类推 本帖最后由 dmmtongyong 于 2024-11-1 16:44 编辑
归并排序的时间复杂度是O(nlogn)。
归并排序需要将原始序列分解成若干个子序列，每个子序列的长度为2^n，因此需要进行logn层的分解。
在合并阶段，需要将两个有序的子序列合并成一个有序的序列，这个过程的时间复杂度为O(n)。
因此，归并排序的总时间复杂度为O(nlogn)。
归并排序的基本思路是将数组分成两组，如果这两组内的数据都是有序的，那么就可以很方便地将这两组数据进行排序。
此外，归并排序的空间复杂度为O(n)，因为需要额外的空间来存储分解后的子序列。 请问这种编程的思维，小白应该如何开始学习？总感觉自己学东西，东一榔头西一棒槌的，最后啥也没学会。 感觉这个效率不怎么快 最近也在开始学习C语言，每天学习的时间不固定，感觉自己学到了点东西，又感觉自己什么都没学到
楼主是自学、学校学习还是报的班呀？ naisitu 发表于 2024-11-2 17:11
最近也在开始学习C语言，每天学习的时间不固定，感觉自己学到了点东西，又感觉自己什么都没学到
楼主是自 ...
自学，同时也是计算机专业。因为周围有非常多水平极高的同学（指大一就几乎全栈），所以我也是一直在压力自己去学习这些内容。至于学习的收获感，考虑去leetcode或者洛谷上找一点题做一下吧，这些算法包含的思想还是挺有帮助的
页:
[1]