九大排序算法及其Python实现之线性排序

输入：n个数的一个序列<a1,a2,...,an> (A[1..n]) 输出：输入序列的一个排序<b1,b2,...,bn>，满足b1≤b2≤...≤bn。

计数排序

思想

假设n个输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。 对每一个输入元素x，确定小于x的元素个数，利用这一信息，就可以直接把x放到它在输出数组中的位置上了。 >注:当有几个元素相同时，要略微修改此方案。

参考：Wiki百科：计数排序 ## 实现 伪代码：

# B[1..n] 存放排序的输出
# C[0..k] 提供临时存储空间
COUNTING-SORT(A, B, k)
    let C[0..k] be a new array
    for i = 0 to k # 将数组C的值置为0
        C[i] = 0
    for j = 1 to A.length
        C[A[j]] = C[A[j]] + 1
    # C[i]现在包含值为i的元素的个数
    for i = 1 to k
        C[i] = C[i] + C[i-1]
    # C[i]现在包含值不大于i的元素的个数
    # 从后往前遍历原数组以排序是保证排序算法稳定性的关键
    for j = A.length downto 1 
        B[C[A[j]]] = A[j]
        C[A[j]] = C[A[j]] - 1

1. Python实现（升序）

def COUNTING_SORT_ASC(A, B, k):
    C = [0 for i in range(0,k+1)] # 初始化C
    for i in range(0,len(A)): # 计数
        C[A[i]] += 1
    for i in range(1,k+1):
        C[i] = C[i]+C[i-1] # 计算最大位置
    for i in range(len(A)-1,-1,-1): # 把元素放在正确的位置上
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1

2. Python实现（降序）

