python 實現快速排序

Enlightenment 發布于2019-07-31 11:18 / 2922人閱讀

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

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

百度百科給的算法：

一趟快速排序的算法是：

1）設置兩個變量i、j，排序開始的時候：i=0，j=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；
3）從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A[j]，將A[j]和A[i]互換；
4）從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]互換；
5）重復第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-完成的時候，此時令循環結束）。

時間復雜度：O(nlgn)

# QuickSort by Alvin


def QuickSort(myList, start, end):
    # 判斷low是否小于high,如果為false,直接返回
    if start < end:
        i, j = start, end
        # 設置基準數
        base = myList[i]

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

            # 同樣的方式比較前半區
            while (i < j) and (myList[i] <= base):
                i = i + 1

            myList[i], myList[j] = myList[j], myList[i]
        # 做完第一輪比較之后,列表被分成了兩個半區,并且i=j,需要將這個數設置回base
        myList[i] = base

        # 遞歸前后半區
        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)

云服務器 GPU云服務器 python快速排序快速排序快速排序函數快速排序算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/44983.html

Github標星2w+，熱榜第一，如何用Python實現所有算法

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

zxhaaa 2019-07-31 10:23 評論0 收藏0
python-八大算法

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

aboutU 2019-07-30 16:20 評論0 收藏0
八大排序算法的Python實現

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

princekin 2019-07-24 18:09 評論0 收藏0
數據結構與算法:常見排序算法

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

wuyumin 2019-07-30 15:33 評論0 收藏0
數據結構與算法:常見排序算法

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

Carson 2019-08-26 11:32 評論0 收藏0