天天看點

Python 3 對幾種常見的内排序算法的比較

前言:開創者必然偉大并且多數是曠世之才,但很多時候,開創者中隻出現了極少數能把這些成果發揚光大的(商業化)。。。反倒是一些敏銳的準商人,才會使這些創造地枝繁葉茂,這是《矽谷之光》所傳達的神谕。

下面進入正題:

說道排序(内排序),按照原始資料的多少和散列特性來選擇合适的排序非常重要,資料量少(幾千)插排、交換排、選擇排都可以,要是資料達到w級别呢?前面那些幾乎都會慢死,是以介紹下面的幾種排序:

#coding=utf-8,
import random,time,sys
'''Author:Frank.ZhangLongQi
   Date:2018-3-23
   e-mail:[email protected]
   Descrip:比較shell、快排、基數排序、堆排、歸并排序處理10w,100w級别資料時表現的   性能
'''
sys.setrecursionlimit(100000000)#設定遞歸深度
def radix_sort(array):
    bucket, digit = [[]], 0
    while len(bucket[0]) != len(array):
        bucket = [[], [], [], [], [], [], [], [], [], []]
        for i in range(len(array)):
            num = (array[i] // 10 ** digit) % 10
            bucket[num].append(array[i])
        array.clear()
        for i in range(len(bucket)):
            array += bucket[i]
        digit += 1
    return array

def quickSort(L, low, high):#快排是很實用的一種排序算法,結合了歸并和插排的優點,平均時間複雜度為nlgn,
    i = low                 #受主元是否劃分均衡的影響,當劃分較均衡時,性能突出,但當劃分極不均衡時
    j = high                #比如極限情況下的已經排序的資料或存在大量重複資料,此時快排的複雜度為n的平方,此時,插排的複雜度僅為n
    if i >= j:
        return L
    key = L[i]
    while i < j:
        while i < j and L[j] >= key:
            j = j-1                                                         
        L[i] = L[j]
        while i < j and L[i] <= key:    
            i = i+1 
        L[j] = L[i]
    L[i] = key 
    quickSort(L, low, i-1)
    quickSort(L, j+1, high)
    return L

def merge(nums, first, middle, last):  
    ''''' merge '''  
    lnums = nums[first:middle+1]   
    rnums = nums[middle+1:last+1]  
    lnums.append(sys.maxsize)  #sys.maxsize為一個64位的十進制數
    rnums.append(sys.maxsize)  
    l = 0  
    r = 0  
    for i in range(first, last+1):  
        if lnums[l] < rnums[r]:  
            nums[i] = lnums[l]  
            l+=1  
        else:  
            nums[i] = rnums[r]  
            r+=1  
def merge_sort(nums, first, last):  
    ''''' merge sort 
    merge_sort函數中傳遞的是下标,不是元素個數 
    '''  
    if first < last:  
        middle = (first + last)//2  #mid要取整
        merge_sort(nums, first, middle)  
        merge_sort(nums, middle+1, last)  
        merge(nums, first, middle,last)  
def shell(arr):
    n=len(arr)
    h=1
    while h<n/3:
        h=3*h+1
    while h>=1:
        for i in range(h,n):
            j=i
            while j>=h and arr[j]<arr[j-h]:
                arr[j], arr[j-h] = arr[j-h], arr[j]
                j-=h
        h=h//3
def heap_sort2(lst):
    for start in range((len(lst)-2)//2,-1,-1):
        sift_down(lst,start,len(lst)-1)
     
    for end in range(len(lst)-1,0,-1):
        lst[0],lst[end]=lst[end],lst[0]
        sift_down(lst,0,end-1)
    return lst
 
def sift_down(lst,start,end):
    root=start
    while True:
        child=2*root+1
        if child>end:
            break
        if child+1<=end and lst[child]<lst[child+1]:
            child+=1
        if lst[root]<lst[child]:
            lst[root],lst[child]=lst[child],lst[root]
            root=child
        else:
            break

if __name__=='__main__':
    N=1000000 #設定資料量
    nums = []
    for _ in range(N):#随機生成
        n=random.randint(1,10000000)
        nums.append(n)
    A=nums.copy() #確定每種算法的測試資料一緻
    B=nums.copy()
    C=nums.copy()
    D=nums.copy()

    start1=time.clock()
    shell(nums)         #希爾排序
    end1=time.clock()
    print('shell time is',end1-start1)

    start3=time.clock()
    merge_sort(A,0, len(A)-1) #歸并排序
    end3=time.clock()
    print('merge time is',end3-start3)

    start4=time.clock()
    B=quickSort(B,0,len(B)-1)   #快速排序
    end4=time.clock()
    print('quick time is',end4-start4)

    start2=time.clock()
    C=heap_sort2(C)         #堆排序
    end2=time.clock()
    print('heap time is',end2-start2)

    start5=time.clock()
    D=radix_sort(D)     #基數排序
    end5=time.clock()
    print('radix time is',end5-start5)

    if  nums==A and A==B and B==C and C=D :#互相驗證排序結果的正确性
        print('True')
    else:
        print('False')
           

Demon:

10w資料:

Python 3 對幾種常見的内排序算法的比較

可以看出,在10w級水準,快排和歸并和基數排序都較快,不到2秒,可以接受

100w資料:

Python 3 對幾種常見的内排序算法的比較

據結果可以看出,對于百萬級别的資料,shell排序和堆排序已經不能滿足使用者需求了,快排(通過優化移位過程還可以加快1秒)、基數排序和歸并排序稍微快點(不到20秒)但也不行,可能用其他語言(C/C++)會稍微快點,對于更大的資料就得采用外排序和其他技術(流水線)了。

歡迎轉載,大牛勿噴

繼續閱讀