常用的排序算法

一、复杂度

排序方式	平均T(n)	最坏T(n)	最好T(n)	空间复杂度	稳定性
插入排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定
冒泡排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
希尔排序	O(n^1.3)	O(n^2)	O(n)	O(1)	不稳定
快速排序	O(nlogn)	O(n^2)	O(nlogn)	O(logn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(n+rd)	稳定

二、代码实现

1、直接插入排序 insert

# 将 L[i] 插入到已经有序的子序列 L[1 2 ... i-1] 中

def InsertSort(arr):
    for i in range(1, len(arr)):
        j = i
        while j > 0 and arr[j] < arr[j-1]:
            arr[j], arr[j-1] = arr[j-1], arr[j]
            j -= 1

2、冒泡排序 bubble

# 对相邻的元素两两进行比较，顺序相反则进行交换，这样每一趟最大的元素浮到顶端

def BubbleSort(arr):
    for i in range(len(arr)-1):
        for j in range(len(arr)-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

3、简单选择排序 select

# 第i趟排序从 L[i,i+1,...,n] 中选择关键字最小的元素与 L[i] 比较
# 每一趟从待排序的数据元素中选择最小的元素作为首元素

def SelectSort(arr):
    for i in range(len(arr)-1):
        minv = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[minv]:
                minv = j
        if minv != i:
            arr[minv], arr[i] = arr[i], arr[minv]

4、希尔排序 shell（跳着插入排序）

距离为 di 的记录放在同一个组中，进行直接插入排序
di = 4, 2, 1

def ShellSort(arr):
    step = len(arr) / 2
    while step > 0:
        for i in range(step, len(arr)):  # 插入排序
            j = i
            while j >= step and arr[j] < arr[j-step]:
                arr[j], arr[j-step] = arr[j-step], arr[j]
                j -= step
        step = step / 2

5、快速排序 quick

待排序表 L[1,2,...,n] 中任取一个元素 pivot 作为基准或枢纽，
将表划分成两部分，一部分小于 pivot，一部分大于或等于 pivot
L[1,2,...,k-1] 和 L[k+1,...,n] , L[k] = pivot

操作：
以当前表中第一个元素作为枢纽，对表进行划分
将表中比枢纽值大的元素向右移动，小的向左移动
移动采用从两端往中间夹入的方式（可用于求n个元素中第k小的元素）

def Partition(arr, begin, end):  # 划分元素
    pivot = arr[begin]  # 选取第一个元素作为基准
    left = begin + 1
    right = end
    while True:
        while left <= right and arr[left] <= pivot:
            left += 1
        while left <= right and arr[right] >= pivot:
            right -= 1
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
        else:
            break
    arr[begin], arr[right] = arr[right], pivot # 划分元素放到中间位置
    return right  # 返回划分元素的下标

def QuickSort(arr, begin, end):
    if begin < end:
        k = Partition(arr, begin, end)
        Partition(arr, begin, k-1)
        Partition(arr, k+1, end)

6、堆排序 heap sort

大顶堆（完全二叉树）：子节点小于父节点
建堆 A[0,2,...,n-1]，移除根节点，将A[0]与A[n-1]交换，
做最大堆调整的递归运算，建堆 A[0,2,...,n-2]，将A[0]与A[n-2]交换，
直到 A[0]与A[1]交换
思想可用于求大量元素中最小的或最大的几个元素

def MaxHeap_adjust(arr, low, high):
    tmp = arr[low]  # 父节点
    while 2 * low + 1 <= high:
        child = 2 * low + 1  # 左子节点
        if child < high and arr[child] < arr[child+1]:
            child += 1
        if arr[child] < tmp:
            break
        arr[low] = arr[child]
        low = child
    arr[low] = tmp

def MaxHeapSort(arr):
    n = len(arr)
    for i in range(n/2-1, -1, -1):  # 从下往上调
        MaxHeap_adjust(arr, i, n-1)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 最大值放最后面
        MaxHeap_adjust(arr, 0, i-1)  # 重新调整一下

7、二路归并排序 merge（分治）

n 个记录看成是 n 个有序的子表，两两归并，得到 n/2 个有序表，再归并

def Merge(left, right):
    i, j = 0, 0
    res = []  # 缺点：需要辅助空间
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res += left[i:] if i < len(left) else right[j:]
    return res

def MergeSort(arr):
    if len(arr) <= 1:
        return arr
    middle = len(arr) / 2
    left = MergeSort(arr[:middle])
    right = MergeSort(arr[middle:])
    return Merge(left, right)

8、基数排序 radix（桶排序）

1 2	对数字最高位优先和最低位优先进行排序例如：先按个位从小到大，再按十位从小到大，再按百位从小到大