归并排序,自顶向下与自底向上两种方式(golang实现)

Tue Sep 5, 2017

300 Words|Read in about 1 Min
Tags: 算法  

封装成函数:

//自顶向下归并排序
func MergeSortUpToDown(s []int) {
	aux := make([]int, len(s)) //辅助切片
	mergeSortUpToDown(s, aux, 0, len(s)-1)
}
 
//自底向上归并排序
func MergeSortDownToUp(s []int) {
	aux := make([]int, len(s)) //辅助切片
	n := len(s)
	for sz := 1; sz < n; sz *= 2 {
		for lo := 0; lo < n-sz; lo += 2 * sz {
			merge(s, aux, lo, lo+sz-1, min(lo+2*sz-1, n-1))
		}
	}
}
 
func mergeSortUpToDown(s, aux []int, lo, hi int) {
	if lo >= hi {
		return
	}
	mid := (lo + hi) >> 1
	mergeSortUpToDown(s, aux, lo, mid)
	mergeSortUpToDown(s, aux, mid+1, hi)
	merge(s, aux, lo, mid, hi)
}
 
//归并操作
func merge(s, aux []int, lo, mid, hi int) {
	for k := lo; k <= hi; k++ {
		aux[k] = s[k]
	}
	i, j := lo, mid+1
	for k := lo; k <= hi; k++ {
		if i > mid {
			s[k] = aux[j]
			j++
		} else if j > hi {
			s[k] = aux[i]
			i++
		} else if aux[j] < aux[i] {
			s[k] = aux[j]
			j++
		} else {
			s[k] = aux[i]
			i++
		}
	}
}
 
func min(i, j int) int {
	if j < i {
		return j
	}
	return i
}

测试:

s := []int{9,0,6,5,8,2,1,7,4,3}
fmt.Println(s)
MergeSortUpToDown(s)
//MergeSortDownToUp(s)
fmt.Println(s)

输出:

[9 0 6 5 8 2 1 7 4 3]
[0 1 2 3 4 5 6 7 8 9]

See Also

Tue Sep 5, 2017

300 Words|Read in about 1 Min
Tags: 算法