把数组分成三个相等的部分归并排序
时间: 2023-07-07 21:40:03 浏览: 69
将数组分成三个相等的部分,我们可以将其分为左、中、右三个部分。我们可以先将左部分和右部分分别归并排序,然后再将中间部分与两个排好序的部分合并。
具体步骤如下:
1. 计算数组长度 $n$ 并判断是否能够被 3 整除,若不能则直接返回。
2. 定义归并排序函数 mergeSort(arr, l, r),其中 arr 表示待排序的数组,l 和 r 分别表示待排序区间的左右端点。
3. 调用 mergeSort(arr, 0, n / 3 - 1) 对数组左部分进行归并排序。
4. 调用 mergeSort(arr, n / 3, n / 3 * 2 - 1) 对数组中间部分进行归并排序。
5. 调用 mergeSort(arr, n / 3 * 2, n - 1) 对数组右部分进行归并排序。
6. 将两个排好序的左右部分和中间部分进行归并,即调用 merge(arr, l, mid, r) 函数,其中 l 为左部分起始位置,r 为右部分结束位置,mid 为中间部分结束位置。
完整的代码示例:
```
void merge(int arr[], int l, int mid, int r) {
int len1 = mid - l + 1, len2 = r - mid;
int L[len1], R[len2];
for (int i = 0; i < len1; i++)
L[i] = arr[l + i];
for (int j = 0; j < len2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = l;
while (i < len1 && j < len2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < len1)
arr[k++] = L[i++];
while (j < len2)
arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
void sortArray(int arr[], int n) {
if (n % 3 != 0) return;
mergeSort(arr, 0, n / 3 - 1);
mergeSort(arr, n / 3, n / 3 * 2 - 1);
mergeSort(arr, n / 3 * 2, n - 1);
merge(arr, 0, n / 3 - 1, n - 1);
}
```
相关推荐
![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_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)