AK F.*ing leetcode 流浪计划之归并排序

LightningBilly · 2021 年5 月 5 日 11:47

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

一、简介

归并排序是基础排序之一，其核心算法是合并2个有序数组。利用合并有序数组算法，自底向上先合并2个数，再4个数，直到整个数组有序。在面试中也经常被问到其原理，甚至会让手写归并排序。合并有序数组算法在解题中经常用到，学习与解理归并排序算法原理，对于解决算法题都是非常有帮助的。防止在面试时眼高手低。

这里主要以int为例，讲解原理，以及排序的实现。最后结合题目讲解归并排序的应用。

本文中归并原理参照严版《数据结构与算法》，公众号内回复“数据结构”可以获取pdf电子版。

二、基本概念

归并排序定义为MergeSort(arr, low, high)

每次先用再对左右部分分别进行排序 MergeSort(arr, low, mid), MergeSort(arr, mid+1, high)保证左右子数组有序再调用merge进行左右子数组合并。

其核心算法是merge算法merge(arr, low, high)。

其作用是将arr[low] 到 arr[high]合并，保持有序。

三、作用

对数组进行排序。
对链表进行排序。
合并2个有序数组/链表。
合并多个有序数组。
求解数组逆序对。

四、方法定义及算法

方法定义

    // 主要操作：
    Merge(arr, low, high) // 核心合并
	MergeSort(arr, low, high) // 归并排序

算法描述

merge过程
图1 merge算法过程

这里merge过程，先把原数组复制到另一个数组，然后最后结果从小到大依次填入到原数组中。

Merge(arr, low, high): // merge算法, 如图动画
	copyArr <- arr[low:high+1]
	mid <- (low+high)/2
	i<- low
	j<- mid+1
	s<-low
	while (i<=mid || j<=high) {
		// j>high 时，只能取copyArr[i-low]
		// 否则，就尝试比较copyArr[i-low]<=copyArr[j-low]
		if (j>high || (i<=mid && copyArr[i-low]<=copyArr[j-low])) {
			arr[s]<-copyArr[i-low]
			s<-s+1
			i<-i+1
		} else { // 除以上情况就只能取copyArr[j-low]
			arr[s]<-copyArr[j-low]
			s<-s+1
			j<-j+1
		}
	}


MergeSort(arr, low, high): // 归并排序
	if low>=high { // 少于一个元素，不用排序
		return
	}
	
	mid <- (low+high)/2
	MergeSort(arr, low, mid) // 先使左边有序
	MergeSort(arr, mid+1, high) // 再使右边有序
	Merge(arr, low, high) // 合并左右两边，使整个有序

五、具体实现

package main

import (
	"fmt"
)

func Merge(arr []int, low, high int) {
	copyArr := make([]int, high-low+1)
	copy(copyArr, arr[low:high+1])
	mid := (low + high) / 2
	for i, j, s := low, mid+1, low; i <= mid || j <= high; s++ {
		// j>high 时，只能取arr[i-low]
		// 否则，就尝试比较arr[i-low]<=arr[j-low]
		if j > high || (i <= mid && copyArr[i-low] <= copyArr[j-low]) {
			arr[s], i = copyArr[i-low], i+1
		} else { // 除以上情况就只能取arr[j-low]
			arr[s], j = copyArr[j-low], j+1
		}
	}
}

func MergeSort(arr []int, low, high int) {
	if low >= high { // 少于一个元素，不用排序
		return
	}

	mid := (low + high) / 2
	MergeSort(arr, low, mid)    // 先使左边有序
	MergeSort(arr, mid+1, high) // 再使右边有序
	Merge(arr, low, high)       // 合并左右两边，使整个有序
}

