二路归并排序采用C语言
时间: 2023-10-12 08:19:02 浏览: 65
二路归并排序是一种经典的排序算法,它采用分治的思想,将待排序的序列不断二分为两个子序列,然后将这两个子序列合并成一个有序序列,最终得到排序结果。以下是C语言实现代码:
```c
void merge(int arr[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
/* 创建临时数组 */
int L[n1], R[n2];
/* 拷贝数据到临时数组 L[] 和 R[] */
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
/* 归并临时数组到 arr[left..right]*/
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++;
}
/* 拷贝 L[] 的保留元素 */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* 拷贝 R[] 的保留元素 */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right)
{
if (left < right) {
// 找到中间点
int mid = left + (right - left) / 2;
// 对左半部分进行排序
mergeSort(arr, left, mid);
// 对右半部分进行排序
mergeSort(arr, mid + 1, right);
// 合并左右两部分
merge(arr, left, mid, right);
}
}
```
在这个代码中,merge() 函数用于合并两个子数组,mergeSort() 函数用于将整个数组进行归并排序。通过递归的方式对每个子数组进行排序和合并,直到最后得到整个有序数组。