排序算法整理

前言

排序算法作为一种很基础的算法，用途很广，也有很多种算法，那时间一长，就容易忘，所以就按照自己的记忆习惯，整理下常见的排序算法，加深印象，忘了也更容易捡起来。

快排

快速排序，经典！必须要记住！

名称：Quicksort，partition-exchange sort

不可使用的场景：pass

对哪些场景有优势：

时间复杂度：平均情况下时间复杂度为O(NlogN); 最坏情况下O(N^2)

空间复杂度：

算法流程简述：

1. 选取一个待排数组中的一个元素的位置，可以称其为基点
   1. 基点的选取规则有很多种，一般分为默认选第一个，或者随机选择，这里使用随机选择
2. 比较得出该基点应该所处的位置，然后将数组划分为两部分，一部分（其所有元素）小于基点的值，另一部分大于基点的值。
3. 对划分出来的两部分进行递归的快速排序。

代码模版：

import random
def conversion(x):
    return x[0]

def indentity(x):
    return x
    
def quick_sort(nums,start,end):
    if start >= end:
        return
    
    idx = partition(nums,start,end)
    # print(f'start={start},end={end},idx={idx},nums={nums}')
    quick_sort(nums,start,idx-1)
    quick_sort(nums,idx+1,end)

def partition(nums,start,end,convert=indentity):
    '''随机定一个基点的位置，以基点为中心，划分数组为两部分，在基点的左边为小于等于基点的序列，右边为大于基点的序列'''
    if start >= end:
        return
    pivot = random.randint(start,end)
    origin = nums[pivot]
    swap(nums,start,pivot) # 把基点放到起始位置
    # print(f'start={start},end={end},pivot={pivot},val={origin}')
    l,r = start,end
    while l < r:
        # 先从右边开始遍历，这样在遇到第一个小于等于origin的值的时候，直接覆盖基点所在位置
        # 由于比较之后，不是进行交换，而是覆盖，那必然会丢失掉一个值，这个值如果是基点，那问题不大
        # 因为有保存基点的变量；如果是其他值的话，还需要进行保存
        while l < r and convert(nums[r]) > convert(origin):
            r -= 1
        nums[l] = nums[r]
        while l < r and convert(nums[l]) <= convert(origin):
            l += 1
        nums[r] = nums[l]
    nums[l] = origin # 把基点的值存上
    return l

def swap(nums,i,j):
    nums[i],nums[j] = nums[j],nums[i]

堆排

堆排序，经典！必须记住！

不可使用的场景：pass

对哪些场景有优势：

1. 在一堆数据中，选出前几个最大的或最重要的；或者反过来，选择最小的。这是因为堆排序所构建的树，根节点就是最大值或者最小值；

时间复杂度：O(NlogN) (数据长度为N)

空间复杂度：O(logN) (更新树的时候需要递归的对树遍历，其中所需要的栈的空间需要O(logN))

算法流程简述：

1. 构建一个完全二叉树，并且每个根节点都大于或者小于其子树中的节点

2. loop: 交换根节点和数组末尾的值，更新树，使其保持每个根节点都大于或者小于其子树中的节点

   直到树中只有一个节点终止。

代码模版：

'''输入的数组按完全二叉树进行展开，堆排序就是将无序的树转成大根堆或者小根堆
大根堆：树中的父节点比每个子节点都大
小根堆：树中的父节点比每个子节点都小
以大根堆为例，就是升序
'''

def compare_v1(nums,i,j):
    '''针对不同数组的结构，指定不同的比较函数
    数组nums只有int型数值
    '''
    if nums[i] > nums[j]:
        return True
    return False

def compare_v2(nums,i,j):
    '''数组nums中每一项是一个list'''
    if nums[i][0] > nums[j][0]:
        return True
    return False

def heap_sort(nums):
    ''' 升序排序'''
    n = len(nums)
    build_tree(nums, n)  # 构建一个树
    r = n-1
    while r > 0:
        swap(nums, 0, r)
        shift_down(nums, 0, r)
        r -= 1

def build_tree(nums, n):
    '''构建一个完全二叉树，并符合大根堆的特性，父节点的值'''
    i = ((n-1)-1)//2 #(n-1)对应树中最后一个节点
    while i > -1:
        shift_down(nums,i,n)
        i -= 1

def shift_down(nums,start,end,compare_fn=compare_v1):
    '''调整以root为根节点的树，使其树变为大根堆

    Args:
    nums (list): 输入的数组
    start (int): 根节点的位置
    end (int): 树的最大边界
    compare_fn (function): 比较函数
    '''
    parent = start
    child = 2*parent+1 # 左节点
    if child >= end:
        return
    # if child+1 < end and nums[child+1] >nums[child]:
    #     # 如果右节点存在,且比较大，则换右节点进行后续的比较和交换
    #     child += 1
    # if nums[parent] < nums[child]:
    #     swap(nums,parent,child)
    #     shift_down(nums,child,end)
    if child+1 < end and compare_fn(nums,child+1,child):
        child += 1
    if compare_fn(nums,child,parent):
        swap(nums,parent,child)
        shift_down(nums,child,end,compare_fn)
        
def add_element(nums,val,compare_fn=compare_v2):
    '''向优先队列里添加一个元素'''
    nums.append(val)
    n = len(nums)
    parent = ((n-1)-1)//2 # 最后一个元素的根节点的位置
    root_val = nums[parent][0]
    while parent > -1:
        shift_down(nums,parent,n,compare_fn)
        if nums[parent][0] == root_val:
            break
        parent = (parent-1)//2 # 再找到这个点的父节点
        root_val = nums[parent][0]
        
def swap(nums,i,j):
    tmp = nums[i]
    nums[i] = nums[j]
    nums[j] = tmp

经典问题：某一个数组，取前k个最小，最大，最接近等

这种问题可以用快排的思想（代码需要改改），也可以使用堆排序（几乎不用改）

参考资料

1. 堆和树的区别 https://www.zhihu.com/question/36134980