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

归并排序是一种十分高效的稳定排序,每次合并操作的平均时间复杂度为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++
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论