C语言如何实现归并排序

---

---

归并排序（Merge Sort）是一种基于分治思想的高效排序算法。它将数组分成较小的子数组，分别对这些子数组进行排序，然后再将已排序的子数组合并成一个大的有序数组。下面是用C语言实现归并排序的示例代码：

```c

include

include

// 合并两个子数组

void merge(int arr[], int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

// 创建临时数组

int L = (int)malloc(n1 sizeof(int));

int R = (int)malloc(n2 sizeof(int));

// 拷贝数据到临时数组

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++;

// 释放临时数组

free(L);

free(R);

// 归并排序函数

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);

// 打印数组

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++)

printf("%d ", arr[i]);

printf("

");

// 主函数

int main() {

int arr[] = {12, 11, 13, 5, 6, 7};

int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is

");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("

Sorted array is

");

printArray(arr, arr_size);

return 0;

```

代码说明：

1. `merge` 函数：

用于将两个子数组合并成一个有序数组。

`L` 和 `R` 是临时数组，用于存储待合并的子数组。

合并过程是将 `L` 和 `R` 中的元素按顺序拷贝回原数组 `arr`。

2. `mergeSort` 函数：

递归地将数组分成两半，分别排序，然后合并。

终止条件是子数组长度为1或0，此时数组已是有序的。

3. `printArray` 函数：

用于打印数组内容。

4. `main` 函数：

初始化一个数组并调用 `mergeSort` 进行排序，然后打印排序前后的数组。

这个实现使用了额外的内存来存储临时数组，因此空间复杂度为 O(n)，时间复杂度为 O(n log n)，是一种非常稳定和高效的排序算法。

上一篇：C语言中如何优化gzip文件的读写性能
下一篇：D-Link路由器如何限制WiFi用户访问

---