用C语言写一个三路归并算法
时间: 2023-12-29 08:52:08 浏览: 31
好的,以下是使用C语言实现三路归并算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int left[], int leftSize, int middle[], int middleSize, int right[], int rightSize) {
int i = 0, j = 0, k = 0;
while (i < leftSize && j < middleSize && k < rightSize) {
if (left[i] < middle[j]) {
if (left[i] < right[k]) {
arr[i + j + k] = left[i];
i++;
} else {
arr[i + j + k] = right[k];
k++;
}
} else {
if (middle[j] < right[k]) {
arr[i + j + k] = middle[j];
j++;
} else {
arr[i + j + k] = right[k];
k++;
}
}
}
while (i < leftSize && j < middleSize) {
if (left[i] < middle[j]) {
arr[i + j + k] = left[i];
i++;
} else {
arr[i + j + k] = middle[j];
j++;
}
}
while (i < leftSize && k < rightSize) {
if (left[i] < right[k]) {
arr[i + j + k] = left[i];
i++;
} else {
arr[i + j + k] = right[k];
k++;
}
}
while (j < middleSize && k < rightSize) {
if (middle[j] < right[k]) {
arr[i + j + k] = middle[j];
j++;
} else {
arr[i + j + k] = right[k];
k++;
}
}
while (i < leftSize) {
arr[i + j + k] = left[i];
i++;
}
while (j < middleSize) {
arr[i + j + k] = middle[j];
j++;
}
while (k < rightSize) {
arr[i + j + k] = right[k];
k++;
}
}
void merge_sort(int arr[], int size) {
if (size > 1) {
int leftSize = size / 3;
int middleSize = size / 3;
int rightSize = size - leftSize - middleSize;
int left[leftSize], middle[middleSize], right[rightSize];
for (int i = 0; i < leftSize; i++) {
left[i] = arr[i];
}
for (int i = 0; i < middleSize; i++) {
middle[i] = arr[leftSize + i];
}
for (int i = 0; i < rightSize; i++) {
right[i] = arr[leftSize + middleSize + i];
}
merge_sort(left, leftSize);
merge_sort(middle, middleSize);
merge_sort(right, rightSize);
merge(arr, left, leftSize, middle, middleSize, right, rightSize);
}
}
int main() {
int arr[] = {9, 1, 6, 3, 8, 7, 5, 2, 0, 4};
int size = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, size);
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)