注:本文已发布超过一年,请注意您所使用工具的相关版本是否适用
说明
归并排序:是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用
步骤
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
- 重复步骤 3 直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
示例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| package merge
const INFINITY = 0xffff
func merge(arr []int, start, end int) { if start < end { mid := (end + start) / 2 merge(arr, start, mid) merge(arr, mid+1, end)
arr1 := make([]int, mid-start+2) copy(arr1, arr[start:mid+1]) arr1[mid-start+1] = INFINITY
arr2 := make([]int, end-mid+1) copy(arr2, arr[mid+1:end+1]) arr2[end-mid] = INFINITY
j, k := 0, 0 for i := start; i <= end; i++ { if arr1[j] <= arr2[k] { arr[i] = arr1[j] j++ } else { arr[i] = arr2[k] k++ } }
} }
|
关注我获取更新
猜你喜欢