[数据结构与算法]超全的排序算法总结——Python

排序算法总结

一些准备工作

import numpy as np
import time

# 交换元素
def swap(array, i, j):
    array[i], array[j] = array[j], array[i]

# 创建 0~1000 的 n 个随机数
def create_random(n):
    return np.random.randint(0, 1000, n)

# 测试array是否是升序
def is_order(array, correct_array):
    length = len(array)
    for i in range(length):
        if array[i] != correct_array[i]:
            return False
    return True

# 计算排序所花费的时间
def test_fun(array,sort_fun,order_fun):
    # 排序出正确的答案
    correct_array = np.sort(array)
    # 排序结束
    before_time = time.time()
    sort_fun(array)
    after_time = time.time()
    require_time = after_time - before_time
    # 排序结束
    
    # 判断结果是否正确
    order_ret = order_fun(array, correct_array)
    # 输出结果
    time_ret = ' {0} takes {1} seconds to sorting {2} int32 numbers!!!'.format(str(sort_fun).split(' ')[1], 
                                                     require_time, len(array))
    return 'Success!!!' + time_ret if order_ret else 'Defeat!!!' + time_ret

1、冒泡排序

def Bubble_Sort(array):
    length = len(array)
    if length <= 1:
        return
    for i in range(length):
        flag = False
        for j in range(length - i - 1):
            if array[j] > array[j + 1]:
                swap(array, j, j + 1)
                flag = True
        if not flag:
            break

print(test_fun(create_random(10000), Bubble_Sort, is_order))

Success!!! Bubble_Sort takes 25.275135040283203 seconds to sorting 10000 int32 numbers!!!

2、鸡尾酒排序

def CockTail_Sort(array):
    length = len(array)
    i, j = 0, length
    while i < j:
        # 将大泡冒到最后面
        for index in range(i + 1, j):
            if array[index - 1] > array[index]:
                swap(array, index - 1, index)
        j -= 1  # 更改排序区间
        # 将小泡冒到最前面
        for index in range(j - 1, i, -1):
            if array[index - 1] > array[index]:
                swap(array, index - 1, index)
        i += 1

print(test_fun(create_random(10000), CockTail_Sort, is_order))

Success!!! CockTail_Sort takes 34.09252619743347 seconds to sorting 10000 int32 numbers!!!

3、选择排序

def Select_Sort(array):
    length = len(array)
    if length <= 1:
        return
    for i in range(length):
        min_index = i
        for j in range(i, length):
            if array[j] < array[min_index]:
                min_index = j
        swap(array, i, min_index)

print(test_fun(create_random(10000), Select_Sort, is_order))

Success!!! Select_Sort takes 12.891336917877197 seconds to sorting 10000 int32 numbers!!!

4、插入排序

def Insert_Sort(array, start=0, gap=1):
    length = len(array)
    if length <= 1:
        return

    for i in range(start + gap, length, gap):
        index = i
        tmp = array[index]
        while index > start and array[index - gap] > tmp:
            array[index] = array[index - gap]
            index -= gap
        array[index] = tmp

print(test_fun(create_random(10000), Insert_Sort, is_order))

Success!!! Insert_Sort takes 8.749930381774902 seconds to sorting 10000 int32 numbers!!!

5、希尔排序

def Shell_Sort(array):
    length = len(array)
    if length <= 1:
        return
    
    gap = length // 2  # python // 表示对最后的结果取整
    
    while(gap >= 1):
        for i in range(gap):
            Insert_Sort(array, i, gap)  # 对插入排序算法复用
        gap //= 2

print(test_fun(create_random(1000000), Shell_Sort, is_order))

Success!!! Shell_Sort takes 17.48081064224243 seconds to sorting 1000000 int32 numbers!!!

6、堆排序

建堆的时间复杂度计算（设最后形成的完全二叉树有$h$层）：

$T=1?2^{h?1}+2?2^{h?2}+3?2^{h?3}+...+(h?1)?2^1+h?2^0$

将$h=lo{g}_2(n)$带入上式得建堆的时间复杂度为$O(n)$

排序的时间复杂度计算：
每一个节点最差要下沉$O(logn)$次，故总时间复杂度为$O(nlogn)$
故堆排序时间复杂度为$O(n)+O(nlogn)=O(nlogn)$

# parent = (child - 1) / 2
# left_child = 2 * parent + 1
# right_child = 2 * parent + 2
# 因为为了升序 故构建大根堆

# 通过 adjust_up 构建堆
def adjust_up(array):
    length = len(array)
    
    for i in range(1, length):
        index = i
        parent = int((index - 1) / 2)
        
        while array[index] > array[parent] and parent >= 0:
            swap(array, index, parent)
            index = parent
            parent = int((index - 1) / 2)
