本系列文章通過 1000（一篇文章表示 1 個實體） 個實體 ，為讀者提供較為詳細的練習題目，以便讀者舉一反三，深度學習，本系列的文章涉及到 Python 知識點包括：Python 語言基礎、運算子和運算式、陳述句和程式結構、串列和元組、字典和集合、字串、正則運算式、函式、面向物件編程、模塊和包、例外處理和程式除錯、檔案和目錄操作、資料庫編程、界面編程、網路編程、WEB 編程、行程和執行緒、網路爬蟲、游戲編程等知識點，由易到難，由淺入深，一步步打下堅實的編程基礎，

本系列文章涉及的演算法包括搜索、回溯、遞回、排序、迭代、貪心、分治和動態規劃等，涉及的資料結構包括字串、串列、指標、區間、佇列、矩陣、堆疊、鏈表、哈希表、線段樹、二叉樹、二叉搜索樹和圖結構等，

本系列文章是筆者為適應當前教育改革的創新要求，更好地踐行語言類課程，滿足實踐教學與創新能力培養的需要，閱讀大量書籍、各大互聯網公司的面試演算法、LintCode、LeetCode、九章演算法和結合筆者近幾年專案經驗撰寫的系列文章，精選了 1000 個趣味性、實用性強的應用實體，從不同難度、不同演算法、不同型別和不同資料結構等方面，將實際演算法進行總結，希望為 Python 編程人員拋磚引玉，由于筆者經驗與水平有限，博文中疏漏及不妥之處在所難免，衷心地希望各位讀者在評論區多提寶貴意見及具體的修改建議，以便筆者進一步修改和完善，

一、快速排序法

快速排序法又稱為分割交換法，它是冒泡排序法的一種改進，它的基本思想是：先在資料中找一個虛擬的中間值，并按此中間值將所有打算排序的資料分為兩部分，其中，小于中間值的資料放在左邊，大于中間值的資料放在右邊，再用同樣的方式處理左、右兩邊的資料，直到排序完成，操作的步驟如下：

假設有n項資料，資料值 用K1，K2，…，Kn 來表示，

1. 先在資料中假設一個虛擬中間值K（為了方便，一般取第一個位置上的數），
2. 從左向右查找資料Ki，使得Ki>K，Ki的位置數記為i，
3. 從右向左查找資料Kj，使得Kj<K，Kj的位置數記為j，
4. 若i<j，那么資料Ki與Kj交換，并回到步驟（2）、（3），
5. 若i≥j，那么資料K與Kj交換，并以j為基準點分割成左右兩部分，然后針對左右兩部分再進行步驟1~步驟5，直到左半邊資料等于右半邊資料為止，

快速排序法最后的結果也有兩種形式，即遞增數列和遞減數列，接下來通過一組資料來演示快速排序法的排序原理，例如，有這樣一組資料：6，1，2，7，9，3，4，5，10，8，如下圖所示：

按照遞增進行排序，步驟如下：

步驟1：取原始值的第一個數6為虛擬中間值，即K=6；然后從左向右查找值大于6的數，即數值7，位置為i，即i=4；再從右向左查找值小于6的數，即數值5，位置是j，即j=8，如下圖所示：

步驟2：i<j，因此交換Ki（數值7）和Kj（數值5）的位置，完成第一次排序結果，然后再從左向右查找值大于6的數，即數值9，位置為i，即i=5；再從右向左查找值小于6的數，即數值4，位置為j，即j=7，如下圖所示：

步驟3：i<j，因此交換Ki（數值9）和Kj（數值4）的位置，完成第二次排序，然后再從左向右查找值大于6的數，即數值9，位置為i，即i=7；再從右向左查找值小于6的數，即數值3，位置是j，即j=6，如下圖所示：

步驟4：i>j，因此交換虛擬中間值K（數值6）和Kj（數值3）的位置，完成第三次排序，此時，發現6的左半邊都是小于6的數，右半邊都是大于6的數，虛擬中間值6變成了真正的中間值，如下圖所示：

步驟5：對中間值6的左半邊資料進行排序，中間值和右半邊資料暫時可以忽略，在左半邊取虛擬中間值K=3，從左向右查找大于3的值，即數值5，位置為i，即i=4；再從右向左查找小于3的值，即數值2，位置為j，即j=3，如下圖所示：

步驟6：i>j，因此需要交換K(數值3)和Kj(數值2)的值，如下圖所示，此時虛擬中間值變成了真正的中間值，小于3的都在中間值3的左半邊，大于3的都在中間值3的右半邊，

步驟7：接下來對中間值為3的左、右兩側排序，經過排序之后，最終排序結果如下圖所示：

步驟8：此時，整組資料的左半邊已經完成排序，接下來對右半邊進行排序，這次忽略已經排序好的左半邊和中間值6，取右半邊第一個位置的數為虛擬中間值K(數值9)，然后從左向右找大于9的值，即數值10，位置為i，即i=9；再從右向左找小于9的值，即數值8，位置為j，即j=10，如下圖所示：

