C语言归并排序算法详解与代码示例

归并排序是一种高效、稳定的排序算法，采用分治法策略，其基本思想是将待排序的数组不断二分，直至每个子数组只包含一个元素。然后，将这些有序的子数组逐层合并，最终得到一个完全有序的数组。

1. 算法步骤：

a. 分解: 将待排序的数组从中间递归地分成两个子数组，直到每个子数组只包含一个元素。 b. 合并: 将两个已排序的子数组合并成一个有序数组。 c. 重复: 重复步骤 b，直到合并成一个完整的有序数组。

**2. C语言代码示例:**c#include <stdio.h>

// 合并两个有序数组void merge(int arr[], int left[], int right[], int leftSize, int rightSize) { int i = 0, j = 0, k = 0;

while (i < leftSize && j < rightSize) {        if (left[i] <= right[j]) {            arr[k] = left[i];            i++;        } else {            arr[k] = right[j];            j++;        }        k++;    }

while (i < leftSize) {        arr[k] = left[i];        i++;        k++;    }

while (j < rightSize) {        arr[k] = right[j];        j++;        k++;    }}

// 归并排序void mergeSort(int arr[], int size) { if (size < 2) { return; }

int mid = size / 2;    int left[mid];    int right[size - mid];

for (int i = 0; i < mid; i++) {        left[i] = arr[i];    }

for (int i = mid; i < size; i++) {        right[i - mid] = arr[i];    }

mergeSort(left, mid);    mergeSort(right, size - mid);    merge(arr, left, right, mid, size - mid);}

int main() { int arr[] = {4, 2, 6, 8, 1, 3, 5, 7}; int size = sizeof(arr) / sizeof(arr[0]);

printf('排序前的数组: ');    for (int i = 0; i < size; i++) {        printf('%d ', arr[i]);    }

mergeSort(arr, size);

printf('

排序后的数组: '); for (int i = 0; i < size; i++) { printf('%d ', arr[i]); }

return 0;}

3. 代码解读:

merge()函数: 将两个有序数组合并成一个有序数组。* mergeSort()函数: 递归地将数组分成两个子数组，并对子数组进行排序，最后合并。* main()函数: 定义一个示例数组，调用mergeSort()函数进行排序，并输出排序结果。

4. 算法复杂度:

时间复杂度：最好、最坏和平均情况下均为 O(n log n)，效率较高。* 空间复杂度：O(n)，需要额外的空间存储临时数组。

5. 总结:

归并排序是一种稳定、高效的排序算法，适用于处理大规模数据。其代码实现清晰易懂，是学习排序算法的经典案例。