# 通过 adjust_down 将数据融进堆 
def adjust_down(array, heap_len):  # heap_len 堆的长度
    index = 0
    max_i = 2 * index + 1
    
    if max_i >= heap_len:
        return
    
    if max_i + 1 < heap_len and array[max_i] < array[max_i + 1]:  # 使得 max_i 指向两个子节点的最大值
         max_i += 1
            
    while array[index] < array[max_i]:
        swap(array, index, max_i)
        index = max_i
        max_i = 2 * index + 1
        
        if max_i >= heap_len:
            return
        
        if max_i + 1 < heap_len and array[max_i] < array[max_i + 1]:  # 使得 max_i 指向两个子节点的最大值
            max_i += 1
def Heap_Sort(array):
    length = len(array)
    
    if length <= 1:
        return
    # 将 array 构建成 heap
    adjust_up(array)
    heap_len = length
    
    while heap_len > 1:
        swap(array, 0, heap_len - 1)
        heap_len -= 1
        adjust_down(array, heap_len)

print(test_fun(create_random(1000000), Heap_Sort, is_order))

Success!!! Heap_Sort takes 27.513195753097534 seconds to sorting 1000000 int32 numbers!!!

7、快速排序

快速排序时间复杂度计算：

在分析快排的时间复杂度时，可以将函数的调用看做成一个二叉树，最优的情况是是一个完全二叉树，层数为$logn$，最差的情况是二叉树只有一个边，这种情况下二叉树的层数变成了$n$，这种情况只会在数组完全倒序的情况下发生，因此在进行快排之前要进行一次洗牌以打乱数组，故对于快排而言，数组越乱，性能越高。对于每一层，都会将数组的所有元素遍历一遍，因此每一层的时间复杂度为$O(n)$。因此快排的时间复杂度为$O(nlogn)$。

快速排序空间复杂度计算：

快排用到了递归，因此主要的空间复杂度即为函数栈帧的建立，根据上面不难得出，最优情况下会创建$nlogn$个栈帧，最差情况下会创建$n^2$个栈帧，因此排序前对数组洗牌非常关键。故快排的时间复杂度为$O(nlogn)$。

def __Quick_Sort(array, left, right):
    base_num = array[left]
    i = left
    j = right

    while i < j:
        while i < j and array[j] >= base_num:
            j -= 1

        while i < j and array[i] <= base_num:
            i += 1

        if j != i:
            swap(array, j, i)
    
    swap(array, left, i)
    return i
    
def _Quick_Sort(array, left, right):
    if left >= right:  # 递归的出口
        return None

    mid = __Quick_Sort(array, left, right)
    
    _Quick_Sort(array, left, mid)
    _Quick_Sort(array, mid + 1, right)

def Quick_Sort(array):
    length = len(array)
    if length <= 1:
        return
    np.random.shuffle(array) # 重新打乱牌序
    _Quick_Sort(array, 0, length - 1)

print(test_fun(create_random(1000000), Quick_Sort, is_order)) 

Success!!! Quick_Sort takes 78.20122027397156 seconds to sorting 1000000 int32 numbers!!!

8、快速排序（非递归）

from queue import Queue  # 导入 python 内置 Queue 模块
def Quick_Sort_Non_Recurse(array):
    length = len(array)
    if length <= 1:
        return
    que = Queue()
    que.put(0), que.put(length - 1)
    while not que.empty():  # empty() 队列为空返回 True
        left ,right = que.get(), que.get()
        mid = __Quick_Sort(array, left, right)
        if right - left + 1 > 2:  # 只有两个以上的元素排序后需要进队列 
            if left < mid:
                que.put(left), que.put(mid)  # 左边的一对区间
            if mid + 1 < right:
                que.put(mid + 1), que.put(right)  # 右边的一对区间

print(test_fun(create_random(1000000), Quick_Sort_Non_Recurse, is_order))

Success!!! Quick_Sort_Non_Recurse takes 96.13525390625 seconds to sorting 1000000 int32 numbers!!!

9、归并排序

def Merge(array, tmp_array, low, mid, high):
    index = low
    p1, p2 = low, mid + 1
    end_p1, end_p2 = mid, high

    while(p1 <= end_p1 and p2 <= end_p2):
        if array[p1] <= array[p2]:
            tmp_array[index] = array[p1]
            p1 += 1
        else:
            tmp_array[index] = array[p2]
            p2 += 1
        index += 1
    while p1 <= end_p1:
        tmp_array[index] = array[p1]
        index += 1
        p1 += 1
    while p2 <= end_p2:
        tmp_array[index] = array[p2]
        index += 1
        p2 += 1      
    # 拷贝到原数组
    for i in range(low, high + 1):
        array[i] = tmp_array[i]
        
def _Merge_Sort(array, tmp_array, low, high):
    # 递归的出口
    if low == high:
        return
    mid = int((low + high) / 2)
    _Merge_Sort(array, tmp_array, low, mid)
    _Merge_Sort(array, tmp_array, mid + 1, high)
    # 将分开的数组合并
    Merge(array, tmp_array, low, mid, high)
    
    
def Merge_Sort(array):
    length = len(array)
    if length <= 1:
        return
    tmp_array = np.zeros(length, dtype=int)
    _Merge_Sort(array, tmp_array, 0, length - 1)

print(test_fun(create_random(1000000), Merge_Sort, is_order))

Success!!! Merge_Sort takes 14.850624799728394 seconds to sorting 1000000 int32 numbers!!!

