Algo python 作者: Joy Liu

【Python】Quick Sort 快速排序｜演算法介紹、新手快速入門

基本概念

快速排序（Quick Sort）是一種高效的、分治的、比較排序演算法，其基本概念如下：

步驟：

  1. 選擇一個基準元素（pivot）。通常，可以選擇數列中的第一個元素、最後一個元素、或隨機選擇一個元素作為基準元素。
  2. 分區（Partitioning）：將數列中的元素分為兩個子數列，一個子數列包含所有小於基準元素的元素，另一個子數列包含所有大於基準元素的元素。基準元素本身已經處於正確的位置。
  3. 遞迴：對每個子數列重複步驟1和步驟2，直到每個子數列只包含一個元素，此時整個數列已經排序完成。

特點：

  • 快速排序是一種不穩定的排序方法，因為在分區步驟中，相等元素的相對位置可能改變。
  • 它的平均時間複雜度為O(n log n)，其中n是數列中的元素數量。快速排序通常比其他O(n log n)時間複雜度的排序演算法效率更高。
  • 快速排序是一種原地排序（in-place sorting）方法，不需要額外的記憶體空間用於排序，因此在空間複雜度上非常優秀。
  • 選擇合適的基準元素是快速排序的關鍵。不同的基準選擇策略（例如，固定基準、隨機基準、中位數基準）會影響排序的效率。

快速排序是一種廣泛應用的排序演算法，特別適合處理大型數據集。其高效性和原地排序特性使得它成為許多編程語言和庫中的標準排序方法之一。

實際應用

以下是使用 Python 實際應用快速排序的範例。我們將對一個數列進行快速排序。

def quick_sort(arr):
    if len(arr) <= 1:
    return arr

    pivot = arr[0]  # 選擇第一個元素作為基準元素
    left = []     
    right = []     
    for element in arr[1:]:         
        if element < pivot:             
            left.append(element)         
        else:             
            right.append(element)     
    return quick_sort(left) + [pivot] + quick_sort(right) 

# 測試 
my_list = [64, 34, 25, 12, 22, 11, 90]

sorted_list = quick_sort(my_list) 

print("排序後的數列：") 
for num in sorted_list:     
    print(num, end=" ")

在這個範例中，我們定義了一個名為 quick_sort 的遞迴函數，它接受一個數列 arr 並執行快速排序。

主要的步驟包括：

  1. 如果數列長度小於等於1，則不需要進行排序，直接返回數列。
  2. 選擇基準元素 pivot，通常我們選擇數列的第一個元素。
  3. 將數列中比基準元素小的元素放入 left 子數列，將比基準元素大的元素放入 right 子數列。
  4. 遞迴地對 left 和 right 子數列進行快速排序，然後將排序後的 left 子數列、基準元素 pivot 和排序後的 right 子數列合併成一個排序完成的數列。
  5. 重複上述步驟，直到整個數列已經排序完成。

其他演算法快速通道：

  1. 【Python】什麼是演算法？
  2. 【Python】Stack(堆疊) 資料結構實作
  3. 【Python】linear search 線性搜尋
  4. 【Python】binary search 二分搜尋
  5. 【Python】Bubble Sort 泡沫排序
  6. 【Python】Selection Sort 選擇排序
  7. 【Python】Insertion Sort 選擇排序
  8. 【Python】Quick Sort 快速排序
  9. 【Python】Single Linked List(單向鏈結串列) 資料結構實作
  10. 【Python】Binary Search Tree (二元搜尋樹) 資料結構實作(1)
  11. 【Python】Binary Search Tree (二元搜尋樹) 資料結構實作(2)

線上學習平台推薦

udemy

我自己最愛用的學習平台是 udemy ，當初會選擇在 udemy 上學習的原因除了課程便宜（當初買的很多課程都300塊左右，是台幣喔台幣！）。

上課時間也可以自己控制（對自律的人來說是一大好處！）

雖然可能有些人會覺得，Youtube上不也很多Tutorials嗎？性質應該差不多吧？而且免費。

