Algo python

【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. 遞迴地對 leftright 子數列進行快速排序,然後將排序後的 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個使用線上平台學習的好處|學生、工程師、各行各業皆適用 看完整介紹。

推薦入門書籍

精通 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,讓不懂程式的人也能利用圖形了解各種演算法的特質跟運作.

雖然內容並沒有程式實作

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

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


Python 自動化的樂趣:搞定重複瑣碎&單調無聊的工作(第二版)

Python 自動化的樂趣|搞定重複瑣碎& 單調無聊的工作(中文版) (Automate the Boring Stuff with Python:  Practical Programming for Total Beginners) | 天瓏網路書店

如果想使用自動化來增強工作流程效率,大推本書

之前這本書只有英文版

在博客來等了1個月還是沒等到

沒想到在2020/08/28 出了中文版

二話不說馬上看看人家都是怎麼用python來完成例行公事的

除了運用Python寫出程式,在幾分鐘內搞定人工手動處理需要花費數小時的工作。

探索Python豐富的模組程式庫來完成某些特定工作

例如從網站上抓取資料、讀取PDF和Word文件,以及自動化執行滑鼠點按和鍵盤輸入的工作。

 ‧在一個或多個檔案中搜尋文字
  ‧建立、更新、搬移和重新命名檔案和資料夾
  ‧搜尋網頁和下載網路上的圖文內容
  ‧處理PDF檔的分割與合併,加入浮水印和加上密碼等作業
  ‧傳送Email和簡訊
  ‧填寫線上表單

發佈留言

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