[教程]掌握C语言，轻松实现高效归并排序

归并排序是一种高效的排序算法，它将待排序的数组分成两半，递归地对它们进行排序，然后将排好序的子数组合并成完整的数组。C语言由于其简洁性和效率，是实现归并排序的理想选择。本文将详细介绍如何在C语言中实现...

归并排序是一种高效的排序算法，它将待排序的数组分成两半，递归地对它们进行排序，然后将排好序的子数组合并成完整的数组。C语言由于其简洁性和效率，是实现归并排序的理想选择。本文将详细介绍如何在C语言中实现归并排序，并提供一个完整的示例代码。

归并排序的基本原理

归并排序是一种分治策略的典型应用。其基本原理如下：

1. 分割：将数组从中间分割成两个子数组。
2. 递归排序：递归地对两个子数组进行排序。
3. 合并：将两个已排序的子数组合并成一个完整的、有序的数组。

C语言实现归并排序

下面是一个使用C语言实现的归并排序的示例：

#include 
void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; // 创建临时数组 int L[n1], R[n2]; // 复制数据到临时数组 for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; // 合并临时数组回到原数组 i = 0; j = 0; k = l; 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 l, int r) { if (l < r) { // 找到中间点 int m = l + (r - l) / 2; // 分别对左右两部分进行排序 mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // 合并两部分 merge(arr, l, m, r); }
}
void printArray(int A[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", A[i]); printf("\n");
}
// 主函数来测试上述函数
int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int arr_size = sizeof(arr) / sizeof(arr[0]); printf("Given array is \n"); printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); printf("\nSorted array is \n"); printArray(arr, arr_size); return 0;
}

代码解析

1. merge函数：这是合并两个已排序数组的函数。它首先创建两个临时数组来存储两个子数组的元素，然后逐个比较并合并这些元素回到原数组。

2. mergeSort函数：这是一个递归函数，它将数组分割成两半，然后递归地对它们进行排序，最后调用merge函数来合并它们。

3. printArray函数：这个函数用于打印数组。

4. main函数：这是程序的入口点，它创建一个数组，调用mergeSort对其进行排序，并打印排序后的数组。

通过以上步骤，您可以在C语言中实现高效的归并排序。这种方法不仅适用于小数组，也可以扩展到处理大数据集，因为它的时间复杂度为O(n log n)。