Golang 归并排序MergeSort

思路

将一排数据，进行左右不断地进行划分（递[归]），然后再对比左右两边的数据后再(合[并])，这就是”归并排序“。

注意：[左右]对比，是指左的第一个元素，与右边的第一个元素进行对比，哪个小，就先放到结果的第一位，然后左或右取出了元素的那边的索引进行++，没有取出的元素的，则不用进行++。比较完后，还要分别将左，右的剩余的元素，追加到结果列的后面。

归并排序(MergeSort)

package main

import "fmt"

import "time"
import number "github.com/emacsist/go-common/helper/number"

func main() {
	data := number.GenerateInt(100000, 100000)
	start := makeTimestamp()
	// fmt.Printf("%v\n", data)
	data = mergeSort(data)
	fmt.Printf("cost %v ms \n", makeTimestamp()-start)
	// fmt.Printf("%v\n", data)
}

//------------------------------------------------------------------------------

func makeTimestamp() int64 {
	return time.Now().UnixNano() / int64(time.Millisecond)
}

func mergeSort(data []int) []int {
	if len(data) <= 1 {
		return data
	}
	//递[归]
	middle := len(data) / 2
	//不断地进行左右对半划分
	left := mergeSort(data[:middle])
	right := mergeSort(data[middle:])
	//合[并]
	return merge(left, right)
}

func merge(left, right []int) (result []int) {
	l, r := 0, 0

    // 注意：[左右]对比，是指左的第一个元素，与右边的第一个元素进行对比，哪个小，就先放到结果的第一位，然后左或右取出了元素的那边的索引进行++
	for l < len(left) && r < len(right) {
        //从小到大排序.
		if left[l] > right[r] {
			result = append(result, right[r])
            //因为处理了右边的第r个元素，所以r的指针要向前移动一个单位
			r++
		} else {
			result = append(result, left[l])
            //因为处理了左边的第r个元素，所以r的指针要向前移动一个单位
			l++
		}
	}
    // 比较完后，还要分别将左，右的剩余的元素，追加到结果列的后面(不然就漏咯）。
	result = append(result, left[l:]...)
	result = append(result, right[r:]...)
	return
}

Contents

思路

归并排序(MergeSort)