归并排序

ByWhat'sUs

归并排序

所谓归并排序，指的是如果要排序一个数据序列，我们可以先把该序列从中间分成前后两部分，然后对这两部分分别做排序操作，再将排好序的两部分合并在一起，这样整个数据序列就都有序了。

归并排序使用了分治思想，分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。说到这里，可能你会联想起我们之前讲到的一个编程技巧 —— 递归，没错，归并排序就是通过递归来实现的。这个递归的公式是每次都将传入的待排序数据序列一分为二，直到变成不能继续分割的最小区间单元，然后将最小区间单元数据排序后合并起来，最终返回的就是排序好的数据序列了。

package main

import (
    "fmt"
)

// 归并排序
func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    // 获取分区位置
    p := len(nums) / 2
    // 通过递归分区
    left := mergeSort(nums[0:p])
    right := mergeSort(nums[p:])
    // 排序后合并
    return merge(left, right)
}

// 排序合并
func merge(left []int, right []int) []int {
    i, j := 0, 0
    m, n := len(left), len(right)
    // 用于存放结果集
    var result []int
    for {
        // 任何一个区间遍历完，则退出
        if i >= m || j >= n {
            break
        }
        // 对所有区间数据进行排序
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    // 如果左侧区间还没有遍历完，将剩余数据放到结果集
    if i != m {
        for ; i < m; i++ {
            result = append(result, left[i])
        }
    }

    // 如果右侧区间还没有遍历完，将剩余数据放到结果集
    if j != n {
        for ; j < n; j++ {
            result = append(result, right[j])
        }
    }

    // 返回排序后的结果集
    return result
}

func main() {
    nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
    sortedNums := mergeSort(nums)
    fmt.Println(sortedNums)
}

性能分析

• 归并排序不涉及相等元素位置交换，是稳定的排序算法；
• 时间复杂度是 O(nlogn)，要优于冒泡排序和插入排序的 O(n²)；
• 归并排序需要额外的空间存放排序数据，不是原地排序，最多需要和待排序数据序列同样大小的空间，所以空间复杂度是 O(n)。