（初学算法，希望得到各位的指正）
归并排序的主要思想
归——将数组分成两部分，分别进行排序。
并——将已经排序的两个数组合并起来。
“并”的部分对于我而言有点难以理解，接下来的重点会放在“并”上面。
代码实现——步骤一
第一步就是使用递归将数组二分，关键在于利用下标实现二分操作。
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开始到结束，也就是说，我们并不是真的将数组分割成了一个一个新数组，我们都是在原数组上进行操作，我们所有操作都是通过下标实现的。
代码实现——步骤二
对于一次并，示意图如下：
- 我们假设有两个已排序的数组（假设已排序，这样就能先解决将两数组合并的问题）
- 这两个数组被拼成了一个数组，下标如图所示
- 对这么一个数组进行排序，只需要一次遍历操作
我们引入两个类似指针的变量i, j，一个指向这个数组的开头，一个指向中间，那么我们就能通过比较i, j索引对应的值来进行排序。
如果只有这一个数组，排序有些困难，于是我们选择引入新的数组（即复制一遍原数组），然后把排序结果保存回原数组。
注意：我们这里加入了left、right、mid变量来获取这个数组的开头、结尾与中间，其中这三个变量都是索引值。
int tmp_arr[right];
for(int i = left; i <= right; i++){
// copy to a temp arr
tmp_arr[i] = arr[i];
}
int i = left, j = mid+1;
for(int k = left; k <= right; k++){
if(i > mid){
arr[k] = tmp_arr[j++];
continue;
}else
if(j > right){
arr[k] = tmp_arr[i++];
continue;
}
if(tmp_arr[i] < tmp_arr[j]){
arr[k] = tmp_arr[i++];
}else
if(tmp_arr[i] >= tmp_arr[j]){
arr[k] = tmp_arr[j++];
}
}
代码解释
在自行实现归并排序的过程中，最纠结的就是如何规定数组的长度，但实际上长度并不重要，因为最后都可以按照其索引值将结果复制回原数组。
在分成单个数组时，回到了上一步两个数组的状态，而这两个数组长度一定小于等于2，由于msort的过程中一次只能处理一个数组，因此实际上，msort是先分别排序了这两个数组，它们混合进了arr[]，然后再进入msort进行排序。
补充
在面对元素较少的数组时，可以考虑其它排序方法。
总结
其实我认为“将数组分割再合并”的说法非常令人费解，因为这样就会让人有“把两个数组传进一个函数，这个函数去把这两个数组首尾相接拼起来”的感觉，这种操作如何用递归实现？我还没有探索过。
实际上可以理解成，含n个元素的一个数组arr，我们先是有n个指针指着各个元素，然后两个两个比较大小/对调元素，接下来指针减半（两个指针之间间隔一个位置），然后4个一组，每组有两个指针，进行比大小与对换元素的操作，然后指针再减半，以此类推 | 
发表于 2024-11-1 15:22
|
发表于 2024-11-2 18:40
