python 算法 排序?qū)崿F(xiàn)快速排序
更新時間：2012年06月05日 22:44:40 作者：
主要分為兩個子算法，PARTITION(A, p, r)以A[r]為基準對數(shù)組進行一個劃分，比A[r]小的放在左邊，比A[r]大的放在右邊
QUICKSORT(A, p, r)是快速排序的子程序，調(diào)用劃分程序?qū)?shù)組進行劃分，然后遞歸地調(diào)用QUICKSORT(A, p, r)，以完成快速排序的過程?？焖倥判虻淖畈顣r間復(fù)雜度為O(n2)，平時時間復(fù)雜度為O(nlgn)。最差時間復(fù)雜度的情況為數(shù)組基本有序的時候，平均時間復(fù)雜度為數(shù)組的數(shù)值分布較為平均的時候。在平時情況下快速排序跟堆排序的時間復(fù)雜度都為O(nlgn)，但是快速排序的常數(shù)項較小，所以要優(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)
實現(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)
實現(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)
相關(guān)文章
python-opencv 將連續(xù)圖片寫成視頻格式的方法
今天小編就為大家分享一篇python-opencv 將連續(xù)圖片寫成視頻格式的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-01-01
這篇文章主要介紹了python 迭代器設(shè)計模式的相關(guān)資料，幫助大家更好的理解和使用python，感興趣的朋友可以了解下2021-01-01
這篇文章主要介紹了python獲取Pandas列名的幾種方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-08-08
Pycharm安裝并配置jupyter notebook的實現(xiàn)
這篇文章主要介紹了Pycharm安裝并配置jupyter notebook的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-05-05
使用pyecharts在jupyter notebook上繪圖
這篇文章主要介紹了使用pyecharts在jupyter notebook上繪圖，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2017-07-07![Python標準庫:內(nèi)置函數(shù)max(iterable, *[, key, default])說明](http://img.jbzj.com/images/xgimg/bcimg5.png)
Python標準庫:內(nèi)置函數(shù)max(iterable, *[, key, default])說明
這篇文章主要介紹了Python標準庫:內(nèi)置函數(shù)max(iterable, *[, key, default])說明，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-04-04
這篇文章主要為大家詳細介紹了Python機器學習中實現(xiàn)距離和相似性計算的方法，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學習一下2023-03-03
這篇文章主要為大家詳細介紹了python實現(xiàn)人民幣大寫轉(zhuǎn)換的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-06-06
Python爬蟲包 BeautifulSoup 遞歸抓取實例詳解
這篇文章主要介紹了Python爬蟲包 BeautifulSoup 遞歸抓取實例詳解的相關(guān)資料,需要的朋友可以參考下2017-01-01
下面小編就為大家分享一篇使用pandas讀取csv文件的指定列方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-04-04