前言：開創者必然偉大并且多數是曠世之才，但很多時候，開創者中隻出現了極少數能把這些成果發揚光大的(商業化)。。。反倒是一些敏銳的準商人，才會使這些創造地枝繁葉茂，這是《矽谷之光》所傳達的神谕。
下面進入正題:
說道排序(内排序),按照原始資料的多少和散列特性來選擇合适的排序非常重要，資料量少(幾千)插排、交換排、選擇排都可以，要是資料達到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資料：
可以看出，在10w級水準，快排和歸并和基數排序都較快，不到2秒，可以接受
100w資料：
據結果可以看出，對于百萬級别的資料，shell排序和堆排序已經不能滿足使用者需求了，快排(通過優化移位過程還可以加快1秒)、基數排序和歸并排序稍微快點(不到20秒)但也不行，可能用其他語言(C/C++)會稍微快點，對于更大的資料就得采用外排序和其他技術(流水線)了。
歡迎轉載，大牛勿噴