归并排序

归并排序（Merge Sort）是一种高效且稳定的排序算法，基于分治法，广泛应用于需要稳定排序的场景。它通过将数组递归地分成较小的子数组，分别排序后合并成有序数组。本文将详细讲解归并排序的原理、步骤，并提供C语言和Go语言的代码示例，帮助初学者快速上手。

原理

归并排序的核心思想是：

1. 分：将数组递归地分成两个子数组，直到子数组长度为1（单个元素视为已排序）。
2. 治：合并两个已排序的子数组，生成一个新的有序数组。
3. 重复上述步骤，直到整个数组排序完成。

它的时间复杂度是 O(n log n)，其中 n 是数组的长度，无论输入数据如何，都保持一致。归并排序需要额外的空间来存储临时数组，因此空间复杂度为 O(n)。它的稳定性使其适合需要保持相同元素相对顺序的场景。

步骤

假设我们要对一个整数数组进行升序排序，以下是归并排序的详细步骤：

1. 划分：将数组分成两个大致相等的子数组，递归地对每个子数组进行排序。
2. 终止条件：当子数组长度为1时，停止划分（单个元素已排序）。
3. 合并：将两个已排序的子数组合并成一个有序数组，通过比较两个子数组的元素，依次选取较小的元素放入结果数组。
4. 重复：对所有子数组递归执行上述步骤，直到整个数组排序完成。

实现

C

下面是用C语言实现归并排序的代码，包含详细注释以帮助理解。

main.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);
    }
}

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

// 主函数：测试归并排序
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组：");
    printArray(arr, n);
    
    mergeSort(arr, 0, n - 1);
    
    printf("排序后的数组：");
    printArray(arr, n);
    
    return 0;
}

编译 & 运行

$ gcc -o bin/merge-sort main.c
$ bin/merge-sort 
原始数组：64 34 25 12 22 11 90 
排序后的数组：11 12 22 25 34 64 90 
$ 

Go

下面是用Go语言实现归并排序的代码，包含详细注释以帮助理解。

main.go

package main

import "fmt"

// merge 合并两个已排序的子数组
func merge(arr []int, left, mid, right int) {
    n1 := mid - left + 1 // 左子数组长度
    n2 := right - mid    // 右子数组长度
    
    // 创建临时切片
    L := make([]int, n1)
    R := make([]int, n2)
    
    // 复制数据到临时切片
    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 // 合并后数组索引
    for i < n1 && j < n2 {
        if L[i] <= R[j] {
            arr[k] = L[i]
            i++
        } else {
            arr[k] = R[j]
            j++
        }
        k++
    }
    
    // 复制左子数组剩余元素
    for i < n1 {
        arr[k] = L[i]
        i++
        k++
    }
    
    // 复制右子数组剩余元素
    for j < n2 {
        arr[k] = R[j]
        j++
        k++
    }
}

// mergeSort 实现归并排序
func mergeSort(arr []int, left, right int) {
    if left < right {
        mid := left + (right-left)/2 // 计算中间索引
        
        // 递归排序左半部分
        mergeSort(arr, left, mid)
        // 递归排序右半部分
        mergeSort(arr, mid+1, right)
        
        // 合并已排序的子数组
        merge(arr, left, mid, right)
    }
}

// printArray 打印数组内容
func printArray(arr []int) {
    for _, val := range arr {
        fmt.Printf("%d ", val)
    }
    fmt.Println()
}

func main() {
    // 示例数组
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    
    fmt.Print("原始数组：")
    printArray(arr)
    
    mergeSort(arr, 0, len(arr)-1)
    
    fmt.Print("排序后的数组：")
    printArray(arr)
}

$ gsk build -v
create merge-sort/bin/merge-sort-linux-amd64
$ ./bin/merge-sort-linux-amd64 
原始数组：64 34 25 12 22 11 90 
排序后的数组：11 12 22 25 34 64 90

总结

归并排序的核心是通过分治法将数组递归分成小块，分别排序后合并成有序数组，具有稳定的排序特性。

---

版权声明：自由转载-非商用-非衍生-保持署名-保持来源

作者：afxcn

来源：https://zh.gostartkit.com/docs/algo/merge-sort

发表日期：2025年6月28日