归并排序c++
时间: 2023-06-29 11:15:44 浏览: 64
好的,以下是C++实现归并排序的代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& nums, int left, int mid, int right) {
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
}
else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
for (int p = 0; p < temp.size(); p++) {
nums[left + p] = temp[p];
}
}
void mergeSort(vector<int>& nums, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
}
int main() {
vector<int> nums = { 12, 11, 13, 5, 6, 7 };
mergeSort(nums, 0, nums.size() - 1);
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
```
在这个代码中,我们使用了一个`vector`来存储数组元素,这样可以方便地进行合并操作。`merge()`函数将两个已排序的子数组合并成一个子数组。`mergeSort()`函数使用递归的方式将数组分成两半,直到每个子数组的长度为1,然后调用`merge()`函数将它们合并成一个已排序的数组。最后,`main()`函数初始化一个`vector`并调用`mergeSort()`函数对其进行排序。