Go语言实现归并排序

归并排序

先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序的实现过程

实现代码

//n为要排序数组的元素个数
func MergeSort(array *[]int, n int) {
	MergeSortDetail(array, 0, n-1)
}

//l,r分别为需要排序的数组的最左、最右元素的下标
func MergeSortDetail(array *[]int, l, r int) {
	if l >= r {
		return
	}
	//分解过程
	mid := (r + l) / 2
	MergeSortDetail(array, l, mid)
	MergeSortDetail(array, mid+1, r)
	//合并过程
	if (*array)[mid] > (*array)[mid+1] {
		Merge(array, l, mid, r)
	}
}

func Merge(array *[]int, l, mid, r int) {
	//temp为需要合并的两个数组无序合并而成的数组，方便下面遍历比较，再调整原数组的元素成有序状态
	temp := make([]int, r+1)
	for i := l; i <= r; i++ {
		temp[i] = (*array)[i]
	}
	//定义两个要合并的数组第一个元素的下标
	i := l
	j := mid + 1
	for k := l; k <= r; k++ {
		//需要合并的两个数组的下标不可以越界,设置判断条件i > mid,j > r
		if i > mid {
			(*array)[k] = temp[j]
			j++
		} else if j > r {
			(*array)[k] = temp[i]
			i++
		} else if temp[j] < temp[i] {
			(*array)[k] = temp[j]
			j++
		} else {
			(*array)[k] = temp[i]
			i++
		}
	}

}

func main() {
	array := []int{39, 2, 5, 23, 54, 12, 78, 34, 45, 40}
	MergeSort(&array, len(array))
	for i, v := range array {
		fmt.Printf("下标为%d的值为%d", i, v)
		fmt.Println()
	}
}

总结

1. 空间复杂度：归并排序不是原地排序算法，在合并两个数组的过程中需要借助额外的空间，空间复杂度是O(n)。
2. 稳定性：归并排序是稳定的排序算法，在合并[l,mid] [mid+1,r]过程中，如果两个区间中有相同的元素，可以处理[l,mid]中的元素，从而保证稳定性。
3. 时间复杂度：归并排序的时间复杂度是 O(nlogn)。从代码中可以看到，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。