归并排序算法：稳定高效的分治排序方案

算法原理

归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法，由约翰·冯·诺伊曼在1945年发明。它是典型的分治算法，采用”分治法”的思想，将问题分解为更小的子问题，然后合并子问题的解来得到原问题的解。

基本思想

1. 分解：将n个元素的数组分解为两个n/2个元素的子数组
2. 解决：递归地对两个子数组进行归并排序
3. 合并：将两个已排序的子数组合并成一个排序的数组

归并过程详解

归并是算法的核心操作，将两个已排序的数组合并为一个排序数组：

1. 使用两个指针分别指向两个子数组的开始
2. 比较指针指向的元素，将较小的元素放入结果数组
3. 移动对应指针，重复比较
4. 当一个数组遍历完毕，将另一个数组的剩余元素全部复制到结果数组

优缺点分析

优点

1. 时间复杂度稳定：在所有情况下都是O(n log n)
2. 稳定排序：相等元素的相对位置不会改变
3. 可预测性能：最好、最坏、平均情况性能一致
4. 适合外部排序：可以处理超出内存的大数据
5. 并行友好：天然支持并行化

缺点

1. 空间复杂度高：需要O(n)的额外空间
2. 内存开销大：不是原地排序算法
3. 常数因子较大：实际运行时间可能比快速排序长
4. 对小数组效率不高：递归开销相对较大

使用场景

适用场景

1. 要求稳定排序：需要保持相等元素相对位置
2. 大规模数据处理：外部排序，如文件排序
3. 实时系统：需要可预测的性能表现
4. 并行计算：多核或分布式环境
5. 链表排序：归并排序天然适合链表结构

不适用场景

1. 内存受限环境：可用内存非常有限
2. 小规模数据：插入排序可能更高效
3. 要求原地排序：无法提供额外内存空间

C语言实现

基础版本

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

/**
 * 合并两个已排序的子数组
 * @param arr 原数组
 * @param temp 临时数组
 * @param left 左子数组起始位置
 * @param mid 左子数组结束位置
 * @param right 右子数组结束位置
 */
void merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left;    // 左子数组指针
    int j = mid + 1; // 右子数组指针
    int k = left;    // 临时数组指针
    
    // 比较并合并两个子数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    // 复制左子数组剩余元素
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    
    // 复制右子数组剩余元素
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    
    // 将临时数组的内容复制回原数组
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

/**
 * 归并排序主函数
 * @param arr 待排序数组
 * @param temp 临时数组
 * @param left 起始位置
 * @param right 结束位置
 */
void merge_sort_recursive(int arr[], int temp[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        // 递归排序左半部分
        merge_sort_recursive(arr, temp, left, mid);
        
        // 递归排序右半部分
        merge_sort_recursive(arr, temp, mid + 1, right);
        
        // 合并两个已排序的部分
        merge(arr, temp, left, mid, right);
    }
}

/**
 * 归并排序入口函数
 * @param arr 待排序数组
 * @param size 数组大小
 */
void merge_sort(int arr[], int size) {
    int* temp = (int*)malloc(size * sizeof(int));
    if (temp == NULL) {
        printf("内存分配失败!\n");
        return;
    }
    
    merge_sort_recursive(arr, temp, 0, size - 1);
    free(temp);
}

/**
 * 自底向上的归并排序（迭代版本）
 * @param arr 待排序数组
 * @param size 数组大小
 */
void merge_sort_iterative(int arr[], int size) {
    int* temp = (int*)malloc(size * sizeof(int));
    if (temp == NULL) {
        printf("内存分配失败!\n");
        return;
    }
    
    // 子数组大小从1开始，每次翻倍
    for (int curr_size = 1; curr_size < size; curr_size *= 2) {
        // 选择起始点
        for (int left = 0; left < size - 1; left += 2 * curr_size) {
            // 计算中点和终点
            int mid = left + curr_size - 1;
            int right = left + 2 * curr_size - 1;
            
            // 确保不越界
            if (mid >= size) mid = size - 1;
            if (right >= size) right = size - 1;
            
            // 只有当left < right时才需要合并
            if (left < right) {
                merge(arr, temp, left, mid, right);
            }
        }
    }
    
    free(temp);
}

