C语言实现归并排序算法

简介

归并排序（Merge Sort）是一种基于分治思想的高效排序算法。它的基本原理是将一个大的无序数组分成两个或多个较小的子数组，对每个子数组分别进行排序，然后再将排序好的子数组合并成一个有序的数组。在C语言中，实现归并排序可以帮助我们更好地处理大规模数据的排序问题，提高程序的执行效率。本文将详细介绍C语言实现归并排序算法的基础概念、使用方法、常见实践以及最佳实践。

基础概念

分治思想

分治思想是将一个复杂的问题分解成若干个规模较小、相互独立且与原问题形式相同的子问题，然后分别解决这些子问题，最后将子问题的解合并起来得到原问题的解。在归并排序中，分治思想体现在将数组不断地分割成更小的子数组，直到每个子数组只有一个元素（此时子数组是有序的），然后再将这些有序的子数组合并成一个有序的大数组。

归并排序的原理

归并排序主要分为两个步骤：分解（Divide）和合并（Merge）。

分解（Divide）：将一个数组从中间分成两个子数组，然后对每个子数组递归地进行分解操作，直到每个子数组的大小为1。
合并（Merge）：将两个有序的子数组合并成一个有序的数组。合并过程中，比较两个子数组的元素，将较小的元素依次放入一个临时数组中，直到其中一个子数组的元素全部被放入临时数组，然后将另一个子数组中剩余的元素直接放入临时数组。最后，将临时数组中的元素复制回原数组。

使用方法

函数定义

在C语言中，实现归并排序通常需要定义三个函数：

merge 函数：用于合并两个有序的子数组。
mergeSort 函数：用于递归地对数组进行分解和排序。
main 函数：用于测试归并排序算法。

代码实现

#include <stdio.h>

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    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[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++;
    }

    // 复制 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);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    printf("Sorted array: ");
    printArray(arr, size);

    return 0;
}

代码解释

merge 函数：接受一个数组 arr，以及两个子数组的边界 left、mid 和 right。函数内部创建两个临时数组 L 和 R，分别存储两个子数组的元素。然后通过比较两个临时数组的元素，将较小的元素依次放入原数组 arr 中。
mergeSort 函数：递归地对数组进行分解和排序。如果 left 小于 right，则计算中间位置 mid，然后分别对左右两个子数组进行递归排序，最后合并两个有序子数组。
main 函数：定义一个测试数组，并调用 mergeSort 函数对数组进行排序，最后打印排序前后的数组。

常见实践

数组排序

上述代码示例展示了如何对一个整数数组进行归并排序。在实际应用中，可以根据需要修改数组的类型和数据。例如，如果要对浮点数数组进行排序，只需将数组的类型从 int 改为 float，并相应地修改 printArray 函数中的格式化字符串。

文件数据排序

归并排序也可以用于对文件中的数据进行排序。以下是一个简单的示例，展示如何从文件中读取数据，进行归并排序，然后将排序后的数据写回文件：

#include <stdio.h>
#include <stdlib.h>

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    // 与上述代码相同
}

// 归并排序函数
void mergeSort(int arr[], int left, int right) {
    // 与上述代码相同
}

int main() {
    FILE *file = fopen("input.txt", "r");
    if (file == NULL) {
        perror("Error opening file");
        return 1;
    }

    int size = 0;
    int *arr = NULL;
    int num;
    while (fscanf(file, "%d", &num)!= EOF) {
        size++;
        arr = realloc(arr, size * sizeof(int));
        arr[size - 1] = num;
    }
    fclose(file);

    mergeSort(arr, 0, size - 1);

    file = fopen("output.txt", "w");
    if (file == NULL) {
        perror("Error opening file");
        free(arr);
        return 1;
    }

    for (int i = 0; i < size; i++) {
        fprintf(file, "%d\n", arr[i]);
    }
    fclose(file);
    free(arr);

    return 0;
}

代码解释

文件读取：使用 fopen 函数打开输入文件 input.txt，并通过 fscanf 函数逐行读取文件中的整数，将其存储到动态分配的数组 arr 中。
排序：调用 mergeSort 函数对数组 arr 进行排序。
文件写入：使用 fopen 函数打开输出文件 output.txt，并将排序后的数组元素逐行写入文件。

最佳实践

优化策略

减少临时数组的分配：在 merge 函数中，每次合并都分配和释放临时数组会增加时间和空间开销。可以预先分配一个足够大的临时数组，在整个排序过程中重复使用，避免频繁的内存分配和释放。
使用插入排序作为子问题的解决方案：当子数组的大小较小时，插入排序的性能通常比归并排序更好。可以在递归分解过程中，当子数组的大小小于某个阈值（例如 16）时，使用插入排序代替归并排序，以提高算法的整体性能。

时间复杂度分析

归并排序的时间复杂度为 $O(n \log n)$，其中 $n$ 是数组的大小。这是因为每次分解都将数组分成两个大致相等的子数组，需要进行 $\log n$ 次分解，而每次合并操作的时间复杂度为 $O(n)$。因此，归并排序在处理大规模数据时具有较好的性能。

小结

本文详细介绍了C语言实现归并排序算法的基础概念、使用方法、常见实践以及最佳实践。归并排序作为一种高效的排序算法，在处理大规模数据时具有明显的优势。通过理解分治思想和归并排序的原理，掌握C语言实现的代码技巧，以及优化策略，读者可以更好地应用归并排序算法解决实际问题。

参考资料

《算法导论》（Introduction to Algorithms），Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

C语言实现归并排序算法

简介

目录

基础概念

分治思想

归并排序的原理

使用方法

函数定义

代码实现

代码解释

常见实践

数组排序

文件数据排序

代码解释

最佳实践

优化策略

时间复杂度分析

小结

参考资料