3.12 归并排序

1. 归并排序

采用了分而治之的思想，就是说把一个大的问题分成小的问题，然后递归求解 不停地把数组拆成两半，直到有序（只有一个节点），最后进行合并

如果说快速排序的关键在于分，那么归并排序的关键在于合

2. 特点

• 稳定性：稳定
• 原地排序：不是
• 复杂度
  • 时间：O（nlogn）
    • 
    • 对于有序数组那么复杂度是O（N）

2026 注：对这里给出的标准归并排序实现，即使输入已有序，时间复杂度仍是 O(NlogN)。 - 空间：O（n）

• 相比较于插入排序，小规模的数据插入排序更快

3. 过程

• 
• 

4. 实现

//O(NlogN)
func MergeSort(data []model.Comparable) {
	mergeSort(data, 0, len(data)-1)
}

func merge2(data []model.Comparable, left int, mid int, right int) {
	length := right - left + 1
	tmp := make([]model.Comparable, length)
	i := left
	j := mid + 1
	k := 0
	for i <= mid && j <= right {
		if data[i].CompareTo(data[j]) >= 0 {
			tmp[k] = data[j]
			k++
			j++
		} else {
			tmp[k] = data[i]
			k++
			i++
		}
	}

	for i <= mid {
		tmp[k] = data[i]
		k++
		i++
	}
	for j <= right {
		tmp[k] = data[j]
		k++
		j++
	}

	k = 0
	i = left
	for i <= right {
		data[i] = tmp[k]
		i++
		k++
	}
}

func mergeSort(data []model.Comparable, left int, right int) {
	if left >= right {
		return
	}

	mid := (left + right) / 2
	mergeSort(data, left, mid)
	mergeSort(data, mid+1, right)

	merge(data, left, mid, right)
    //或者经典的
    //merge2(data, left, mid, right)
}

func merge(data []model.Comparable, left int, mid int, right int) {
	length := right - left + 1
	tmp := make([]model.Comparable, length)
	for i := 0; i < length; i++ {
		tmp[i] = data[i+left]
	}

	i := left
	j := mid + 1
	for k := left; k <= right; k++ {
		//左边的数组取完了
		if i > mid {
			data[k] = tmp[j-left]
			j++
		//右边的数组取完了
		} else if j > right {
			data[k] = tmp[i-left]
			i++
		//左边数组的元素<=右边数组的元素
		} else if tmp[i-left].CompareTo(tmp[j-left]) <= 0 {
			data[k] = tmp[i-left]
			i++
		//左边数组的元素>右边数组的元素
		} else {
			data[k] = tmp[j-left]
			j++
		}
	}
}

4.1. 测试

func TestMergeSort(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	MergeSort(data)
	fmt.Println(data)
}

5. 参考

• 排序算法之 归并排序 及其时间复杂度和空间复杂度_网络_YuZhiHui_No1的专栏-CSDN博客
• 排序算法稳定性_百度百科
• 归并排序的空间复杂度为什么是O（n）？快速排序的空间复杂度为什么是O（log2n）？_Java_taotao12312的博客-CSDN博客