python 算法 排序?qū)崿F(xiàn)快速排序 -電腦資料

    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的用法分享