归并排序的c++简易算法
时间: 2024-04-20 17:20:12 浏览: 24
归并排序是一种经典的排序算法,它采用分治的思想,将一个大问题分解为多个小问题,然后将小问题的解合并起来得到最终的解。下面是归并排序的C++简易算法:
```cpp
// 归并排序函数
void mergeSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSort(arr, left, mid); // 对左半部分进行归并排序
mergeSort(arr, mid + 1, right); // 对右半部分进行归并排序
merge(arr, left, mid, right); // 合并左右两部分
}
// 合并函数
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // 左半部分元素个数
int n2 = right - mid; // 右半部分元素个数
// 创建临时数组存放左右两部分的元素
int L[n1], R[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
// 合并左右两部分的元素
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 将剩余的元素复制到数组中
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
```
相关推荐
![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_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.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)