掌握C语言，轻松学会归并排序：高效算法实战指南

归并排序是一种经典的排序算法，它通过将大数组分解成小数组，对它们进行排序，然后合并这些排好序的数组，从而实现整体排序。掌握归并排序对于理解更复杂的排序算法和提升编程能力都有很大帮助。本文将使用C语言实现归并排序，并详细讲解其原理和步骤。

归并排序的基本原理

归并排序是一种分治算法，其基本思想是将原始数组分解成更小的子数组，直到每个子数组只有一个元素或者为空，然后将这些子数组合并起来，形成有序的数组。

分解：将数组分解成两个大小相等的子数组。
排序：对每个子数组进行归并排序。
合并：将两个已排序的子数组合并为一个有序的数组。

C语言实现归并排序

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

#include <stdio.h> void merge(int arr[], int left, int middle, int right) { int n1 = middle - left + 1; int n2 = right - middle; int L[n1], R[n2]; for (int i = 0; i < n1; i++) L[i] = arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[middle + 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++; } } void mergeSort(int arr[], int left, int right) { if (left < right) { int middle = left + (right - left) / 2; mergeSort(arr, left, middle); mergeSort(arr, middle + 1, right); merge(arr, left, middle, right); } } 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; }