第1关:归并排序的递归算法
时间: 2024-07-07 21:01:19 浏览: 60
归并排序是一种分治算法,它的递归过程分为两个主要步骤:分治和合并。在第一关的递归算法中,这两个步骤具体如下:
1. **分治(Divide)**:
- 将待排序数组 `arr` 分成两半,每次递归调用将处理一半,直到每个子数组只包含一个元素,这时数组已经是有序的。
- 分治策略的关键点在于将问题分解为规模更小的相同问题。
2. **合并(Conquer)**:
- 当子数组足够小后,开始合并它们。这通常通过创建一个新的数组 `temp` 来完成,然后逐个比较两个子数组的元素,较小的放入 `temp`,直到其中一个子数组完全被添加,然后再将另一个子数组剩余部分添加到 `temp` 中。
- 合并操作是递归的终止条件,因为它将两个有序子数组合并成一个更大的有序数组。
递归过程的伪代码示例(使用 C++ 语言风格):
```cpp
void mergeSort(int arr[], int left, int right) {
if (left < right) {
// 计算中间索引
int mid = (left + right) / 2;
// 递归排序左半部分
mergeSort(arr, left, mid);
// 递归排序右半部分
mergeSort(arr, mid + 1, right);
// 合并两个已排序的部分
merge(arr, left, mid, right);
}
}
// 合并函数,实际的合并操作
void merge(int arr[], int left, int mid, int right) {
int temp[right - left + 1];
int i = left, j = mid + 1, k = 0;
// 比较并复制较小的元素到临时数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 复制剩余元素(如果存在)
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组的内容复制回原数组
for (i = left; i <= right; i++) {
arr[i] = temp[i - left];
}
}
```