func main() {
	arr := []int{10, 6, 7, 12, 18, 12, 1, 2, 4, 3}
	MergeSort(arr, 0, len(arr)-1)
	fmt.Println(arr)

	arr = []int{1, 1, 1, 1, 1}
	MergeSort(arr, 0, len(arr)-1)
	fmt.Println(arr)

	arr = []int{}
	MergeSort(arr, 0, len(arr)-1)
	fmt.Println(arr)

	arr = []int{1}
	MergeSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

复杂度分析，MergeSort最多递归log(n) 层, 每层合并总数是N个数，整体复杂度O(nlog(n))。

六、牛刀小试

练习1 验证代码是否正确，排序应用

题目链接力扣

题目大意

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

题目解析

对原数组进行排序，调用归并排序方法即可。

AC代码

func Merge(arr []int, low, high int) {
	copyArr := make([]int, high-low+1)
	copy(copyArr, arr[low:high+1])
	mid := (low + high) / 2
	for i, j, s := low, mid+1, low; i <= mid || j <= high; s++ {
		// j>high 时，只能取arr[i-low]
		// 否则，就尝试比较arr[i-low]<=arr[j-low]
		if j > high || (i <= mid && copyArr[i-low] <= copyArr[j-low]) {
			arr[s], i = copyArr[i-low], i+1
		} else { // 除以上情况就只能取arr[j-low]
			arr[s], j = copyArr[j-low], j+1
		}
	}
}

func MergeSort(arr []int, low, high int) {
	if low >= high { // 少于一个元素，不用排序
		return
	}

	mid := (low + high) / 2
	MergeSort(arr, low, mid)    // 先使左边有序
	MergeSort(arr, mid+1, high) // 再使右边有序
	Merge(arr, low, high)       // 合并左右两边，使整个有序
}

func sortArray(nums []int) []int {
    MergeSort(nums, 0, len(nums)-1)
    return nums
}

练习2 利用归并排序原理，对链表进行排序

题目链接：力扣,

题目大意

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

题目解析

可以有2种方法：归并排序，爬楼梯排序（C++ 列表排序算法）

参考之前的文章：头条面试题之链表排序

练习3 合并2个有序数组

题目链接：力扣

题目大意

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[i] <= 10^9

题目解析

由于nums1空间是m+n, 可以利用倒序遍历进行merge, 实现O(1)空间复杂度。

AC代码

func merge(nums1 []int, m int, nums2 []int, n int)  {
    for i, j, s := m-1, n-1, m+n-1; s>=0;s-- {
        if j<0 || (i>=0 && nums1[i]>=nums2[j]) {
            nums1[s]=nums1[i]
            i--
        } else {
            nums1[s]=nums2[j]
            j--
        }
    }
}

练习4 合并多个有序链表

题目链接：力扣

题目大意

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：

输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

题目解析

有2种方法：1. 利用堆每次取到最小的数字放到ans中。2. 利用归并排序思想，对链表两两合并，直到剩下一个链表。

由于这里讲解的是归并排序的应用，给出的解答没有涉及到堆。

思路及优化

暴力思路如下：

func mergeKLists(lists []*ListNode) *ListNode {
  ans := &ListNode{}
  for _, l:= range lists{ // 每次拿一个链表合并到最终结果中
    ans = Merge(ans, l)
  }
  
  return ans
}

复杂度分析，最外层一共是len(lists) 次，每次最差情况是所有链表长度总和（L）, 总复杂度是 O(len(lists)*L), 大约是 500 *(10^4)*500 = 25*10^8 操作数太大了，会超时。

优化如下：

/*
利用归并思想，先将左右2边分别合并成一个链表，最后再合并左右2边成一个链表。
*/
func mergeKLists(lists []*ListNode) *ListNode {
  if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	if len(lists) == 2 {
		return Merge(lists[0], lists[1])
	}
  // 以上情况如果数组<=2元素就直接合并了
  // 否则就先分成左右2边合并，再整体合并
	mid := len(lists) / 2
	a := mergeKLists(lists[:mid])
	b := mergeKLists(lists[mid:])
	return Merge(a, b)
}

复杂度分析：根据归并原理，一共需要log(len(lists))层，每层总操作数是所有数字个数L, 总体复杂度是 O(log(len(lists))*L), 大约是 log(500) *(10^4)*500 = 45*10^6 操作数，勉强可以接受。

AC代码

func Merge(a, b *ListNode) *ListNode {
	ans := &ListNode{}
	temp := ans

	for ;a != nil || b != nil;temp = temp.Next {
		if b == nil || (a != nil && a.Val <= b.Val) {
			temp.Next = a
			a = a.Next
		} else {
			temp.Next = b
			b = b.Next
		}
	}
    temp.Next = nil
	return ans.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	if len(lists) == 2 {
		return Merge(lists[0], lists[1])
	}
	mid := len(lists) / 2
	a := mergeKLists(lists[:mid])
	b := mergeKLists(lists[mid:])
	return Merge(a, b)
}

七、总结

主要内容：

归并排序是基础排序之一，其核心算法是合并2个有序数组。利用合并有序数组算法，自底向上先合并2个数，再4个数，直到整个数组有序。
介绍了merge算法原理。
作用：1）对数组进行排序, 2)对链表进行排序, 3)合并2个有序数组/链表, 4) 合并多个有序数组, 5)求解数组逆序对。

笔者水平有限，有写得不对或者解释不清楚的地方还望大家指出，我会尽自己最大努力去完善。

下面我精心准备了几个流行网站上的题目（首先AK F.*ing leetcode），给大家准备了一些题目，供大家练习参考。干他F.*ing (Fighting?)。

八、实战训练

代码基础训练题

光说不练假把式，学完了怎么也要实操一下吧，快快动用把刚才那4题A了。

排序应用力扣
利用归并排序原理，对链表进行排序：力扣
合并2个有序数组：力扣
合并多个有序链表: 力扣

AK leetcode

leetcode相关题目都在下面了，拿起武器挨个点名呗。

力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
力扣
https://leetcode.com/problems/sort-list/

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。

在这里插入图片描述