leetcode刷题记录：归并排序和快速排序

1. 快速排序

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/kuai-su-pa-39aa2/

1.1 快排基础

先看核心代码

def sort(nums, lo, hi):
    if (lo >= hi):
        return
    p = partition(nums, lo, hi)
    sort(nums, lo, p-1)
    sort(nums, p+1, hi)

一句话总结快排：先将一个元素排好序(nums[p])，再将剩下的元素排好序

快排的核心是partition函数，其作用是在nums[lo, …, hi]中寻找一个切分点索引p, 让nums[lo,...,p] <= nums[p] < nums[p+1, ..., hi]，注意这里的边界条件，是小于等于和大于。即把nums[p]放到正确的位置上；再用递归把左边和右边的部分都排好序即可，其实就是一个二叉树的前序遍历。

partition函数的结果类似一个二叉搜索树，nums[p]是根节点，左边是左子树，右边是右子树。或者说，快排就是一个构造二叉搜索树的过程。

但是有可能会碰到极端不平衡的情况，比如每次选出的p都在两端，导致左子树或者右子树为空，这样时间复杂度会大幅度上升，因此需要增加数组的随机性。

class Solution(object):
    def quickSort(self, nums, lo, hi):
        if (lo >= hi):
            return
        p = self.partition(nums, lo, hi)
        self.quickSort(nums, lo, p-1)
        self.quickSort(nums, p+1, hi)
    def partition(self, nums, lo, hi):
        import random
        pivot_idx = random.randint(lo, hi)   
        self.swap(nums, lo, pivot_idx)                # 随机选择pivot
        pivot = nums[lo]
        i, j = lo+1, hi
        while i <= j:            
            while i < hi and nums[i] <= pivot:
                i += 1
            while j > lo and nums[j] > pivot:
                j -= 1                
            if (i >= j):
                break                
            self.swap(nums, i, j)
        self.swap(nums, lo, j)
        return j
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        self.quickSort(nums, 0, len(nums)-1)
        return nums

1.2 快排变体：三路快排解决相同元素的case

以上方法是传统的两路快排，缺点是leetcode上有个[2,2,2,2…]的相同元素case过不了(官方的c++题解都过不了)。这里可以用以下三路排序的方式来解决，把整个数组分成<pivot, =pivot 和 >pivot三段来解决。
代码如下，详细思路可以参考： https://www.runoob.com/data-structures/3way-qiuck-sort.html

class Solution(object):
    def quickSort(self, nums, l, r):
        import random
        if (l >= r):
            return
        self.swap(nums, l, random.randint(l, r))
        pivot = nums[l]
        # index
        lt, gt = l, r
        i = l + 1
        while (i <= gt):
            if (nums[i] < pivot):
                self.swap(nums, i, lt+1)
                i += 1
                lt += 1                
            elif (nums[i] > pivot):
                self.swap(nums, i, gt)
                gt -= 1
            else:
                i += 1
        self.swap(nums, l, lt)
        self.quickSort(nums, l, lt-1)
        self.quickSort(nums, gt+1, r)
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        self.quickSort(nums, 0, len(nums)-1)
        return nums

时间复杂度：
主要的时间复杂度在partition循环里。第一次partition函数的执行时间最长，是数组总的元素数，所以partition的时间复杂度是O(N).
假设切分点每次都落在中间，类比一个二叉树，数的深度是logN，一共要执行logN次partion函数。所以理想的时间复杂度是O(NlogN)

空间复杂度：空间复杂度就是递归栈的深度，即O(logN)

假设数组的分布不均匀，每次partition的长度从N开始递减，时间复杂度是
N + N-1 + N-2 + … + N-(N-1) = N^2 - (N-1)N/2 = N^2/2+N/2 => O(N^2)
这个时候树的深度是N，因此空间复杂度是O(N)

1.3 快排衍生：快速选择 Quick Select

快速选择是快排的变体，例子是leetcode215题：数组中的第k个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/

解法一：二叉堆（优先队列）

一些基本的定义：

堆：一颗用数组表示的特殊的树。我们主要讨论二叉堆，即对应的是二叉树。这颗树需要满足以下条件
- 完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都集中在左部连续位置
- 堆中每一个节点的值都必须大于等于（或小于等于）其左右子节点的值。前者叫大顶堆，后者叫小顶堆
大顶堆：即任何一个父节点的值，都大于等于它左右孩子节点的值。
小顶堆：即任何一个父节点的值，都小于等于它左右孩子节点的值。
堆的建立：这里先跳过
堆的操作：删除、添加
优先队列：优先队列也是一种队列，只不过其入队和出队顺序是按照优先级来的；支持插入和删除最小值操作（返回并删除最小元素）或删除最大值操作（返回并删除最大元素）；对应的数据结构就是小顶堆和大顶堆
本题用二叉堆的解法：

解法二：快速选择

