归并排序的基本思想
将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。
综上可知:
归并排序其实要做两件事:
(1)“分解”——将序列每次折半划分。
(2)“合并”——将划分后的序列段两两合并后排序。
归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。
如 设有数列{6,202,100,301,38,8,1}
初始状态:6,202,100,301,38,8,1
第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;
第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;
第三次归并后:{1,6,8,38,100,202,301},比较次数:4;
总的比较次数为:3+4+4=11,;
package algomithms
import "fmt"
type MergeSort struct {
}
func (object MergeSort) Sort(values []int) {
mergeSort(values)
}
func mergeSort(values []int) {
length := len(values)
gap := 1
for gap < length {
fmt.Println(" --merge by gap ", gap)
mergebygap(values, gap)
gap = gap * 2
fmt.Println(" --the tuple is ", values)
}
}
func mergebygap(values []int, gap int) {
length := len(values)
for i := 0; i < length; i += 2 * gap {
mergeTwoValues(values, i, gap)
}
}
func mergeTwoValues(values []int, start int, gap int) {
// fmt.Println(" ---- try to merge", values[start:start+gap], "and ", values[start+gap:start+2*gap])
length := len(values)
if start+gap >= length {
return
}
slice := make([]int, 2*gap)
lpos, rpos, slicepos := start, start+gap, 0
for lpos < start+gap && (rpos < start+2*gap && rpos < length) {
if values[lpos] <= values[rpos] {
slice[slicepos] = values[lpos]
lpos++
} else {
slice[slicepos] = values[rpos]
rpos++
}
slicepos++
}
if lpos != start+gap {
for lpos < start+gap {
slice[slicepos] = values[lpos]
lpos++
slicepos++
}
} else if rpos != start+2*gap && rpos != length {
for rpos < start+2*gap && rpos < length {
slice[slicepos] = values[rpos]
rpos++
slicepos++
}
}
for i := 0; i < slicepos; i++ {
values[i+start] = slice[i]
}
fmt.Println(" ---- merge result is ", slice[:slicepos])
// fmt.Println(" ---- merge result is ", values[start:start+2*gap])
}
有疑问加站长微信联系(非本文作者)