python 算法 排序?qū)崿F(xiàn)快速排序
更新時(shí)間：2012年06月05日 22:44:40 作者：
主要分為兩個(gè)子算法，PARTITION(A, p, r)以A[r]為基準(zhǔn)對(duì)數(shù)組進(jìn)行一個(gè)劃分，比A[r]小的放在左邊，比A[r]大的放在右邊
QUICKSORT(A, p, r)是快速排序的子程序，調(diào)用劃分程序?qū)?shù)組進(jìn)行劃分，然后遞歸地調(diào)用QUICKSORT(A, p, r)，以完成快速排序的過程?？焖倥判虻淖畈顣r(shí)間復(fù)雜度為O(n2)，平時(shí)時(shí)間復(fù)雜度為O(nlgn)。最差時(shí)間復(fù)雜度的情況為數(shù)組基本有序的時(shí)候，平均時(shí)間復(fù)雜度為數(shù)組的數(shù)值分布較為平均的時(shí)候。在平時(shí)情況下快速排序跟堆排序的時(shí)間復(fù)雜度都為O(nlgn)，但是快速排序的常數(shù)項(xiàng)較小，所以要優(yōu)于堆排序。
PARTITION(A, p, r)
x ← A[r]
i ← p - 1
for j ← p to r - 1
do if A[j] ≤ x
then i ← i + 1
swap(A[i], A[j])
swap(A[i + 1], A[r])
return i + 1
QUICKSORT(A, p, r)
if p < r
then q ← PARTITION(A, p, r)
QUICKSORT(A, p, q - 1)
QUICKSORT(A, q + 1, r)
實(shí)現(xiàn)：
#!/usr/bin/python
import sys
def partion(array, p, r):
x = array[r]
i = p - 1
for j in range(p, r):
if (array[j] < x):
i+=1
array[j], array[i] = array[i], array[j]
i+=1
array[i], array[r] = array[r], array[i]
return i
def quick_sort(array, p, r):
if p < r:
q = partion(array, p, r)
quick_sort(array, p, q - 1)
quick_sort(array, q + 1, r)
if __name__ == "__main__":
array = [1, 3, 5, 23, 64, 7, 23, 6, 34, 98, 100, 9]
quick_sort(array, 0, len(array) - 1)
for a in array:
sys.stdout.write("%d " % a)
PARTITION(A, p, r)
復(fù)制代碼 代碼如下:
x ← A[r]
i ← p - 1
for j ← p to r - 1
do if A[j] ≤ x
then i ← i + 1
swap(A[i], A[j])
swap(A[i + 1], A[r])
return i + 1
QUICKSORT(A, p, r)
復(fù)制代碼 代碼如下:
if p < r
then q ← PARTITION(A, p, r)
QUICKSORT(A, p, q - 1)
QUICKSORT(A, q + 1, r)
實(shí)現(xiàn)：
復(fù)制代碼 代碼如下:
#!/usr/bin/python
import sys
def partion(array, p, r):
x = array[r]
i = p - 1
for j in range(p, r):
if (array[j] < x):
i+=1
array[j], array[i] = array[i], array[j]
i+=1
array[i], array[r] = array[r], array[i]
return i
def quick_sort(array, p, r):
if p < r:
q = partion(array, p, r)
quick_sort(array, p, q - 1)
quick_sort(array, q + 1, r)
if __name__ == "__main__":
array = [1, 3, 5, 23, 64, 7, 23, 6, 34, 98, 100, 9]
quick_sort(array, 0, len(array) - 1)
for a in array:
sys.stdout.write("%d " % a)
您可能感興趣的文章:
- python實(shí)現(xiàn)冒泡排序算法的兩種方法
- python冒泡排序算法的實(shí)現(xiàn)代碼
- python 實(shí)現(xiàn)插入排序算法
- python選擇排序算法的實(shí)現(xiàn)代碼
- Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之快速排序詳解
- python 實(shí)現(xiàn)歸并排序算法
- python實(shí)現(xiàn)的各種排序算法代碼
- Python實(shí)現(xiàn)的直接插入排序算法示例
- 基于python的七種經(jīng)典排序算法（推薦）
- 如何利用Python動(dòng)態(tài)展示排序算法
相關(guān)文章
利用Python3實(shí)現(xiàn)統(tǒng)計(jì)大量單詞中各字母出現(xiàn)的次數(shù)和頻率的方法
這篇文章主要介紹了利用Python3實(shí)現(xiàn)統(tǒng)計(jì)大量單詞中各字母出現(xiàn)的次數(shù)和頻率，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
Python?Fire中兩種命令行參數(shù)靈活設(shè)置方式詳解
Python的Fire庫,一個(gè)用來生成命令行工具的的庫,這篇文章主要針對(duì)命令行參數(shù),補(bǔ)充兩種更加靈活的設(shè)置方式,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-01-01
Selenium中免登錄的實(shí)現(xiàn)方法option詳解
在selenium中有很多種可以實(shí)現(xiàn)網(wǎng)站的免登錄，option就是其中的一種做法，這篇文章主要介紹了Selenium中免登錄的實(shí)現(xiàn)方法option,需要的朋友可以參考下2022-12-12
Python PyTorch實(shí)現(xiàn)Timer計(jì)時(shí)器
這篇文章主要為大家詳細(xì)介紹了Python PyTorch如何實(shí)現(xiàn)簡單的Timer計(jì)時(shí)器,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-08-08
在本篇文章里小編給大家分享了關(guān)于java和Python哪個(gè)適合大數(shù)據(jù)分析的相關(guān)知識(shí)點(diǎn)文章，有需要的朋友們可以學(xué)習(xí)下。
2020-07-07 
Python實(shí)現(xiàn)UDP程序通信過程圖解
這篇文章主要介紹了Python實(shí)現(xiàn)UDP程序通信過程圖解,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2020-05-05 
python排序函數(shù)sort()與sorted()的區(qū)別
這篇文章主要介紹了python排序函數(shù)sort()與sorted()的區(qū)別,需要的朋友可以參考下
2018-09-09 
Python多任務(wù)版靜態(tài)Web服務(wù)器實(shí)現(xiàn)示例
這篇文章主要為大家介紹了Python靜態(tài)Web服務(wù)器多任務(wù)版實(shí)現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
2022-06-06 
python issubclass 和 isinstance函數(shù)
這篇文章主要介紹了python issubclass 和 isinstance函數(shù)，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下
2019-07-07