如何在C++中实现基于分治策略的归并排序算法?
时间: 2024-10-19 19:17:58 浏览: 46
在C++中,归并排序是一种采用分治策略的经典算法。它将待排序数组分成两个大小相等的部分,分别对这两部分进行递归排序,然后合并已排序的部分。以下是基本步骤:
1. **分割(Divide)**:首先,将输入数组`arr`一分为二,通常取数组长度的一半作为分界点。
```cpp
void mergeSort(int arr[], int left, int right) {
if (left < right) {
// ...
}
}
```
2. **递归(Conquer)**:对左右两部分递归地调用`mergeSort()`函数。
```cpp
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
}
}
```
3. **合并(Combine)**:当两个部分都被排序后,将它们合并成一个有序数组。这一步创建了一个临时数组`temp`,并将左、右部分按顺序复制到`temp`,同时保持左侧元素小于右侧元素的条件。
```cpp
void merge(int arr[], int temp[], int left, int mid, int right) {
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 (int x = 0; x < k; ++x) {
arr[left + x] = temp[x];
}
}
// 调用合并操作
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, arr, left, mid, right);
}
}
```
阅读全文