python快速排序的實現(xiàn)及運(yùn)行時間比較
快速排序的基本思想：首先選定一個數(shù)組中的一個初始值，將數(shù)組中比該值小的放在左邊，比該值大的放在右邊，然后分別對左邊的數(shù)組進(jìn)行如上的操作，對右邊的數(shù)組進(jìn)行如上的操作。（分治+遞歸）
1.利用匿名函數(shù)lambda
匿名函數(shù)的基本用法func_name = lambda x:array，冒號左邊的x代表傳入的參數(shù)，冒號右邊的array代表返回值，當(dāng)然名字是可以自己取的。
quick_sort = lambda array: \
array if len(array) <= 1 \
else quick_sort([item for item in array[1:] if item <= array[0]]) \
+ [array[0]] + \
quick_sort([item for item in array[1:] if item > array[0]])
2.將匿名函數(shù)拆解封裝為函數(shù)
def func2(array):
if len(array)<=1:
return array
tmp = array[0]
left = [x for x in array[1:] if x<=tmp]
right = [x for x in array[1:] if x>tmp]
return func2(left) + [tmp] + func2(right)
3.網(wǎng)上常見的
def func2(array,left,right):
if left>=right:
return
low=left
high=right
tmp=array[low]
while left<right:
while left<right and array[right]>tmp:
right-=1
array[left] = array[right]
while left<right and array[left]<=tmp:
left+=1
array[right]=array[left]
array[right]=tmp
func2(array,low,left-1)
func2(array,left+1,high)
4.算法導(dǎo)論里面的
def func3(array, l, r):
if l < r:
q = partition(array, l, r)
func3(array, l, q - 1)
func3(array, q + 1, r)
def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[r] = array[r], array[i + 1]
return i + 1
5.利用棧實現(xiàn)非遞歸版本
def func4(array, l, r):
if l >= r:
return
stack = []
stack.append(l)
stack.append(r)
while stack:
low = stack.pop(0)
high = stack.pop(0)
if high - low <= 0:
continue
x = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[high] = array[high], array[i + 1]
stack.extend([low, i, i + 2, high])
6.python內(nèi)置的
sorted(array)
本來是想利用裝飾器來測一下每個函數(shù)的運(yùn)行時間的，但是由于快排里面存在遞歸，使用裝飾器會報錯，就只好一個個計算了。這里還是貼一下用裝飾器計算時間的代碼：
def count_time(func):
@wraps(func)
def helper(func,*args,**kwargs):
start=time()
result = func(*args,**kwargs)
end=time()
print("函數(shù)：", func.__name__, "運(yùn)行時間：", round(end - start, 4), "s")
return result
return helper
這里我們的輸入是隨機(jī)生成的在0-100間的整數(shù)，我們測試一下在不同數(shù)量下的消耗時間：
from functools import wraps
from random import randint
from time import time
func1_start =time()
res = quick_sort(array)
func1_end =time()
print("函數(shù)：func1 運(yùn)行時間：", round(func1_end - func1_start, 4), "s")
func2_start =time()
func2(array)
func2_end =time()
print("函數(shù)：func2 運(yùn)行時間：", round(func2_end - func2_start, 4), "s")
func3_start =time()
func3(array,0,len(array)-1)
func3_end =time()
print("函數(shù)：func3 運(yùn)行時間：", round(func3_end - func3_start, 4), "s")
func4_start =time()
func4(array,0,len(array)-1)
func4_end =time()
print("函數(shù)：func4 運(yùn)行時間：", round(func4_end - func4_start, 4), "s")
func5_start =time()
func5(array,0,len(array)-1)
func5_end =time()
print("函數(shù)：func5 運(yùn)行時間：", round(func5_end - func5_start, 4), "s")
func6_start =time()
sorted(array)
func6_end =time()
print("函數(shù)：func6 運(yùn)行時間：", round(func6_end - func6_start, 4), "s")
輸入array的定義：
array = [randint(0,100) for i in range(5000)]
需要注意的是，隨著數(shù)據(jù)量的增加，方法4，也就是算法導(dǎo)論中的會出現(xiàn)以下問題：
這是因為python中的遞歸深度是有一定限制的，可以使用如下方法暫時解決該問題：
import sys sys.setrecursionlimit(100000)
同時，方法4還會出現(xiàn)內(nèi)存溢出問題，方法4也太坑了。
最后對比一下這些方法消耗的時間：
總結(jié)：
方法一、方法二速度較快，同時也較好理解，想要學(xué)會快速排序，只要記住方法二即可；
python內(nèi)置的排序速度還是最快的呀；
以上所述是小編給大家介紹的python快速排序的實現(xiàn)及運(yùn)行時間比較，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！
如果你覺得本文對你有幫助，歡迎轉(zhuǎn)載，煩請注明出處，謝謝！
相關(guān)文章
Python數(shù)據(jù)結(jié)構(gòu)之Array用法實例
這篇文章主要介紹了Python數(shù)據(jù)結(jié)構(gòu)之Array用法實例,較為詳細(xì)的講述了Array的常見用法,具有很好的參考借鑒價值,需要的朋友可以參考下2014-10-10
關(guān)于Pycharm配置翻譯插件Translation報錯更新TTK失敗不能使用的問題
這篇文章主要介紹了關(guān)于Pycharm配置翻譯插件Translation報錯更新TTK失敗不能使用的問題,本文通過圖文并茂的形式給大家分享解決方案，需要的朋友可以參考下2022-04-04
python中for語句簡單遍歷數(shù)據(jù)的方法
這篇文章主要介紹了python中for語句簡單遍歷數(shù)據(jù)的方法,以一個簡單實例形式分析了Python中for語句遍歷數(shù)據(jù)的技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-05-05
Python實現(xiàn)壓縮和解壓縮ZIP文件的方法分析
這篇文章主要介紹了Python實現(xiàn)壓縮和解壓縮ZIP文件的方法,結(jié)合具體實例形式分析了Python操作zip文件壓縮與解壓縮的常用操作技巧,需要的朋友可以參考下2017-09-09
Python實現(xiàn)結(jié)構(gòu)體代碼實例
這篇文章主要介紹了Python實現(xiàn)結(jié)構(gòu)體代碼實例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-02-02
這篇文章主要給大家介紹了關(guān)于Python代碼縮進(jìn)和測試模塊的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-05-05
這篇文章主要介紹了Python掃描IP段查看指定端口是否開放的方法,涉及Python使用socket模塊實現(xiàn)端口掃描功能的相關(guān)技巧,需要的朋友可以參考下2015-06-06
部署django項目安裝uwsgi出錯的解決方法總結(jié)
uwsgi協(xié)議是一個uWSGI服務(wù)器自有的協(xié)議,它用于定義傳輸信息的類型(type of information),每一個uwsgi packet前4byte為傳輸信息類型描述,它與WSGI相比是兩樣?xùn)|西,下面這篇文章主要給大家介紹了關(guān)于部署django項目安裝uwsgi出錯的解決方法,需要的朋友可以參考下2022-08-08
這篇文章主要介紹了解決TensorFlow程序無限制占用GPU的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06
這篇文章主要介紹了Django實現(xiàn)圖片文字同時提交的方法,較為詳細(xì)的分析了Django+jQuery實現(xiàn)圖片與文字同時提交的相關(guān)技巧,需要的朋友可以參考下2015-05-05