注：排序算法的稳定性指相等的元素在排序前后相对位置是否变化，稳定排序主要用于不同键值比较，比如ACM成绩排序，先按分数排序，相同分数再按用时最短排序。

冒泡排序

不断比较相邻元素，每次遍历将最大值移至队尾。

def bubble(arr):
    swapped = True
    end = len(arr)
    while swapped:
        swapped = False
        for i in range(1, end):
            if arr[i-1] > arr[i]:
                arr[i-1], arr[i] = arr[i], arr[i-1]
                swapped = True
        end -= 1
    return arr

选择排序

每次遍历找到一个最小值，将其移至队首。

def selection(arr):
    for start in range(len(arr)-1):
        mini = start
        for i in range(start+1, len(arr)):
            if arr[i] < arr[mini]:
                mini = i
        arr[start], arr[mini] = arr[mini], arr[start]
    return arr

插入排序

很像打麻将，每摸到一张牌，就依次比较将其插入正确的位置。

def insertion(arr):
    for cur in range(len(arr)):
        for i in range(cur-1, -1, -1):
            if arr[cur] < arr[i]:
                arr[cur], arr[i] = arr[i], arr[cur]
                cur = i
            else:
                break
    return arr

归并排序

分分合合

def merge(arr):
    l = len(arr)
    if l <= 1:
        return arr
    arrleft = merge(arr[:l//2])
    arright = merge(arr[l//2:])
    res = []
    while arrleft or arright:
        if arrleft and arright:
            res.append(arrleft.pop(
                0) if arrleft[0] < arright[0] else arright.pop(0))
        elif arrleft:
            res.append(arrleft.pop(0))
        elif arright:
            res.append(arright.pop(0))
    return res

快速排序

选一个基准，然后将基准放在正确的位置上，并保证左边比基准小，右边比基准大，再一直递推下去。

def quick(arr):
    def _quick(i, j):
        if i >= j:
            return
        # 这里选取左端点为参考点
        pivot = arr[i]
        low = i
        high = j
        while i != j:
            # 从右往左 找小于pivot的
            while i < j and arr[j] >= pivot:
                j -= 1
            arr[i] = arr[j]
            # 从左往右 找大于pivot的
            while i < j and arr[i] <= pivot:
                i += 1
            arr[j] = arr[i]
        arr[i] = pivot
        _quick(low, i-1)
        _quick(i+1, high)
        return arr
    return _quick(0, len(arr)-1)

堆排序

每次将堆顶元素和最后一个元素交换，交换后上浮

class HeapSort:
    def __init__(self, arr):
        self.arr = arr
        self.len = len(arr)
        for i in range(len(arr)//2, -1, -1):
            self.heapify(i)

    def heapify(self, i):
        left = 2*i+1
        right = 2*i+2
        largest = i
        if left < self.len and self.arr[left] > self.arr[largest]:
            largest = left
        if right < self.len and self.arr[right] > self.arr[largest]:
            largest = right

        if largest != i:
            self.swap(i, largest)
            self.heapify(largest)

    def swap(self, a, b):
        self.arr[a], self.arr[b] = self.arr[b], self.arr[a]


def heapSort(arr):
    heapq = HeapSort(arr)
    for i in range(len(arr)-1, 0, -1):
        heapq.swap(0, i)
        heapq.len -= 1
        heapq.heapify(0)
    return heapq.arr

计数排序

统计每个数字出现的次数，然后依次取出，适合都是整数且数字集中的场景。

def count(arr):
    if not arr:
        return arr
    minn = min(arr)
    maxn = max(arr)
    dic = {n: 0 for n in range(minn, maxn+1)}
    for n in arr:
        dic[n] += 1
    res = []
    for n in range(minn, maxn+1):
        res += [n]*dic[n]
    return res

基数排序

先创建10个队列（0~9桶），先按个位放入桶中，然后依次清空桶，然后是十位...
适合整数，数据跨度较大的场景。

def radix(arr):
    buckets = [[] for _ in range(10)]
    flag = True
    rad = 1
    while flag:
        flag = False
        for n in arr:
            buckets[n // rad % 10].append(n)
            if not flag and n % rad < n:
                flag = True
        i = 0
        for bucket in buckets:
            while bucket:
                arr[i] = bucket.pop(0)
                i += 1
        rad *= 10
    return arr

桶排序

每个桶有不同的范围，桶内有自己的排序算法

参考

https://visualgo.net/zh/sorting