合并排序是一种基于分而治之技术排序的方法，最坏的情况下复杂度为O（n log n）。

合并排序首先将数组分成相等的一半，然后已排序方式组合他们。

原理解析

声明一个未排序的数组

image

将数组分成两段

image

再将两个数组分成两半

image

一直分下去，直到不能再分为止。

image

现在，我们以完全相同的方式将它们组合在一起。请注意这些列表的颜色代码。

我们首先比较每个列表的元素，然后以排序的方式将它们组合到另一个列表中。我们看到14和33处于排序位置。我们比较27和10并且在2个值的目标列表中我们首先放置10个，然后是27.我们改变19和35的顺序，而顺序地放置42和44。

image

继续组合

image

在最终合并以后，列表如下：

image

代码实现

GO

package main

import (
    "fmt"
)

func main() {
    numbers := []int{14, 33, 27, 10, 35, 19, 42, 44}
    fmt.Printf("%v\n", numbers)
    numbers = MergeSort(numbers)
    fmt.Printf("%v\n", numbers)
}
func MergeSort(numbers []int) []int {
    length := len(numbers)
    //数组不可再分
    if length <= 1 {
        return numbers
    }
    //评分两个数组。
    mid := length / 2
    //递归进行，持续分割
    array1, array2 := MergeSort(numbers[0:mid]), MergeSort(numbers[mid:length])
    //分组完成，合并分组数据
    return Merge(array1, array2)
}
func Merge(array1, array2 []int) []int {
    len1 := len(array1)
    len2 := len(array2)
    //获取数据长度
    lmax := len1
    if lmax < len2 {
        lmax = len2
    }
    if lmax < 1 {
        return array1
    }
    var ret []int
    //需要合并数组元素下标
    index1 := 0
    index2 := 0
    for true {
        if index2 >= len2 && index1 >= len1 {
            //所有数据排序完毕，退出循环
            break
        }
        if index1 < len1 && index2 < len2 {
            // 两个数组 同时存在元素
            if array1[index1] < array2[index2] {
                ret = append(ret, array1[index1])
                index1++
            } else {
                ret = append(ret, array2[index2])
                index2++
            }
        } else if index1 < len1 {
            //array1 单独存在元素
            ret = append(ret, array1[index1])
            index1++
        } else if index2 < len2 {
            //array2 单独存在元素
            ret = append(ret, array2[index2])
            index2++
        }
    }
    return ret
}

Python

numbers = [14, 33, 27, 10, 35, 19, 42, 44]


def merge_sort(lo, hi):
    if lo >= hi:
        return
    else:
        mid = int((lo + hi) / 2)
        #print(lo, mid, hi, "\n")
        merge_sort(lo, mid)
        merge_sort(mid + 1, hi)
        merge(lo, mid, hi)


def merge(lo, mid, hi):
    loIndex = lo
    hiIndex = mid

    merged = []
    while True:
        if loIndex < mid and hiIndex <= hi:
            if numbers[loIndex] < numbers[hiIndex]:
                merged.append(numbers[loIndex])
                loIndex += 1
            else:
                merged.append(numbers[hiIndex])
                hiIndex += 1

        elif loIndex < mid:
            # array1 单独存在元素
            merged.append(numbers[loIndex])
            loIndex += 1
        elif hiIndex <= hi:
            # array2 单独存在元素
            merged.append(numbers[hiIndex])
            hiIndex += 1

        if loIndex >= mid and hiIndex > hi:
            break

    for i in range(0, len(merged), 1):
        numbers[i + lo] = merged[i]


print("排序前：", numbers)
merge_sort(0, len(numbers) - 1)
print("排序后：", numbers)

#排序前： [14, 33, 27, 10, 35, 19, 42, 44]
#排序后： [10, 14, 19, 33, 27, 35, 42, 44]

长按二维码关注我们