python 算法 排序實現快速排序
更新時間：2012年06月05日 22:44:40 作者：
主要分為兩個子算法，PARTITION(A, p, r)以A[r]為基準對數組進行一個劃分，比A[r]小的放在左邊，比A[r]大的放在右邊
QUICKSORT(A, p, r)是快速排序的子程序，調用劃分程序對數組進行劃分，然后遞歸地調用QUICKSORT(A, p, r)，以完成快速排序的過程?？焖倥判虻淖畈顣r間復雜度為O(n2)，平時時間復雜度為O(nlgn)。最差時間復雜度的情況為數組基本有序的時候，平均時間復雜度為數組的數值分布較為平均的時候。在平時情況下快速排序跟堆排序的時間復雜度都為O(nlgn)，但是快速排序的常數項較小，所以要優(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)
實現：
#!/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)
復制代碼 代碼如下:
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)
實現：
復制代碼 代碼如下:
#!/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)
相關文章
利用Python3實現統(tǒng)計大量單詞中各字母出現的次數和頻率的方法
這篇文章主要介紹了利用Python3實現統(tǒng)計大量單詞中各字母出現的次數和頻率，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-03-03
Python的Fire庫,一個用來生成命令行工具的的庫,這篇文章主要針對命令行參數,補充兩種更加靈活的設置方式,感興趣的小伙伴可以跟隨小編一起學習一下2024-01-01
在selenium中有很多種可以實現網站的免登錄，option就是其中的一種做法，這篇文章主要介紹了Selenium中免登錄的實現方法option,需要的朋友可以參考下2022-12-12
這篇文章主要為大家詳細介紹了Python PyTorch如何實現簡單的Timer計時器,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2023-08-08
在本篇文章里小編給大家分享了關于java和Python哪個適合大數據分析的相關知識點文章，有需要的朋友們可以學習下。
2020-07-07 
這篇文章主要介紹了Python實現UDP程序通信過程圖解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-05-05 
python排序函數sort()與sorted()的區(qū)別
這篇文章主要介紹了python排序函數sort()與sorted()的區(qū)別,需要的朋友可以參考下
2018-09-09 
這篇文章主要為大家介紹了Python靜態(tài)Web服務器多任務版實現示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2022-06-06 
python issubclass 和 isinstance函數
這篇文章主要介紹了python issubclass 和 isinstance函數，本文通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值 ,需要的朋友可以參考下
2019-07-07