用c++表示归并排序算法的基本格式(只需要归并排序部分即可)
时间: 2024-05-10 17:12:20 浏览: 12
归并排序是一种经典的排序算法,它基于分治思想,将待排序的序列递归地分成两部分,对每一部分进行排序,然后再将两部分合并起来。以下是 C++ 中表示归并排序的基本格式:
```
void merge(vector<int>& nums, int l, int mid, int r) {
vector<int> temp(r - l + 1);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= r) {
temp[k++] = nums[j++];
}
for (i = l, k = 0; i <= r; ++i, ++k) {
nums[i] = temp[k];
}
}
void mergeSort(vector<int>& nums, int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
merge(nums, l, mid, r);
}
```
其中,`merge()` 函数实现了归并操作,将两个有序的数组合并成一个有序数组。`mergeSort()` 函数实现了归并排序,它通过递归地对左右两部分进行归并排序,并最终将两部分合并起来。