QUICKSORT(A, p, r)是快速排序的子程序,調(diào)用劃分程序?qū)?shù)組進(jìn)行劃分,然后遞歸地調(diào)用QUICKSORT(A, p, r),以完成快速排序的過(guò)程,
python 算法 排序?qū)崿F(xiàn)快速排序
?焖倥判虻淖畈顣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)
復(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計(jì)數(shù)排序和基數(shù)排序算法實(shí)例
python實(shí)現(xiàn)排序算法
python算法學(xué)習(xí)之計(jì)數(shù)排序?qū)嵗?/p>
python算法學(xué)習(xí)之基數(shù)排序?qū)嵗?/p>
python算法學(xué)習(xí)之桶排序算法實(shí)例(分塊排序)
python冒泡排序算法的實(shí)現(xiàn)代碼
python選擇排序算法的實(shí)現(xiàn)代碼
python插入排序算法的實(shí)現(xiàn)代碼
python快速排序代碼實(shí)例
python實(shí)現(xiàn)的各種排序算法代碼
python 實(shí)現(xiàn)堆排序算法代碼
python 實(shí)現(xiàn)歸并排序算法
python 快速排序代碼
python3.0 字典key排序
Python學(xué)習(xí)筆記_數(shù)據(jù)排序方法
QQ空間 搜狐微博 人人網(wǎng) 開心網(wǎng) 百度搜藏更多
Tags:python 快速排序
復(fù)制鏈接收藏本文打印本文關(guān)閉本文返回首頁(yè)
上一篇:python操作MySQL數(shù)據(jù)庫(kù)的方法分享
下一篇:windows下wxPython開發(fā)環(huán)境安裝與配置方法
相關(guān)文章
2014-06-06Python實(shí)例分享:快速查找出被掛馬的文件
2014-06-06pycharm 使用心得(四)顯示行號(hào)
2014-06-06Python對(duì)兩個(gè)有序列表進(jìn)行合并和排序的例子
2006-09-09Python入門教程 超詳細(xì)1小時(shí)學(xué)會(huì)Python
2014-03-03python基礎(chǔ)教程之元組操作使用詳解
2014-04-04sqlalchemy對(duì)象轉(zhuǎn)dict的示例
2014-04-04Python和php通信亂碼問(wèn)題解決方法
2009-03-03wxpython 學(xué)習(xí)筆記 第一天
2014-02-02使用python在校內(nèi)發(fā)人人網(wǎng)狀態(tài)(人人網(wǎng)看狀態(tài))
2014-06-06解決windows下Sublime Text 2 運(yùn)行 PyQt 不顯示的方法分享
文章評(píng)論
最 近 更 新
python 實(shí)現(xiàn)堆排序算法代碼
linux系統(tǒng)使用python監(jiān)測(cè)系統(tǒng)負(fù)載腳本分享
python線程池的實(shí)現(xiàn)實(shí)例
win7安裝python生成隨機(jī)數(shù)代碼分享
Python Web框架Pylons中使用MongoDB的例子
Python設(shè)計(jì)模式之單例模式實(shí)例
Python 錯(cuò)誤和異常小結(jié)
python實(shí)現(xiàn)猜數(shù)字游戲(無(wú)重復(fù)數(shù)字)示例分
Python的print用法示例
python抓取京東商城手機(jī)列表url實(shí)例代碼
熱 點(diǎn) 排 行
Python入門教程 超詳細(xì)1小時(shí)學(xué)會(huì)
python 中文亂碼問(wèn)題深入分析
比較詳細(xì)Python正則表達(dá)式操作指
Python字符串的encode與decode研
Python open讀寫文件實(shí)現(xiàn)腳本
Python enumerate遍歷數(shù)組示例應(yīng)
Python 深入理解yield
Python+Django在windows下的開發(fā)
python 文件和路徑操作函數(shù)小結(jié)
python 字符串split的用法分享