成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

python 實現(xiàn)快速排序

Enlightenment / 2937人閱讀

摘要：排序算法之快速排序快速排序快排的思想首先任意選取一個數(shù)據(jù)通常選用數(shù)組的第一個數(shù)作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序。

Python排序算法之快速排序
快速排序（quickSort）
快排的思想：首先任意選取一個數(shù)據(jù)（通常選用數(shù)組的第一個數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序。

百度百科給的算法：

一趟快速排序的算法是：

1）設(shè)置兩個變量i、j，排序開始的時候：i=0，j=N-1；
2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；
3）從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A(chǔ)[j]，將A[j]和A[i]互換；
4）從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]互換；
5）重復(fù)第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環(huán)結(jié)束）。

時間復(fù)雜度：O(nlgn)

# QuickSort by Alvin


def QuickSort(myList, start, end):
    # 判斷l(xiāng)ow是否小于high,如果為false,直接返回
    if start < end:
        i, j = start, end
        # 設(shè)置基準(zhǔn)數(shù)
        base = myList[i]

        while i < j:
            # 如果列表后邊的數(shù),比基準(zhǔn)數(shù)大或相等,則前移一位直到有比基準(zhǔn)數(shù)小的數(shù)出現(xiàn)
            while (i < j) and (myList[j] >= base):
                j = j - 1

            # 同樣的方式比較前半?yún)^(qū)
            while (i < j) and (myList[i] <= base):
                i = i + 1

            myList[i], myList[j] = myList[j], myList[i]
        # 做完第一輪比較之后,列表被分成了兩個半?yún)^(qū),并且i=j,需要將這個數(shù)設(shè)置回base
        myList[i] = base

        # 遞歸前后半?yún)^(qū)
        QuickSort(myList, start, i - 1)
        QuickSort(myList, j + 1, end)
    return myList


myList = [49, 38, 65, 97, 76, 13, 27, 49]
print("Quick Sort: ")
QuickSort(myList, 0, len(myList)-1)
print(myList)

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/44983.html

相關(guān)文章

  • Github標(biāo)星2w+，熱榜第一，如何用Python實現(xiàn)所有算法

    摘要：歸并排序歸并排序，或，是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為大符號。以此類推，直到所有元素均排序完畢。與快速排序一樣都由托尼霍爾提出的，因而也被稱為霍爾選擇算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);編譯：周素云、蔣寶尚 學(xué)會了Python基礎(chǔ)知識，想進階一下，那就來點算法吧！畢竟編程語言只...

    zxhaaa 評論0 收藏0

  • python-八大算法

    摘要：排序算法總結(jié)排序算法平均時間復(fù)雜度冒泡排序選擇排序插入排序希爾排序快速排序歸并排序堆排序基數(shù)排序一冒泡排序基本思想兩個數(shù)比較大小，較大的數(shù)下沉，較小的數(shù)冒起來。 排序算法總結(jié) 排序算法 平均時間復(fù)雜度 冒泡排序O(n2) 選擇排序O(n2) 插入排序O(n2) 希爾排序O(n1.5) 快速排序O(N*logN) 歸并排序O(N*logN) 堆排序O(N*logN) 基數(shù)排序O(d(n+...

    aboutU 評論0 收藏0

  • 八大排序算法的Python實現(xiàn)

    摘要：是穩(wěn)定的排序方法。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。算法實現(xiàn)選擇排序堆排序描述堆排序是指利用堆積樹堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。 1、插入排序 描述 插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復(fù)雜度為O(n^2)。是穩(wěn)定...

    princekin 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法

    摘要：這是一個簡單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號的數(shù)值這個函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計算。 本章內(nèi)容銜接上一章　數(shù)據(jù)結(jié)構(gòu)與算法：二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu)： 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 　　- 如何將問題分成基線條件和遞歸條件 　　- 分而治之策略解決棘手問題 ...

    wuyumin 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法

    摘要：這是一個簡單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號的數(shù)值這個函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計算。 本章內(nèi)容銜接上一章　數(shù)據(jù)結(jié)構(gòu)與算法：二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu)： 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 　　- 如何將問題分成基線條件和遞歸條件 　　- 分而治之策略解決棘手問題 ...

    Carson 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<