归并排序

2021-03-31 | 129 浏览

归并排序

归并排序是利用递归与分治技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成为越来越大的有序序列.归并排序中,"归"代表的是递归的意思,既递归的将数组折半的分离为单个数组,例如数组:{2,6,1,0},会先折半,分为{2,6}和{1,0}两个子数组,然后再折半将数组分离,分为{2},{6}和{1},{0},"并"就是将分开的数据按照从小到大或者从大到小的顺序再放到一个数组中,如上面的{2}{6}合并到一个数组中是{2,6},{1},{0}合并到一个数组中是{0,1},然后再将{2,6}和{0,1}合并到一个数组中是{2,6},{1},{0}合并到一个数组中是{0,1},然后再将{2,6}和{0,1}合并到一个数组中既为{0,1,2,6}.

具体而言,归并排序算法的原理如下:对于给定的一组记录,首先将每两个相邻的长度为1的子序列进行归并,得到n/2(向上取整)个长度为2或1的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列为止

所以归并排序的关键就是两步,第一步,划分子表;第二步,合并半子表

package main

import "fmt"

func Merge(array []int, p, q, r int) {
	n1 := q - p + 1
	n2 := r - q
	L := make([]int, n1)
	R := make([]int, n2)

	for i, k := 0, p; i < n1; i, k = i+1, k+1 {
		L[i] = array[k]
	}
	for i, k := 0, q+1; i < n2; i, k = i+1, k+1 {
		R[i] = array[k]
	}
	var i, k, j int
	for i, k, j = 0, p, 0; i < n1 && j < n2; k++ {
		if L[i] > R[j] {
			array[k] = L[i]
			i++
		} else {
			array[k] = R[j]
			j++
		}
	}
	if i < n1 {
		for j = i; j < n1; j, k = j+1, k+1 {
			array[k] = L[j]
		}
	}
	if j < n2 {
		for i = j; i < n2; i, k = i+1, k+1 {
			array[k] = R[i]
		}
	}
	fmt.Printf("排序过程: %v\n", array)
}

func MergeSort(array []int, p, r int) {
	if p < r {
		q := (p + r) / 2
		MergeSort(array, p, q)
		MergeSort(array, q+1, r)
		Merge(array, p, q, r)
	}
}
func main() {
	array := []int{5, 11, 100, 2, 6, 23, 65, 9, 98, 48, 24, 16}
	MergeSort(array, 0, len(array)-1)
	fmt.Println("排序结果如下:")
	fmt.Println(array)
}

排序过程如下

[administrator@administrator-dev 20210330]$ go run  03.go 
排序过程: [11 5 100 2 6 23 65 9 98 48 24 16]
排序过程: [100 11 5 2 6 23 65 9 98 48 24 16]
排序过程: [100 11 5 6 2 23 65 9 98 48 24 16]
排序过程: [100 11 5 23 6 2 65 9 98 48 24 16]
排序过程: [100 23 11 6 5 2 65 9 98 48 24 16]
排序过程: [100 23 11 6 5 2 65 9 98 48 24 16]
排序过程: [100 23 11 6 5 2 98 65 9 48 24 16]
排序过程: [100 23 11 6 5 2 98 65 9 48 24 16]
排序过程: [100 23 11 6 5 2 98 65 9 48 24 16]
排序过程: [100 23 11 6 5 2 98 65 48 24 16 9]
排序过程: [100 98 65 48 24 23 16 11 9 6 5 2]
排序结果如下:
[100 98 65 48 24 23 16 11 9 6 5 2]

二路归并排序的过程需要进行logn趟,每一趟归并排序的操作,就是将两个有序子序列进行归并,而每一次有序子序列归并时,记录的比较次数均小于等于记录的移动次数,二路归并排序的时间复杂度为O(nlogn)

算法