Python最强排序算法大比拼（python排行）

说起排序算法，可以分为这几类:

时间复杂度高:冒泡排序、选择排序、插入排序

复杂度为O(n2)

时间复杂度低:快速排序、堆排序、归并排序、希尔排序等等

复杂度都差不多为O(nlogn)

别小看了n2和nlogn的差距！如果一个长度为8的列表，O(n2)排序算法的运算就是82=64次，可O(nlogn)的算法却只需8×log8=8×3=24次，几乎差了三倍

而如果是一个长度为2^32(a^b代表a的b次方)的列表,如果复杂度为O(n2),需要计算2^32^2次,等于18446744073709551616次!但是复杂度如果为O(nlogn),却只需2^32×log2^32=2^32×32=137438953472次。

几乎相差了4294967296倍!

所以时间复杂度哪怕相差一点，在大数据面前也会变得相差很大。

而今天给大家介绍的计数排序、桶排序、基数排序，则是王者中的王者。

他们的时间复杂度仅为O(n)！

要知道，时间复杂度是这么排的:

O(1)<O(logn)<O(n)(计数排序、桶排序、基数排序)<O(nlogn)(快速排序、堆排序、归并排序、希尔排序)<O(n2)(冒泡排序、选择排序、插入排序)<O(n2logn)<O(n3)

真不愧是道高一尺魔高一丈呀!

但是，再厉害，也没有sorted()函数厉害……但可以说，已经非常接近了:(前方高能)

排序1000000个数的混乱列表

sorted():

1000000个数的混乱列表，0.3秒就排好了

但是，今天的计数排序、桶排序、基数排序也不甘示弱:

计数排序:

桶排序:

基数排序:

(由于基数排序的时间复杂度为O(nk),所以会慢一些，桶排序则是基数排序的优化)

很遗憾，终究还是没能打败sorted()函数,大家知道sorted()函数的时间复杂度和代码吗?欢迎大家评论!

源代码：（cal_time那个函数我也发了一篇文章，大家可以去看看)(sort我用视频讲解过，大家赶紧去学一学吧!)

计数排序:

import random
from cal_time import *
import sort

@cal_time
def count_sort(lst):

    max_count=max(lst)
    count=[0 for i in range(max_count+1)]
    for val in lst:
        count[val]+=1
        #sort.draw_bars(lst,val,-1,len(lst))
    lst.clear()
    for ind,val in enumerate(count):
        for j in range(val):
            lst.append(ind)
    #sort.draw_bars(lst,-1,-1,len(lst))

a=list(range(1,1000001))
random.shuffle(a)
#sort.t.bgcolor('black')
count_sort(a)
#sort.t.done()

桶排序:（利用了计数排序）

import random
import sort
from cal_time import *

def count_sort(lst):

    max_count=max(lst)
    count=[0 for i in range(max_count+1)]
    for val in lst:
        count[val]+=1
        #sort.draw_bars(lst,val,-1,len(lst))
    lst.clear()
    for ind,val in enumerate(count):
        for j in range(val):
            lst.append(ind)
    return lst

@cal_time
def buckets_sort(lst,max_num,n=100):
    buckets=[[] for i in range(n)]  #创建桶
    for var in lst:
        i=min(var//(max_num//n),n-1) #var放到i桶里
        buckets[i].append(var)

    lst.clear()
    for buc in buckets:
        sdbuc=sorted(buc)

        lst.extend(sdbuc)
    return lst

a=list(range(1,1000001))
random.shuffle(a)
#sort.t.bgcolor('black')
buckets_sort(a,max(a))
#sort.t.done()

基数排序:

import random
import sort
from cal_time import *

@cal_time
def radix_sort(lst):
    max_num=max(lst)
    it=0
    while 10**it<=max_num:
        buckets=[[] for i in range(10)]
        for var in lst:
            digit=(var//10**it)%10
            buckets[digit].append(var)
        lst.clear()
        for buc in buckets:
            lst.extend(buc)
        it+=1

a=list(range(1,1000001))
random.shuffle(a)
#sort.t.bgcolor('black')
radix_sort(a)
#sort.t.done()