常用排序算法之归并排序

归并排序(Merge Sort)

归并排序是创建在归并操作上的一种有效的排序算法,1945年由约翰·冯·诺伊曼首次提出.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。 -- 维基百科

归并排序算法采用分治思想+递归实现:

image.png

归并排序是一种十分高效的稳定排序,每次合并操作的平均时间复杂度为O(n),总的平均时间复杂度为O(nlogn)。

goloang code:

package main

import (
    "fmt"
    _ "os"
)

func main() {

    var arr = [9] int {9, 8, 7, 6, 5, 4, 3, 2, 1}
    mergeSort(&arr)
    fmt.Println(arr)
}

func mergeSort(arr *[9]int) {
    var temp = [len(arr)] int {}
    sort(arr, 0, len(arr) - 1, &temp)
}

func sort(arr *[9]int, left int, right int, temp *[9] int) {

    if left < right {
        mid := (left + right) / 2
        sort(arr, left, mid, temp)
        sort(arr, mid + 1, right, temp)
        merge(arr, left, mid, right, temp)
    }
}

func merge(arr *[9]int, left int, mid int, right int, temp *[9] int) {

    fmt.Println(left, mid, right)
    //os.Exit(1)

    i := left
    j := mid + 1
    t := 0

    for i <= mid && j <= right {

        if arr[i] <= arr[j] {
            temp[t] = arr[i]
            t++
            i++
        } else {
            temp[t] = arr[j]
            t++
            j++
        }
    }

    for i <= mid {
        temp[t] = arr[i]
        t++
        i++
    }

    for j <= right {
        temp[t] = arr[j]
        t++
        j++
    }

    t = 0
    for left <= right {
        arr[left] = temp[t]
        left++
        t++
    }

}

评论

暂无评论