比较

各类排序算法复杂度

排序时间比较表：(单位：秒)

几点说明：

• 上表中空的位置，是因为Python快速排序递归超过了递归深度，所以报错没输出了

• 关于冒泡排序和选择排序

  • 它们的时间复杂度都为 O(n^2)，那么为什么排序时间差别这么大呢？因为虽然它们排序的比较次数一致，但它们的交换次数不一样。对于冒泡排序，最优交换次数为0，只需要比较n次；对于选择排序，最优交换次数为n次，需要比较 n^2 次。
  • 在大规模无序数据排序情况下，选择排序比冒泡排序快，选择排序只需交换n次，冒泡排序可能要交换n^2次。
  • 在有序数据排序情况下，冒泡排序比选择排序快，冒泡排序只需比较n次，选择排序需要比较 n^2次。

• 快速排序和归并排序效率最好。

附Python代码:

import time,random
N = 1000
# ls = [random.randint(1,N) for _ in range(N)]
ls = [i for i in range(N)]

def log_time(ls):
    def wrapper(func):
        start = time.time()
        func(ls)
        end = time.time()
        print('{}排序函数运行了 {} s！'.format(func.__name__,end-start))
    return wrapper

@log_time(ls)
def bubble_sort(ls):
    length = len(ls)
    for i in range(length-1,0,-1):
        count = 0
        for j in range(i):
            if ls[j]>ls[j+1]:
                ls[j],ls[j+1]=ls[j],ls[j+1]
                count += 1
        if count == 0: return ls
    return ls

@log_time(ls)
def select_sort(ls):
    length = len(ls)
    for i in range(length):
        min_index = i
        for j in range(i+1,length):
            if ls[j]<ls[min_index]:
                min_index = j
        ls[i],ls[min_index]=ls[min_index],ls[i]
    return ls

@log_time(ls)
def insert_sort(ls):
    length = len(ls)
    for i in range(1,length):
        for j in range(i,-1,-1):
            if ls[j]>ls[j-1]:
                ls[j],ls[j-1]=ls[j-1],ls[j]
            else:
                break
    return ls

@log_time(ls)
def shell_sort(alist):
    n = len(alist)
    # 初始步长
    gap = n // 2
    while gap > 0:
        # 按步长进行插入排序
        for i in range(gap, n):
            j = i
            # 插入排序
            while j>=gap and alist[j-gap] > alist[j]:
                alist[j-gap], alist[j] = alist[j], alist[j-gap]
                j -= gap
        # 得到新的步长
        gap = gap // 2
    return alist

# @log_time(ls)
def quick_sort(ls):
    def q_sort(ls,left,right):
        if left >= right:
            return
        i,j = left,right
        pivot = ls[left]
        while i<j:
            while ls[j] > pivot and i<j:
                j -= 1
            ls[i] = ls[j]
            while ls[i] <= pivot and i<j:
                i += 1
            ls[j] = ls[i]
        ls[i] = pivot
        q_sort(ls,left,i-1)
        q_sort(ls,i+1,right)
        return ls
    return q_sort(ls,0,len(ls)-1)

@log_time(ls)
def merge_test(ls):
    def merge_sort(ls):
        if len(ls) <= 1:
            return ls
        mid = len(ls)//2
        # 序列左边部分
        left = merge_sort(ls[:mid])
        # 序列右边部分
        right = merge_sort(ls[mid:])
        return merge(left,right)

    def merge(left,right):
        ## left部分的指针 l right部分的指针 r
        l,r = 0,0
        res = []
        while l < len(left) and r < len(right):
            if left[l] < right[r]:
                res.append(left[l])
                l += 1
            else:
                res.append(right[r])
                r += 1
        res += left[l:]
        res += right[r:]
        return res
    return merge_sort(ls)