归并排序 O(n*log2(n))

分：把列表一分为二，得到两个有序列表
治：合并两个有序列表

递归地拆分列表，当拆分出来的列表只含有单个元素的时候，自然是有序的，可以作为递归的终止条件

在这里插入图片描述

'''
归并排序
'''
def mergeSort(nums):
    if len(nums)==1:
        return nums
    s = len(nums)//2
    sa,sb = mergeSort(nums[:s]),mergeSort(nums[s:])
    ans = doMerge(sa,sb)
    return ans
def doMerge(sa,sb):
    ans = []
    i = j = 0
    while(i<len(sa) and j <len(sb)):
        if sa[i]<=sb[j]:  # 等号保证排序稳定（元素相等的时候，sb中的元素插在后面）
            elem = sa[i]
            i+=1
        else:
            elem = sb[j]
            j+=1
        ans.append(elem)
    ans.extend(sa[i:])
    ans.extend(sb[j:])
    return ans

堆排序

堆的性质

堆的实现通过构造二叉堆（binary
heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。

任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

来源维基百科堆积性质

由此可知，大根堆的子树也是大根堆

用数组存一棵完全二叉树，通过下标获取某个已知节点的关联节点

若数组下标从0开始

已知父节点为i, 则左孩子为：2i+1，右孩子为 2i+2
已知孩子节点为j，则父节点为 (j-1)//2

若数组下标从1开始

已知父节点为i, 则左孩子为：2i，右孩子为 2i+1
已知孩子节点为j，则父节点为 j//2

在这里插入图片描述

本文大根堆数组下标都从0开始

方案1 自底向上调整大根堆O(n^2)

从最后一个非叶结点开始调整，让这个节点比后裔大，一直到root节点比后裔大，再将root节点放在末尾。这样，最大的数就排在了数组的末尾。再把倒数第二大的数字，放在数组倒数第二的位置，依此类推。

'''
堆排序 -- 自底向上调整
目前时间复杂度：O(n^2)
'''
def heapSort(nums):
    for end in range(len(nums)-1,-1,-1):
        doheapSort(nums,end)
    return nums

def doheapSort(nums,end):
    root = (end-1) // 2  # 最后一个非叶节点的下标
    while(root>=0):
        left = root*2+1
        right = root*2+2
        if nums[left]>nums[root]:
            nums[left], nums[root] = nums[root],nums[left]
        if nums[right] > nums[root] and right<=end:
            nums[right], nums[root] = nums[root], nums[right]
        root-=1
    # root -1 # 倒数第二个非叶节点的下标
    nums[0], nums[end] = nums[end], nums[0]

方案2 自顶向下调整大根堆O(n*log2(n))

先构建一个大根堆（每一个节点都大于等于后裔），把root和数组末尾的值交换，再自顶向下调整（末尾这个数字已经是确保是最大值，因此下一次大根堆的数组不包括原来数组基础上的末尾元素）

'''
O(n*log2(n))
'''
def heapSort(nums):  # O(n * log2(n))
    generateBigheap(nums) # O(n * log2(n))
    for end in range(len(nums)-1,-1,-1): # O(n * log2(n))
        nums[0], nums[end] = nums[end], nums[0]
        down_adjust(nums,0,end-1)
    return nums

def generateBigheap(nums): # O(n * log2(n))
    for root in range((len(nums)-2)//2,-1,-1):
        print(root)
        left = root*2+1
        right = left+1
        maxelem = left if right>len(nums)-1 or nums[right]<nums[left] else right
        if nums[root]>nums[maxelem]:continue
        nums[maxelem], nums[root] = nums[root], nums[maxelem]
        down_adjust(nums, maxelem,len(nums)-1)
def down_adjust(nums,root,end): # O(log2(n))
    while root * 2 + 1 <end:
        left = root * 2 + 1
        right = left + 1
        maxelem = left if right>end or nums[right]<nums[left] else right
        if nums[root] > nums[maxelem]: break
        nums[maxelem], nums[root] = nums[root], nums[maxelem]
        root = maxelem

快排 O(n*log2(n))

主要用到了基准元素和双指针，以及递归思想

双指针移动和 leetcode 11,42,407, 容器，接雨水，二维雨水，坑文中对墙的移动相似。本文中每次数组被修改位置的指针，向着另一个指针的方向挪动1位
双指针每一次碰头的时候，基准元素到达了最终位置。草图中展示了双指针一次碰头的过程。
找到了最终位置的基准元素将列表一分为二，下一步需要递归地去找下一个基准元素的位置，直到找到所有的基准元素

快排草图

在这里插入图片描述

def quickSort(nums,start,end):
    i = start
    j = end
    if start>=end:return
    base = i
    b = nums[base]
    while i<j:
        while nums[j] >= b and i<j:j-=1
        nums[i] = nums[j]
        while nums[i]<=b and i<j:i+=1
        nums[j] = nums[i]
    nums[i] = b
    quickSort(nums,start,j-1)
    quickSort(nums,j+1,end)

ans = quickSort(nums,0,len(nums)-1)