步驟9：i<j，因此交換Ki(數值10)和Kj(數值8)的位置，然后再從左向右查找大于9的值，即數值10，位置為i，即i=10；再從右向左找小于9的值，即數值8，位置為j，即j=9，如下圖所示：

步驟10：i>j，因此交換Kj（數值8）和虛擬中間值（數值9）的值，此時，虛擬中間值變成為真正的中間值，如下圖所示：

步驟11：以中間值為9的左右兩側進行排序，最后完成右半邊排序，如下圖所示：

結合左半邊排序和右半邊排序，最終的結果如下圖所示：

至此，完成排序，

二、實體：使用快速排序法進行遞增排序

使用快速排序法為串列：6，1，2，7，9，3，4，5，10，8，進行遞增排序，具體代碼如下：

def quick(data, start, end):  # 定義快速排序法函式
    if start > end:  # 如果開始值大于結束值
        return  # 直接退出程式
    i, j = start, end
    result = data[start]  # 取虛擬中間值
    while True:  # 回圈
        while j > i and data[j] >= result:  # 從右向左找，找到的數比虛擬中間值小就停止回圈
            j = j - 1  # 從右向左找，位置每次-1
        while i < j and data[i] <= result:  # 從左向右找，找到的數比虛擬中間值大就停止回圈
            i += 1  # 從左向右找，位置每次+1
        if i < j:  # i和j都停止，找到對應的位置，判斷i<j
            data[i], data[j] = data[j], data[i]  # 交換位置i和j對應的數值
        elif i >= j:  # 判斷i>=j
            # 交換虛擬中間值和j位置上的數，此時虛擬中間值變成真正中間值
            data[start], data[j] = data[j], data[start]
            break  # 完成第一次排序，此時以中間值分左右兩側
    quick(data, start, i - 1)  # 呼叫快速排序函式，再快速排序左半邊資料
    quick(data, i + 1, end)  # 呼叫快速排序函式，再快速排序右半邊資料


data = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]  # 定義串列并初始化
print("原始資料為：")
print(data)  # 輸出原始資料
print("--------------------------------")
quick(data, 0, (len(data) - 1))  # 呼叫快速排序，資料從位置0開始，到資料長度-1為止
print("排序之后的資料為：")
print(data)  # 輸出排序后資料
print("--------------------------------")

程式運行結果如圖所示：

三、練習：入職年限排名

例如，某公司的6名職員入職年限分別是：1，3，15，20，5，4，利用快速排序法給這些職員入職年限按照從高到低順序排序，具體代碼如下：

def quick(data, start, end):  # 定義快速排序法函式
    if start > end:  # 如果開始值大于結束值
        return  # 直接退出程式
    i, j = start, end
    result = data[start]  # 取虛擬中間值
    while True:  # 回圈
        while j > i and data[j] <= result:  # 從右向左找，找到的數虛擬中間值大就停止回圈
            j = j - 1  # 從右向左找，位置每次-1
        while i < j and data[i] >= result:  # 從左向右找，找到的數虛擬中間值小就停止回圈
            i += 1  # 從左向右找，位置每次+1
        if i < j:  # i和j都停止，找到對應的位置，判斷i<j
            data[i], data[j] = data[j], data[i]  # 交換位置i和j對應的數值
        elif i >= j:  # 判斷i>=j
            # 交換虛擬中間值和j位置上的數，此時虛擬中間值變成真正中間值
            data[start], data[j] = data[j], data[start]
            break  # 完成第一次排序，此時以中間值分左右兩側
    quick(data, start, i - 1)  # 呼叫快速排序函式，再快速排序左半邊資料
    quick(data, i + 1, end)  # 呼叫快速排序函式，再快速排序右半邊資料


data = [1, 3, 15, 20, 5, 4]  # 定義串列并初始化
print("六名職員入職年限如下：")
print(data)  # 輸出原始資料
print("→→→→→→→→→→→→→→→→→→→→→")
quick(data, 0, (len(data) - 1))  # 呼叫快速排序，資料從位置0開始，到資料長度-1為止
print("從高到低排序之后的入職年限如下：")
print(data)  # 輸出排序后資料
print("→→→→→→→→→→→→→→→→→→→→→")

程式運行結果如圖所示：

感謝您閱讀本篇博文，希望本文能成為您編程路上的領航者，祝您閱讀愉快！

好書不厭讀百回，熟讀課思子自知，而我想要成為全場最靚的仔，就必須堅持通過學習來獲取更多知識，用知識改變命運，用博客見證成長，用行動證明我在努力，
如果我的博客對你有幫助、如果你喜歡我的博客內容，請 點贊、評論、收藏 一鍵三連哦！聽說點贊的人運氣不會太差，每一天都會元氣滿滿呦！如果實在要白嫖的話，那祝你開心每一天，歡迎常來我博客看看，
?編碼不易，大家的支持就是我堅持下去的動力，點贊后不要忘了 關注 我哦！