排序算法-归并排序-EW帮帮网

算法排序-归并排序

简介

归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法，由约翰·冯·诺伊曼（John von Neumann）在1945年发明。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各种语言或库中都有实现。

归并排序是一种稳定的排序方法，其时间复杂度始终为O(n log n)，不受输入数据的影响，这使得它在需要稳定性能的场景中非常有用。

算法原理

归并排序的基本思想是：

分解（Divide）: 将待排序的数组分成两个子数组，直到每个子数组只有一个元素
解决（Conquer）: 递归地对子数组进行排序
合并（Combine）: 将两个已排序的子数组合并成一个有序数组

这个过程可以用递归来实现，递归的终止条件是数组长度为1。

Go语言实现

基础版本

package main

import "fmt"

// MergeSort 归并排序主函数
func MergeSort(arr []int) []int {
    // 递归终止条件
    if len(arr) <= 1 {
        return arr
    }
    
    // 分解：找到中点，分割数组
    mid := len(arr) / 2
    left := MergeSort(arr[:mid])
    right := MergeSort(arr[mid:])
    
    // 合并：将两个有序数组合并
    return merge(left, right)
}

// merge 合并两个有序数组
func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    
    // 比较两个数组的元素，将较小的元素加入结果数组
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    
    // 将剩余元素加入结果数组
    for i < len(left) {
        result = append(result, left[i])
        i++
    }
    
    for j < len(right) {
        result = append(result, right[j])
        j++
    }
    
    return result
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("排序前:", arr)
    
    sorted := MergeSort(arr)
    fmt.Println("排序后:", sorted)
}

原地归并排序版本

package main

import "fmt"

// MergeSortInPlace 原地归并排序
func MergeSortInPlace(arr []int, left, right int) {
    if left < right {
        mid := left + (right-left)/2
        
        // 递归排序左半部分
        MergeSortInPlace(arr, left, mid)
        // 递归排序右半部分
        MergeSortInPlace(arr, mid+1, right)
        
        // 合并两个有序部分
        mergeInPlace(arr, left, mid, right)
    }
}

// mergeInPlace 原地合并两个有序数组
func mergeInPlace(arr []int, left, mid, right int) {
    // 创建临时数组存储左半部分
    leftArr := make([]int, mid-left+1)
    copy(leftArr, arr[left:mid+1])
    
    // 创建临时数组存储右半部分
    rightArr := make([]int, right-mid)
    copy(rightArr, arr[mid+1:right+1])
    
    // 合并过程
    i, j, k := 0, 0, left
    
    for i < len(leftArr) && j < len(rightArr) {
        if leftArr[i] <= rightArr[j] {
            arr[k] = leftArr[i]
            i++
        } else {
            arr[k] = rightArr[j]
            j++
        }
        k++
    }
    
    // 复制剩余元素
    for i < len(leftArr) {
        arr[k] = leftArr[i]
        i++
        k++
    }
    
    for j < len(rightArr) {
        arr[k] = rightArr[j]
        j++
        k++
    }
}

// MergeSortInPlaceWrapper 原地归并排序包装函数
func MergeSortInPlaceWrapper(arr []int) {
    if len(arr) > 1 {
        MergeSortInPlace(arr, 0, len(arr)-1)
    }
}

带步骤显示的版本

package main

import "fmt"

var step int

// MergeSortWithSteps 带步骤显示的归并排序
func MergeSortWithSteps(arr []int, depth int) []int {
    step++
    indent := ""
    for i := 0; i < depth; i++ {
        indent += "  "
    }
    
    fmt.Printf("%s步骤 %d: 处理数组 %v (长度: %d)\n", 
               indent, step, arr, len(arr))
    
    if len(arr) <= 1 {
        fmt.Printf("%s数组长度 <= 1，直接返回\n", indent)
        return arr
    }
    
    mid := len(arr) / 2
    fmt.Printf("%s分割点: %d，分为 %v 和 %v\n", 
               indent, mid, arr[:mid], arr[mid:])
    
    fmt.Printf("%s递归排序左半部分:\n", indent)
    left := MergeSortWithSteps(arr[:mid], depth+1)
    
    fmt.Printf("%s递归排序右半部分:\n", indent)
    right := MergeSortWithSteps(arr[mid:], depth+1)
    
    fmt.Printf("%s合并 %v 和 %v\n", indent, left, right)
    result := mergeWithSteps(left, right, depth)
    fmt.Printf("%s合并结果: %v\n", indent, result)
    
    return result
}

// mergeWithSteps 带步骤显示的合并函数
func mergeWithSteps(left, right []int, depth int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    
    indent := ""
    for k := 0; k <= depth; k++ {
        indent += "  "
    }
    
    fmt.Printf("%s开始合并过程:\n", indent)
    
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            fmt.Printf("%s  选择 %d (来自左数组)\n", indent, left[i])
            result = append(result, left[i])
            i++
        } else {
            fmt.Printf("%s  选择 %d (来自右数组)\n", indent, right[j])
            result = append(result, right[j])
            j++
        }
    }
    
    // 添加剩余元素
    for i < len(left) {
        fmt.Printf("%s  添加剩余元素 %d (来自左数组)\n", indent, left[i])
        result = append(result, left[i])
        i++
    }
    
    for j < len(right) {
        fmt.Printf("%s  添加剩余元素 %d (来自右数组)\n", indent, right[j])
        result = append(result, right[j])
        j++
    }
    
    return result
}

func main() {
    // 测试基础版本
    arr1 := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("=== 基础归并排序 ===")
    fmt.Println("排序前:", arr1)
    sorted1 := MergeSort(arr1)
    fmt.Println("排序后:", sorted1)
    
    // 测试原地版本
    arr2 := []int{5, 2, 8, 1, 9, 3}
    fmt.Println("\n=== 原地归并排序 ===")
    fmt.Println("排序前:", arr2)
    MergeSortInPlaceWrapper(arr2)
    fmt.Println("排序后:", arr2)
    
    // 测试带步骤显示的版本
    arr3 := []int{5, 2, 8, 1}
    fmt.Println("\n=== 带步骤显示的归并排序 ===")
    fmt.Printf("初始数组: %v\n", arr3)
    step = 0
    result := MergeSortWithSteps(arr3, 0)
    fmt.Printf("最终结果: %v\n", result)
}

复杂度分析

时间复杂度

所有情况: O(n log n) - 无论输入数据如何，时间复杂度都是稳定的

空间复杂度

基础版本: O(n) - 需要额外的数组空间存储临时结果
原地版本: O(n) - 仍需要临时数组进行合并操作

算法特点

优点

稳定性: 相等元素的相对位置不会改变
时间复杂度稳定: 始终为O(n log n)，不受输入数据影响
可预测性: 性能稳定，适合对时间要求严格的场景
适合外部排序: 可以处理大于内存的数据集
并行化友好: 容易实现并行版本

缺点

空间复杂度高: 需要O(n)的额外空间
不是原地排序: 需要额外的存储空间
对小数组效率不高: 递归开销相对较大

优化策略

1. 小数组优化

// 对小数组使用插入排序
func MergeSortOptimized(arr []int) []int {
    if len(arr) <= 10 { // 小数组阈值
        return insertionSort(arr)
    }
    
    mid := len(arr) / 2
    left := MergeSortOptimized(arr[:mid])
    right := MergeSortOptimized(arr[mid:])
    
    return merge(left, right)
}

func insertionSort(arr []int) []int {
    result := make([]int, len(arr))
    copy(result, arr)
    
    for i := 1; i < len(result); i++ {
        key := result[i]
        j := i - 1
        
        for j >= 0 && result[j] > key {
            result[j+1] = result[j]
            j--
        }
        result[j+1] = key
    }
    
    return result
}

2. 自底向上的归并排序

// BottomUpMergeSort 自底向上的归并排序
func BottomUpMergeSort(arr []int) {
    n := len(arr)
    
    // 子数组大小从1开始，每次翻倍
    for size := 1; size < n; size *= 2 {
        // 对每个大小为size的子数组进行合并
        for left := 0; left < n-size; left += 2 * size {
            mid := left + size - 1
            right := min(left+2*size-1, n-1)
            
            mergeInPlace(arr, left, mid, right)
        }
    }
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

实际应用场景

归并排序广泛应用于：

外部排序: 处理大于内存的数据文件
稳定排序需求: 需要保持相等元素相对位置的场景
链表排序: 归并排序特别适合链表数据结构
并行计算: 容易实现并行版本
数据库系统: 大数据集的排序操作
分布式系统: MapReduce等框架中的排序阶段

性能测试

package main

import (
    "fmt"
    "math/rand"
    "time"
)

// 性能测试函数
func benchmarkMergeSort(size int) {
    // 生成随机数组
    arr := make([]int, size)
    for i := 0; i < size; i++ {
        arr[i] = rand.Intn(10000)
    }
    
    start := time.Now()
    MergeSort(arr)
    duration := time.Since(start)
    
    fmt.Printf("数组大小: %d, 排序时间: %v\n", size, duration)
}

// 比较不同输入情况下的性能
func comparePerformance() {
    size := 10000
    
    // 随机数组
    randomArr := make([]int, size)
    for i := 0; i < size; i++ {
        randomArr[i] = rand.Intn(10000)
    }
    
    // 已排序数组
    sortedArr := make([]int, size)
    for i := 0; i < size; i++ {
        sortedArr[i] = i
    }
    
    // 逆序数组
    reverseArr := make([]int, size)
    for i := 0; i < size; i++ {
        reverseArr[i] = size - i
    }
    
    // 测试随机数组
    start := time.Now()
    MergeSort(randomArr)
    fmt.Printf("随机数组排序时间: %v\n", time.Since(start))
    
    // 测试已排序数组
    start = time.Now()
    MergeSort(sortedArr)
    fmt.Printf("已排序数组排序时间: %v\n", time.Since(start))
    
    // 测试逆序数组
    start = time.Now()
    MergeSort(reverseArr)
    fmt.Printf("逆序数组排序时间: %v\n", time.Since(start))
}

func main() {
    fmt.Println("=== 归并排序性能测试 ===")
    sizes := []int{1000, 10000, 100000, 1000000}
    
    for _, size := range sizes {
        benchmarkMergeSort(size)
    }
    
    fmt.Println("\n=== 不同输入情况性能比较 ===")
    comparePerformance()
}

总结

归并排序是一个非常重要的排序算法，其稳定的O(n log n)时间复杂度和稳定性使其在许多场景中都有重要应用。虽然空间复杂度较高，但其可预测的性能和良好的稳定性使其成为许多系统中的首选排序算法。

关键要点:

使用分治法，递归地分解和合并数组
时间复杂度稳定为O(n log n)，空间复杂度为O(n)
是稳定的排序算法
适合外部排序和需要稳定性的场景
容易实现并行版本，适合大数据处理

排序算法-归并排序