先抄一个解法，有个case会超时，明天再看下。再不休息就要死了啊啊啊啊

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def quickSelect(nums, lo, hi, k):
            lt, gt = partition(nums, lo, hi)
            if lt > k:
                return quickSelect(nums, lo, lt-1, k)
            elif gt < k:
                return quickSelect(nums, gt+1, hi, k)
            else:
                return nums[lt]
            
        def partition(nums, lo, hi):
            import random
            p = random.randint(lo, hi)
            pivot = nums[p]
            swap(nums, lo, p)
            lt, gt, i = lo, hi+1, lo+1
            # print("before:", nums, lt, gt, i)
            while i < gt:
                if nums[i] < pivot:
                    swap(nums, i, lt+1)
                    i += 1
                    lt += 1
                elif nums[i] > pivot:
                    gt -= 1
                    swap(nums, i, gt)
                else:
                    i += 1
            swap(nums, lo, lt)
            # print("after:", nums, lt, gt, i)
            return lt, gt-1
        def swap(nums, i, j):
            nums[i], nums[j] = nums[j], nums[i]
        # print("nums:", nums)
        if not nums:
            return 
        k = len(nums) - k
        return quickSelect(nums, 0, len(nums)-1, k)

2. 归并排序

归并排序采用分而治之(divide-and-conquer)的思想。

分：将问题分解成一个个小的子问题然后递归求解
治：将解决好的问题merge在一起。
即先让每个子序列有序，再让子序列之间有序，即可完成数组的排序。
图片示例：https://blog.csdn.net/python_tian/article/details/122086920

归并排序的思路和代码框架

归并排序就是先把左半边数组排好序，再把右半边数组排好序，然后把两半数组合并。

def sort(nums, lo, hi):
    if lo == hi:
        return nums
    mid = lo + (hi-lo)//2
    sort(nums, lo, mid)
    sort(nums, mid+1, hi)
    # 后序位置
    merge(nums, lo, mid, hi)
def merge(nums, lo, mid, hi):
    pass

在二叉树的纲领篇(记得放link)我们说过，二叉树问题有两种解法，一是遍历一遍二叉树，而是分解问题。从上面这段代码可以看出，归并排序就是分解二叉树的解法。
归并排序的逻辑可以抽象成一个二叉树的后序遍历。树上每个结点的值是nums[lo:hi], 其中左子树是nums[lo:mid-1], 右子树是nums[mid+1:hi]，根节点是nums[mid].
然后在每个节点的后序位置执行merge函数，合并两个子节点上的子数组。
时间复杂度O(nlogn), 空间O(n)

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """        
        n = len(nums)
        if n <= 1:
            return nums
        self.temp = [0] * n
        self.mergeSort(nums, 0, n-1)
        return nums
    def mergeSort(self, nums, lo, hi):
        if lo >= hi:
            return
        mid = lo + (hi-lo)//2
        self.mergeSort(nums, lo, mid)
        self.mergeSort(nums, mid+1, hi)
        self.merge(nums, lo, mid, hi)
    def merge(self, nums, lo, mid, hi):
        # 合并两个有序数组.
        for i in range(lo, hi+1):
            self.temp[i] = nums[i]
        i, j = lo, mid+1
        for p in range(lo, hi+1):
            if i == mid+1:
                # 左半边数组已经全部被合并
                nums[p] = self.temp[j]
                j += 1
            elif j == hi+1:
                # 右半边数组已经全部被合并
                nums[p] = self.temp[i]
                i += 1
            elif self.temp[i] > self.temp[j]:
                nums[p] = self.temp[j]
                j += 1
            else:
                nums[p] = self.temp[i]
                i += 1

归并排序的应用：计算右侧小于当前元素的个数

leetcode315 https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
构造一个pair class，key是元素值，value是index
merge函数中arr[i] = temp[p1]时更新count

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        class Pair(object):
            def __init__(self, key, val):
                self.key = key
                self.val = val
        def mergeSort(arr, lo, hi):
            if lo >= hi:
                return
            mid = lo  + (hi-lo)//2
            mergeSort(arr, lo, mid)
            mergeSort(arr, mid+1, hi)
            merge(arr, lo, mid, hi)
        def merge(arr, lo, mid, hi):
            idx = lo
            p1, p2 = lo, mid+1
            for i in range(lo, hi+1):
                temp[i] = arr[i]
            for i in range(lo, hi+1):
                if p1 == mid+1:
                    arr[i] = temp[p2]
                    p2 += 1
                elif p2 == hi+1:
                    arr[i] = temp[p1]
                    count[temp[p1].val] += p2-mid-1
                    # print(temp[p1].val, count)
                    p1 += 1 
                elif temp[p1].key <= temp[p2].key:
                    arr[i] = temp[p1]
                    count[temp[p1].val] += p2-mid-1
                    p1 += 1                    
                else:
                    arr[i] = temp[p2]
                    p2 += 1            
        arr = [Pair(nums[i], i) for i in range(len(nums))]
        temp = [Pair(0, i) for i in range(len(nums))]
        count = [0 for _ in range(len(nums))]
        mergeSort(arr, 0, len(arr)-1)
        return count