欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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)，以完成快速排序的過(guò)程。快速排序的最差時(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)
復(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)

相關(guān)文章

最新評(píng)論