10、基数排序

创建一个获取最大数位数的函数，这个函数的返回值决定排序的次数

排序的循环体：
创建 0~9 共十个 bucket 用于存放比较当前位时，元素的个数，但应注意每一次排序前要清空
遍历一遍原数组，将当前位元素的个数分配给各个 bucket
更新 bucket ，统计在当前第 n 个 bucket 以及前面的所有 bucket 共有多少元素，以便后续获取当前排序元素在 tmp 数组中的位置
获取当前排序的元素的对应位的数值k，然后 bucket[k]-1 即为当前元素在tmp数组中的位置，同时 bucket[k] -= 1
最后，将 tmp 数组 copy 到原数组

# 统计array中最大数的位数
def MaxBit(array):
    length = len(array)
    maxNum = array[0]
    for i in range(length):
        if array[i] > maxNum:
            maxNum = array[i]
    d = 1
    while maxNum >= 10:
        maxNum /= 10
        d += 1
    
    return d
# 获取当前数的第k位的数值
def get_k_num(num, k):
    for i in range(k):
        num = int(num / 10)
    return num % 10
# 基数排序
def Radix_Sort(array):
    length = len(array)
    if length <= 1:
        return
    # 创建一个长度为length的数组
    tmp = np.zeros(length, dtype=int)
    # 获取最大数的位数，即排序的次数
    radix = MaxBit(array)
    # 创建10个空桶
    buckets = np.zeros(10, dtype=int)
    for j in range(radix):
        # 清空桶
        buckets -= buckets
        # 统计装入桶的元素个数
        for i in range(length):
            buckets[get_k_num(array[i], j)] += 1
        # 更新bucket
        for i in range(1, 10):
            buckets[i] = buckets[i - 1] + buckets[i]
        # 将排序后的数放到tmp中
        for i in range(length):
            # 要倒着来排序
            index = length - i - 1
            tmp[buckets[get_k_num(array[index], j)] - 1] = array[index]
            buckets[get_k_num(array[index], j)] -= 1

        # 将tmp的元素copy到array中
        for i in range(length):
            array[i] = tmp[i]

print(test_fun(create_random(1000000), Radix_Sort, is_order))

Success!!! Radix_Sort takes 12.643389463424683 seconds to sorting 1000000 int32 numbers!!!

11、计数排序

在遇到范围比较小且数据量非常大的情况下，计数排序性能是不错的

# 寻找最大数
def M_Num(array):
    length = len(array)
    max_num = array[0]
    min_num = array[0]
    for i in range(length):
        if array[i] > max_num:
            max_num = array[i]
        if array[i] < min_num:
            min_num = array[i]
    return min_num, max_num
# 算法本体
def Count_Sort(array):
    length = len(array)
    if length <= 1:
        return
    tmp_array = np.array(array)
    min_num, max_num = M_Num(array)
    buckets = np.zeros(max_num - min_num + 1, dtype=int)
    for i in range(length):
        buckets[tmp_array[i] - min_num] += 1
    for i in range(1, len(buckets)):
        buckets[i] += buckets[i - 1]
    for i in range(length - 1, -1, -1):
        array[buckets[tmp_array[i] - min_num] - 1] = tmp_array[i]
        buckets[tmp_array[i] - min_num] -= 1

print(test_fun(create_random(1000000), Count_Sort, is_order))

Success!!! Count_Sort takes 8.175300121307373 seconds to sorting 1000000 int32 numbers!!!

12、桶排序

def M_Num(array):
    length = len(array)
    max_num = array[0]
    min_num = array[0]
    for i in range(length):
        if array[i] > max_num:
            max_num = array[i]
        if array[i] < min_num:
            min_num = array[i]
    return min_num, max_num

def Bucket_Sort(array, bucket_num=10):
    length = len(array)
    if length <= 1:
        return
    min_num, max_num = M_Num(array)
    bucket_size = int((max_num - min_num) / bucket_num) + 1
    buckets = []
    for i in range(bucket_num):
        buckets.append([])
    for i in range(length):
        bucket_index = int((array[i] - min_num) / bucket_size)
        buckets[bucket_index].append(array[i])

    for i in range(bucket_num):
        Quick_Sort(buckets[i])

    index = 0
    for i in range(bucket_num):
        #bucket_len = len(buckets[i])
        for j in buckets[i]:
            array[index] = j
            index += 1

print(test_fun(create_random(1000000), Bucket_Sort, is_order))

Success!!! Bucket_Sort takes 44.678382873535156 seconds to sorting 1000000 int32 numbers!!!

猴子排序

作者写这个排序纯粹是为了搞笑的，哈哈哈哈

def is_in_order(array):
    length = len(array)
    for i in range(1, length):
        if array[i - 1] > array[i]:
            return False
    return True

def Monkey_Sort(array):
    while not is_in_order(array):
        np.random.shuffle(array)

print(test_fun(create_random(10), Monkey_Sort, is_order))

Success!!! Monkey_Sort takes 21.361676454544067 seconds to sorting 10 int32 numbers!!!