以下代码采用分而治之算法实现归并排序。请补充函数mergesort()的代码。提示:mergesort()函数可用递归实现,其中参数n在递归调用中不需要变化。 函数接口定义: void mergesort(int a[],int n,int left,int right);
时间: 2024-05-13 09:19:43 浏览: 11
```c++
void merge(int a[], int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = 0;
int* tmp = new int[right - left + 1];
while (i <= mid && j <= right) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
}
else {
tmp[k++] = a[j++];
}
}
while (i <= mid) {
tmp[k++] = a[i++];
}
while (j <= right) {
tmp[k++] = a[j++];
}
for (int x = 0; x < k; x++) {
a[left + x] = tmp[x];
}
delete[] tmp;
}
void mergesort(int a[], int n, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergesort(a, n, left, mid);
mergesort(a, n, mid + 1, right);
merge(a, left, mid, right);
}
}
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)