归并排序的代码怎么理解啊
时间: 2023-10-19 15:09:08 浏览: 36
归并排序是一种分治算法,其核心思想是将一个大问题分解成小问题来解决。具体来说,它将待排序的数组分成两个部分,分别对这两个部分进行排序,然后再将它们归并起来。
下面是归并排序的代码实现(使用递归):
```
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
```
在这段代码中,`merge_sort` 函数接收一个待排序的数组以及该数组的左右边界,然后将其分成两个部分,分别对这两个部分进行排序,最后再将它们归并起来。`merge` 函数则是将两个已经排序好的部分归并成一个有序的数组。
具体来说,`merge_sort` 函数的实现逻辑如下:
1. 如果左边界小于右边界,说明待排序的数组至少有两个元素,需要分成两个部分进行排序;
2. 将数组分成左右两部分,分别对左右两部分递归调用 `merge_sort` 函数进行排序;
3. 将排好序的左右两部分通过 `merge` 函数进行归并。
`merge` 函数的实现逻辑如下:
1. 首先计算出左右两部分的长度 `n1` 和 `n2`;
2. 创建两个数组 L 和 R,分别存放左右两部分的元素;
3. 使用两个指针 i 和 j 分别指向数组 L 和 R 的开头,再使用一个指针 k 指向归并后的数组的开头;
4. 依次比较 L[i] 和 R[j] 的大小,将较小的元素存入归并后的数组中;
5. 如果 L 或 R 中还有剩余元素,则将其添加到归并后的数组中。
希望这样的解释能够帮助您理解归并排序的代码。