def COUNTING_SORT_DESC(A, B, k):
    C = [0 for i in range(0,k+1)] # 初始化C
    for i in range(0,len(A)): # 计数
        C[A[i]] += 1
    for i in range(k-1,-1,-1): # 此处是与升序最大的不同
        C[i] = C[i]+C[i+1] # 计算最大位置
    for i in range(len(A)-1,-1,-1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1

## 图片说明 ## 复杂度 1. 空间复杂度：O(k+n) 2. 最差/平均/最优时间复杂度：O(k+n)

注意

1. 稳定的线性时间排序
2. 常用作基数排序算法的一个子过程
3. 由于下标是从0开始的，因此在实际实现过程中，最后的排序步骤需要把下标减一

基数排序

思想

先按最低有效位进行排序。

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

参考：Wiki百科：基数排序

实现

伪代码：

# 第1位是最低位，第d位师最高位
RADIX-SORT(A, d)
    for i = 1 to d
        use a stable sort to sort array A on digit i
# 常用计数排序来对A中元素的i位进行排序。算法修改如下
# k为单位数字最大值
RADIX-SORT(A, d, k)
    for i = 1 to d
        COUNTING-SORT(A, i, k)
COUNTING-SORT(A, h, k)
    let C[0..k] be a new array
    let B[1..n] be a new array
    for i = 0 to k #初始化C
        C[i] = 0
    for j = 1 to A.length # 计算A[j]出现的次数，将结果保存在C[A[j]]中
        ivalue = (A[j]%(10^h))/(10^(h-1)) # 计算A[j]第h位的值
        C[ivalue] = C[ivalue] + 1
    for i = 1 to k # C[i]包含小于或等于i的元素个数
        C[i] = C[i-1]
    for j = A.length downto 1
        ivalue = (A[j]%(10^h))/(10^(h-1)) # 计算A[j]第h位的值
        B[C[ivalue]] = A[j]
        C[ivalue] = C[ivalue] - 1
    copy B to A

1. Python实现（升序）

def RADIX_SORT_ASC(A, d, k):
    for i in range(1,d+1):
        COUNTING_SORT_ASC(A,i,k)
def COUNTING_SORT_ASC(A,h,k):
    B = A[:]
    C = [0 for _ in range(0,k+1)]
    for j in range(0,len(A)):
        ivalue = (A[j]%(10**h))/(10**(h-1)) #此处可以用lambda写个匿名函数
        C[ivalue] += 1
    for i in range(1,k+1): C[i] += C[i-1]
    for j in range(len(A)-1,-1,-1):
        ivalue = (A[j]%(10**h))/(10**(h-1))
        B[C[ivalue]-1] = A[j] #下标从0开始，因此需要-1，否则会下标越界
        C[ivalue] -= 1
    for j in range(0,len(A)): A[j] = B[j]

2. Python实现（降序）

def RADIX_SORT_DESC(A, d, k):
    for i in range(1,d+1):
        COUNTING_SORT_DESC(A,i,k)
def COUNTING_SORT_DESC(A,h,k):
    B = A[:]
    C = [0 for _ in range(0,k+1)]
    for j in range(0,len(A)):
        ivalue = (A[j]%(10**h))/(10**(h-1))
        C[ivalue] += 1
    for i in range(k-1,-1,-1): C[i] += C[i+1]
    for j in range(len(A)-1,-1,-1):
        ivalue = (A[j]%(10**h))/(10**(h-1))
        B[C[ivalue]-1] = A[j] #下标从0开始，因此需要-1，否则会下标越界
        C[ivalue] -= 1
    for j in range(0,len(A)): A[j] = B[j]

## 图片说明 ## 复杂度 1. 空间复杂度：O(k+n) , n是排序元素个数，k是单位数字最大值 2. 空间复杂度：O(d*n), n是排序元素个数，d是数字位数

注意

1. 此算法还可以用于字符串排序

桶排序

思想

假设输入是由一个随机过程产生，该过程将元素均与、独立地分布在[0,m)区间上

1. 将[0,m)区间划分为BUCKET_NUM个相同大小的子区间（桶）
2. 将n个输入数分别放到各个桶中
3. 对每个桶中的数进行排序
4. 遍历每个桶，按照次序把各个桶中的元素列出即可

参考：Wiki百科：基数排序

实现

伪代码：

# 输入的每个元素A[i]满足0≤A[i]x<1
# 临时数组B[0..BUCKET_NUM-1]存放链表（桶）
BUCKET-SORT(A)
    let B[0..BUCKET_NUM-1] be a new array
    for i = 0 to BUCKET_NUM-1
        make B[i] an empty list
    for i = 1 to A.length # 将输入数放到各个桶中
        insert A[i] into list B[int(BUCKET_NUM*A[i])]
    for i = 0 to BUCKET_NUM-1 # 对每个桶进行排序
        sort list B[i] with insertion sort
    concatenate the lists B[0], B[1], ..., B[BUCKET_NUM-1] together in order

1. Python实现（升序）

BUCKET_NUM = 10
def BUCKET_SORT_ASC(A):
    global BUCKET_NUM
    B = [[] for _ in range(0,BUCKET_NUM)] # 创建BUCKET_NUM个空桶
    for i in range(0,len(A)): # 将元素放到各自的桶中
        B[int(BUCKET_NUM*A[i])].append(A[i])
    for i in range(0,BUCKET_NUM):# 对桶中的数据进行排序
        #INSERTION_SORT_ASC(B[i])
        for p in range(1,len(B[i])):
            key,q = B[i][p],p-1
            while q>=0 and B[i][q] > key:
                B[i][q+1] = B[i][q]
                q -=1
            B[i][q+1] = key
    return reduce(lambda a,b:a+b,B) #将桶里的数据连接在一起

2. Python实现（降序）

def BUCKET_SORT_DESC(A):
    global BUCKET_NUM
    B = [[] for _ in range(0,BUCKET_NUM)] # 创建BUCKET_NUM个空桶
    for i in range(0,len(A)): # 将元素放到各自的桶中
        B[int(BUCKET_NUM*A[i])].append(A[i])
    for i in range(0,BUCKET_NUM):# 对桶中的数据进行排序(降序)
        #INSERTION_SORT_DESC(B[i])
        for p in range(1,len(B[i])):
            key,q = B[i][p],p-1
            while q>=0 and B[i][q]<key:
                B[i][q+1] = B[i][q]
                q -= 1
            B[i][q+1] = key
    return reduce(lambda a,b:a+b,B[::-1]) #将桶里的数据连接在一起（从后往前）

## 图片说明 ## 复杂度 1. 空间复杂度：O(n*k) 2. 最差时间复杂度：O(n^2), 平均时间复杂度：O(n+k)

注意

无

总结

稳定性(来自wiki)：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

名称	稳定性	时间复杂度	空间复杂度	描述
插入排序	Y	\[O(n^2)\]	\[O(1)\]	（有序区，无序区）从头到尾扫描数据，把无序区第一个数据插入到有序区
选择排序	N	\[O(n^2)\]	\[O(1)\]	（有序区，无序区）从头到尾扫描数据，把无序区最小的数据插入到有序区后面
冒泡排序	Y	\[O(n^2)\]	\[O(1)\]	（有序区，无序区）从头到尾扫描数据，无序区中从后开始扫描，不断把小的元素往前推至（通过交换）有序区后面
归并排序	Y	\[O(nlogn)\]	\[O(n)+O(logn)\]	分治法，递归将数列分成子数列，对子数列排序后合并
堆排序	N	\[O(nlogn)\]	\[O(1)\]	（有序区，无序区）构造二叉堆，将堆顶元素插入到有序区后面，然后再对新的无序区重建堆
快速排序	N	平均：\[O(nlogn)\] 最坏：\[O(n^2)\]	\[O(logn)\],\[O(n)\]	分治法。递归的将数列分成（小数，pivot，大数）
计数排序	Y	\[O(n+m)\]	\[O(n+m)\]	统计小于等于该元素的元素的个数i，该元素就放在目标数组的索引i位
基数排序	Y	平均：\[O(k*n)\] 最坏：\[O(n^2)\]	--	对元素的每一位进行单独排序，从低位开始，可以结合计数排序
桶排序	Y	\[O(n)\]	\[O(m)\]	把每个元素放在对应的桶中，对桶中元素进行排序后合并桶

说明： 1. 升序排序 2. k表示数值中的数位的个数 3. n表示数据规模 4. m表示数据的最大值与最小值之差