/**
 * 优化的归并排序（小数组使用插入排序）
 */
void insertion_sort_range(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

void merge_sort_optimized(int arr[], int temp[], int left, int right) {
    // 小数组使用插入排序
    if (right - left + 1 <= 10) {
        insertion_sort_range(arr, left, right);
        return;
    }
    
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        merge_sort_optimized(arr, temp, left, mid);
        merge_sort_optimized(arr, temp, mid + 1, right);
        
        // 如果已经有序，跳过合并
        if (arr[mid] <= arr[mid + 1]) {
            return;
        }
        
        merge(arr, temp, left, mid, right);
    }
}

/**
 * 原地归并排序（减少空间使用）
 */
void merge_inplace(int arr[], int left, int mid, int right) {
    int start2 = mid + 1;
    
    // 如果直接合并位置已经正确
    if (arr[mid] <= arr[start2]) {
        return;
    }
    
    while (left <= mid && start2 <= right) {
        // 如果左侧元素在正确位置
        if (arr[left] <= arr[start2]) {
            left++;
        } else {
            int value = arr[start2];
            int index = start2;
            
            // 将元素向右移动
            while (index != left) {
                arr[index] = arr[index - 1];
                index--;
            }
            
            arr[left] = value;
            left++;
            mid++;
            start2++;
        }
    }
}

void merge_sort_inplace(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        merge_sort_inplace(arr, left, mid);
        merge_sort_inplace(arr, mid + 1, right);
        merge_inplace(arr, left, mid, right);
    }
}

/**
 * 计算逆序对数量的归并排序
 */
long long merge_and_count(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    long long inv_count = 0;
    
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            // 计算逆序对
            inv_count += (mid - i + 1);
        }
    }
    
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
    
    return inv_count;
}

long long merge_sort_count_inversions(int arr[], int temp[], int left, int right) {
    long long inv_count = 0;
    
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        inv_count += merge_sort_count_inversions(arr, temp, left, mid);
        inv_count += merge_sort_count_inversions(arr, temp, mid + 1, right);
        inv_count += merge_and_count(arr, temp, left, mid, right);
    }
    
    return inv_count;
}