雖然看Youtube上也有教學影片，但其實你會發現，這些老師都有另外開課程。

原因也很簡單，只要我們付費購買了他的課程，他就能提供更多的資源來輔助學習，且更有組織的教學過程，甚至有被公司認可的證書。

這就是在免費的youtube上沒辦法做到的。

想知道更多的話，歡迎到【2023】10個使用線上平台學習的好處｜學生、工程師、各行各業皆適用 看完整介紹。

點擊加入Udemy

推薦入門書籍

精通 Python：運用簡單的套件進行現代運算（第二版）

博客來-精通Python：運用簡單的套件進行現代運算（第二版）

之前開始入坑python時就是用這本打底的（有換封面過）

這本書除了前幾張介紹基本的語法之外

後續幾張開始介紹與python相關的延伸性的功能

非常適合程式設計初學者以及剛要開始學習這個語言的讀者

羅列以下幾點關於本書大綱供大家參考

  • 學習簡單的資料類型、基本數學運算與文字操作 
  • 以Python的內建資料結構處理資料 
  • 探索Python程式碼結構，包括函式的使用
  • 使用模組與套件編寫大型Python程式
  • 深入討論物件、類別與其他物件導向功能
  • 檢視一般檔案、關聯式資料庫與NoSQL的儲存機制 
  • 使用Python建構web用戶端、伺服器、API與服務 
  • 管理系統工作，例如程式、程序與執行緒
  • 瞭解並行處理與網路程式設計的基礎
前往博客來購買 -- 中文版
前往博客來購買 -- 英文版

流暢的 Python：清晰、簡潔、有效的程式設計

博客來-流暢的Python：清晰、簡潔、有效的程式設計

適合已經有Python程式語言基礎的人

這本書更詳細的介紹有關python的用法

讓我們寫的程式可以更加"Pythonic"

建議可以與英文版同時閱讀

以後在查閱stackoverflow文獻的時候能不因語言而產生隔閡

  • Python 資料模型：瞭解特殊方法是讓物件具備一致行為的關鍵
  • 資料結構：充分使用內建的型態，並瞭解 Unicode 時代中，文字 vs. bytes 之間的關係
  • 函式就是物件：見識 Python 函式是一級物件，並瞭解這個事實如何影響熱門的設計模式
  • 物件導向的習慣用法：學習參考、可變性、介面、運算子多載與多重繼承，並建構類別
  • 控制流程：藉由 concurrent.futures 與 asyncio 套件，來充分活用情境管理器、產生器、協同程序與並行
  • 中繼編程：瞭解特性、屬性描述器、類別修飾器與中繼類別的工作原理
前往博客來購買 -- 中文版
前往博客來購買 -- 英文版

演算法圖鑑

直觀理解，從基礎開始學習，全圖像化step by step，讓不懂程式的人也能利用圖形了解各種演算法的特質跟運作．

雖然內容並沒有程式實作

但內容演算法流程圖片非常精美

非常適合用來教學或以圖像的方式了解演算法的運作！

前往博客來購買 — 中文版

跟著 Docker 隊長，修練 22 天就精通：搭配20小時作者線上教學，無縫接軌 Microservices、Cloud-native、Serverless、DevOps 開發架構

Docker視為必備技能，無論是什麼專案規模和使用技術，都一定會應用Docker作為開發工具。

這本書是由資深Docker Captain撰寫的，不僅有基礎Docker命令，更深入實務運用，像是如何整合熱門的Kubernetes、Jenkins、Prometheus等技術，打造CI/CD pipeline和監控系統。

作者大方分享多年的實戰經驗，教導如何優化image大小、提高安全性,實現應用程式自我修復、不停機更新等高階功能。

無論你是什麼背景，本書都適合你學習，內含大量範例檔和練習，只要22天，就能精通容器部署、管理與維運的實務經驗。

還有20小時的線上課程加強學習效果。由施威銘研究室監修、加註詳細說明,並提供GitHub範例檔同步更新，絕對是物超所值的學習寶典。

前往博客來購買 — 中文版

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *