python八大排序算法速度實例對比
這篇文章并不是介紹排序算法原理的,純粹是想比較一下各種排序算法在真實場景下的運行速度。
算法由 Python 實現(xiàn),可能會和其他語言有些區(qū)別,僅當(dāng)參考就好。
測試的數(shù)據(jù)是自動生成的,以數(shù)組形式保存到文件中,保證數(shù)據(jù)源的一致性。
排序算法
直接插入排序
時間復(fù)雜度:O(n²)
空間復(fù)雜度:O(1)
穩(wěn)定性:穩(wěn)定
def insert_sort(array): for i in range(len(array)): for j in range(i): if array[i] < array[j]: array.insert(j, array.pop(i)) break return array
希爾排序
時間復(fù)雜度:O(n)
空間復(fù)雜度:O(n√n)
穩(wěn)定性:不穩(wěn)定
def shell_sort(array): gap = len(array) while gap > 1: gap = gap // 2 for i in range(gap, len(array)): for j in range(i % gap, i, gap): if array[i] < array[j]: array[i], array[j] = array[j], array[i] return array
簡單選擇排序
時間復(fù)雜度:O(n²)
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
def select_sort(array): for i in range(len(array)): x = i # min index for j in range(i, len(array)): if array[j] < array[x]: x = j array[i], array[x] = array[x], array[i] return array
堆排序
時間復(fù)雜度:O(nlog₂n)
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
def heap_sort(array): def heap_adjust(parent): child = 2 * parent + 1 # left child while child < len(heap): if child + 1 < len(heap): if heap[child + 1] > heap[child]: child += 1 # right child if heap[parent] >= heap[child]: break heap[parent], heap[child] = \ heap[child], heap[parent] parent, child = child, 2 * child + 1 heap, array = array.copy(), [] for i in range(len(heap) // 2, -1, -1): heap_adjust(i) while len(heap) != 0: heap[0], heap[-1] = heap[-1], heap[0] array.insert(0, heap.pop()) heap_adjust(0) return array
冒泡排序
時間復(fù)雜度:O(n²)
空間復(fù)雜度:O(1)
穩(wěn)定性:穩(wěn)定
def bubble_sort(array): for i in range(len(array)): for j in range(i, len(array)): if array[i] > array[j]: array[i], array[j] = array[j], array[i] return array
快速排序
時間復(fù)雜度:O(nlog₂n)
空間復(fù)雜度:O(nlog₂n)
穩(wěn)定性:不穩(wěn)定
def quick_sort(array): def recursive(begin, end): if begin > end: return l, r = begin, end pivot = array[l] while l < r: while l < r and array[r] > pivot: r -= 1 while l < r and array[l] <= pivot: l += 1 array[l], array[r] = array[r], array[l] array[l], array[begin] = pivot, array[l] recursive(begin, l - 1) recursive(r + 1, end) recursive(0, len(array) - 1) return array
歸并排序
時間復(fù)雜度:O(nlog₂n)
空間復(fù)雜度:O(1)
穩(wěn)定性:穩(wěn)定
def merge_sort(array): def merge_arr(arr_l, arr_r): array = [] while len(arr_l) and len(arr_r): if arr_l[0] <= arr_r[0]: array.append(arr_l.pop(0)) elif arr_l[0] > arr_r[0]: array.append(arr_r.pop(0)) if len(arr_l) != 0: array += arr_l elif len(arr_r) != 0: array += arr_r return array def recursive(array): if len(array) == 1: return array mid = len(array) // 2 arr_l = recursive(array[:mid]) arr_r = recursive(array[mid:]) return merge_arr(arr_l, arr_r) return recursive(array)
基數(shù)排序
時間復(fù)雜度:O(d(r+n))
空間復(fù)雜度:O(rd+n)
穩(wěn)定性:穩(wěn)定
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
速度比較
from random import random from json import dumps, loads # 生成隨機數(shù)文件 def dump_random_array(file='numbers.json', size=10 ** 4): fo = open(file, 'w', 1024) numlst = list() for i in range(size): numlst.append(int(random() * 10 ** 10)) fo.write(dumps(numlst)) fo.close() # 加載隨機數(shù)列表 def load_random_array(file='numbers.json'): fo = open(file, 'r', 1024) try: numlst = fo.read() finally: fo.close() return loads(numlst)
from _datetime import datetime # 顯示函數(shù)執(zhí)行時間 def exectime(func): def inner(*args, **kwargs): begin = datetime.now() result = func(*args, **kwargs) end = datetime.now() inter = end - begin print('E-time:{0}.{1}'.format( inter.seconds, inter.microseconds )) return result return inner
如果數(shù)據(jù)量特別大,采用分治算法的快速排序和歸并排序,可能會出現(xiàn)遞歸層次超出限制的錯誤。
解決辦法:導(dǎo)入 sys 模塊(import sys),設(shè)置最大遞歸次數(shù)(sys.setrecursionlimit(10 ** 8))。
@exectime def bubble_sort(array): for i in range(len(array)): for j in range(i, len(array)): if array[i] > array[j]: array[i], array[j] = array[j], array[i] return array array = load_random_array() print(bubble_sort(array) == sorted(array))
↑ 示例:測試直接插入排序算法的運行時間,@exectime 為執(zhí)行時間裝飾器。
算法執(zhí)行時間
算法速度比較
總結(jié)
以上就是本文關(guān)于Python八大排序算法速度實例對比的全部內(nèi)容,希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站:
如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!
相關(guān)文章
學(xué)會Python數(shù)據(jù)可視化必須嘗試這7個庫
數(shù)據(jù)可視化是使用一些繪圖和圖形更詳細地理解數(shù)據(jù)的過程.最著名的庫之一是 matplotlib,它可以繪制幾乎所有您可以想象的繪圖類型.matplotlib 唯一的問題是初學(xué)者很難掌握.在本文中,我將介紹七個數(shù)據(jù)可視化庫,你可以嘗試使用它們來代替 matplotlib ,需要的朋友可以參考下2021-06-06Windows系統(tǒng)下cython_bbox庫的正確安裝步驟
Cython-bbox一般無法直接通過pip直接安裝,那么如何安裝呢?下面這篇文章主要給大家介紹了關(guān)于Windows系統(tǒng)下cython_bbox庫的正確安裝步驟,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2023-05-05Python隨機生成均勻分布在三角形內(nèi)或者任意多邊形內(nèi)的點
這篇文章主要為大家詳細介紹了Python隨機生成均勻分布在三角形內(nèi)或者任意多邊形內(nèi)的點,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-12-12python+mediapipe+opencv實現(xiàn)手部關(guān)鍵點檢測功能(手勢識別)
這篇文章主要介紹了python+mediapipe+opencv實現(xiàn)手部關(guān)鍵點檢測功能(手勢識別),本文僅僅簡單介紹了mediapipe的使用,而mediapipe提供了大量關(guān)于圖像識別等的方法,需要的朋友可以參考下2022-01-01