// 测试和演示函数
void print_array(int arr[], int size, const char* title) {
    printf("%s: ", title);
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void test_merge_sort() {
    printf("=== 归并排序算法演示 ===\n\n");
    
    // 测试数据
    int test_cases[][10] = {
        {38, 27, 43, 3, 9, 82, 10, 1, 7, 15},
        {5, 2, 4, 6, 1, 3, 8, 9, 7, 0},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
    };
    
    const char* descriptions[] = {
        "随机数组",
        "普通数组",
        "重复元素数组",
        "逆序数组"
    };
    
    for (int t = 0; t < 4; t++) {
        printf("%s:\n", descriptions[t]);
        
        int arr1[10], arr2[10], arr3[10];
        memcpy(arr1, test_cases[t], sizeof(test_cases[t]));
        memcpy(arr2, test_cases[t], sizeof(test_cases[t]));
        memcpy(arr3, test_cases[t], sizeof(test_cases[t]));
        
        print_array(arr1, 10, "排序前");
        
        // 测试递归归并排序
        merge_sort(arr1, 10);
        print_array(arr1, 10, "递归归并排序");
        
        // 测试迭代归并排序
        merge_sort_iterative(arr2, 10);
        print_array(arr2, 10, "迭代归并排序");
        
        // 测试原地归并排序
        merge_sort_inplace(arr3, 0, 9);
        print_array(arr3, 10, "原地归并排序");
        
        // 计算逆序对
        int arr4[10];
        memcpy(arr4, test_cases[t], sizeof(test_cases[t]));
        int* temp = (int*)malloc(10 * sizeof(int));
        long long inversions = merge_sort_count_inversions(arr4, temp, 0, 9);
        printf("逆序对数量: %lld\n", inversions);
        free(temp);
        
        printf("\n");
    }
}

void stability_test() {
    printf("=== 稳定性测试 ===\n");
    
    // 使用结构体测试稳定性
    typedef struct {
        int value;
        int original_index;
    } Element;
    
    Element elements[] = {
        {3, 0}, {1, 1}, {3, 2}, {2, 3}, {1, 4}
    };
    int size = sizeof(elements) / sizeof(elements[0]);
    
    printf("排序前: ");
    for (int i = 0; i < size; i++) {
        printf("(%d,%d) ", elements[i].value, elements[i].original_index);
    }
    printf("\n");
    
    // 简化的归并排序（针对结构体）
    // 这里为了演示简化实现
    printf("归并排序保持了相等元素的相对位置（稳定性）\n\n");
}

void performance_test() {
    printf("=== 性能测试 ===\n");
    
    const int sizes[] = {1000, 10000, 100000};
    const int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
    
    for (int s = 0; s < num_sizes; s++) {
        int size = sizes[s];
        int* arr1 = (int*)malloc(size * sizeof(int));
        int* arr2 = (int*)malloc(size * sizeof(int));
        
        // 生成随机数据
        srand((unsigned int)time(NULL));
        for (int i = 0; i < size; i++) {
            arr1[i] = rand() % 10000;
        }
        memcpy(arr2, arr1, size * sizeof(int));
        
        // 测试递归版本
        clock_t start = clock();
        merge_sort(arr1, size);
        clock_t end = clock();
        double time_recursive = ((double)(end - start)) / CLOCKS_PER_SEC;
        
        // 测试迭代版本
        start = clock();
        merge_sort_iterative(arr2, size);
        end = clock();
        double time_iterative = ((double)(end - start)) / CLOCKS_PER_SEC;
        
        printf("数组大小: %d\n", size);
        printf("  递归版本: %.6f 秒\n", time_recursive);
        printf("  迭代版本: %.6f 秒\n", time_iterative);
        
        free(arr1);
        free(arr2);
    }
}

int main() {
    test_merge_sort();
    stability_test();
    performance_test();
    return 0;
}

算法变种和应用

1. 外部排序

// 文件归并排序示例（简化版）
void external_merge_sort(const char* input_file, const char* output_file, int memory_limit) {
    // 1. 将大文件分割成可以装入内存的小文件
    // 2. 对每个小文件进行内存排序
    // 3. 多路归并所有小文件
    
    printf("外部排序：处理超出内存大小的文件\n");
    printf("内存限制: %d bytes\n", memory_limit);
    // 实际实现会涉及文件操作和多路归并
}

2. 自然归并排序

// 利用输入中已有的有序序列
void natural_merge_sort(int arr[], int size) {
    int* temp = (int*)malloc(size * sizeof(int));
    int run_count;
    
    do {
        run_count = 0;
        int i = 0;
        
        while (i < size) {
            int start = i;
            
            // 找到当前有序序列的结束位置
            while (i + 1 < size && arr[i] <= arr[i + 1]) {
                i++;
            }
            
            int mid = i;
            i++;
            
            if (i < size) {
                // 找到下一个有序序列的结束位置
                while (i + 1 < size && arr[i] <= arr[i + 1]) {
                    i++;
                }
                
                // 合并两个有序序列
                merge(arr, temp, start, mid, i);
                run_count++;
            }
            
            i++;
        }
    } while (run_count > 0);
    
    free(temp);
}

复杂度分析

时间复杂度

• 最好情况：O(n log n)
• 平均情况：O(n log n)
• 最坏情况：O(n log n)

空间复杂度

• 递归版本：O(n + log n) - n为临时数组，log n为递归栈
• 迭代版本：O(n) - 只需要临时数组
• 原地版本：O(log n) - 只有递归栈

稳定性

归并排序是稳定的排序算法，相等元素的相对位置保持不变。

实际应用

1. 外部排序：处理大文件排序
2. 数据库系统：多表连接、排序操作
3. 并行计算：多线程/多进程排序
4. TimSort：Python、Java等语言的默认排序算法的基础
5. 计算逆序对：数组乱序程度的度量

总结

归并排序是一个优秀的排序算法，具有稳定的O(n log n)时间复杂度和稳定性特征。虽然空间复杂度较高，但在需要稳定排序、外部排序或并行排序的场景中，归并排序是首选算法。

其分治思想和稳定的性能表现，使得归并排序成为理解算法设计和分析的重要范例，是计算机科学教育中不可或缺的经典算法。

版权所有，如有侵权请联系我