【数据结构】排序算法：归并与堆

归并排序：分治策略的经典实现

算法原理

归并排序采用分治法策略，包含三个关键步骤：

1. 分解：递归地将数组分成两半

2. 解决：对子数组进行排序

3. 合并：将两个有序子数组合并为一个有序数组

C语言实现

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

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

    // 创建临时数组
    int *L = (int*)malloc(n1 * sizeof(int));
    int *R = (int*)malloc(n2 * sizeof(int));

    // 拷贝数据到临时数组
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 合并临时数组
    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);
    }
}

性能分析

• 时间复杂度：O(n log n)（所有情况）

• 空间复杂度：O(n)（需要临时数组）

• 稳定性：稳定排序（保持相等元素顺序）

优化方向

1. 小数组优化：当子数组较小时（如n<15）改用插入排序

2. 原地归并：减少空间使用但增加时间复杂度

3. 并行化：利用多线程处理独立子问题

堆排序：基于完全二叉树的高效排序

算法原理

堆排序利用堆数据结构的特性：

1. 建堆：将无序数组构建为最大堆

2. 排序：反复取出堆顶元素（最大值）并调整堆

C语言实现

#include <stdio.h>

// 调整堆
void heapify(int arr[], int n, int i) {
    int largest = i;        // 初始化最大元素为根
    int left = 2 * i + 1;   // 左子节点
    int right = 2 * i + 2;  // 右子节点

    // 如果左子节点大于根
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是根节点
    if (largest != i) {
        // 交换
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // 递归调整受影响的子堆
        heapify(arr, n, largest);
    }
}

// 堆排序主函数
void heapSort(int arr[], int n) {
    // 构建最大堆（从最后一个非叶子节点开始）
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 逐个提取元素
    for (int i = n - 1; i > 0; i--) {
        // 将当前根移动到数组末尾
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 在减小的堆上调用heapify
        heapify(arr, i, 0);
    }
}

性能分析

• 时间复杂度：O(n log n)（所有情况）

• 空间复杂度：O(1)（原地排序）

• 稳定性：不稳定排序（可能改变相等元素顺序）

优化方向

1. 堆化优化：减少不必要的比较操作

2. 多叉堆：使用d叉堆减少树高度

3. 并行建堆：利用多线程加速建堆过程

算法对比与选择指南

实际应用建议

1. 选择归并排序：

   • 需要稳定排序结果

   • 处理大数据集（特别是外部排序）

   • 内存充足的情况

2. 选择堆排序：

   • 内存受限环境

   • 需要原地排序

   • 实现优先级队列

3. 其他考虑：

   • 小规模数据（n<100）可考虑简单排序（如插入排序）

   • 现代CPU架构下，归并排序的缓存友好性可能带来实际性能优势

总结

归并排序和堆排序都是基于O(n log n)复杂度排序算法，各有其特点和适用场景。

归并排序作为分治策略的经典实现，优势在于稳定性、可预测的性能以及适用于外部排序的特点。它的递归实现简洁优雅，是理解分治思想的绝佳案例。在实际应用中，归并排序是处理大规模数据、特别是无法全部装入内存时的首选算法。

堆排序则充分利用了完全二叉树的性质，实现了原地排序，空间效率极高。它不仅是一种排序算法，更重要的是其堆数据结构在优先级队列等场景中有广泛应用。堆排序特别适合内存受限的环境，或者需要同时维护优先级队列功能的场景。

在实际开发中，选择排序算法需要综合考虑数据结构特征、稳定性要求、内存限制等多方面因素。现代标准库通常会在不同场景下选择最适合的排序算法，甚至采用混合策略以获得最佳性能。