使用分治法用c++写sort函数
时间: 2024-06-14 14:04:14 浏览: 18
以下是使用分治法用C++编写的sort函数的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 分治法排序函数
void merge(vector<int>& nums, int start, int mid, int end) {
int n1 = mid - start + 1;
int n2 = end - mid;
vector<int> left(n1);
vector<int> right(n2);
for (int i = 0; i < n1; i++) {
left[i] = nums[start + i];
}
for (int j = 0; j < n2; j++) {
right[j] = nums[mid + 1 + j];
}
int i = 0, j = 0, k = start;
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
nums[k] = left[i];
i++;
} else {
nums[k] = right[j];
j++;
}
k++;
}
while (i < n1) {
nums[k] = left[i];
i++;
k++;
}
while (j < n2) {
nums[k] = right[j];
j++;
k++;
}
}
void mergeSort(vector<int>& nums, int start, int end) {
if (start < end) {
int mid = start + (end - start) / 2;
mergeSort(nums, start, mid);
mergeSort(nums, mid + 1, end);
merge(nums, start, mid, end);
}
}
int main() {
vector<int> nums = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
cout << "原始数组:";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
mergeSort(nums, 0, nums.size() - 1);
cout << "排序后的数组:";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)