Algo python 作者: Joy Liu

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

基本概念

插入排序（Insertion Sort）是一種簡單且直觀的排序演算法，其基本概念是將一個數列分為已排序和未排序兩部分，然後逐步將未排序部分的元素插入到已排序部分的適當位置，直到整個數列都已排序完成。其基本概念如下：

步驟：

  1. 假設數列的第一個元素被視為已排序部分，而其餘元素被視為未排序部分。
  2. 從未排序部分選擇第一個元素，將它視為“待插入元素”。
  3. 開始與已排序部分的元素進行比較，並找到待插入元素在已排序部分中的正確位置。這通常涉及到逐一比較，並將大於待插入元素的元素向右移動，以為待插入元素腾出位置。
  4. 插入待插入元素到已排序部分的正確位置。
  5. 重複步驟2至步驟4，直到未排序部分不再包含任何元素，整個數列即完成排序。

特點：

  • 插入排序是一種穩定排序（相等元素的相對位置不會改變），因為只有當比較的元素小於待插入元素時才進行插入操作。
  • 它的時間複雜度為O(n^2)，其中n是數列中的元素數量。在最壞情況下，即當數列是反向排序時，插入排序的效率最低。
  • 插入排序在處理小型數據集時可能效率較高，但對於大型數據集，更高效的排序演算法如快速排序和合併排序更適用。
  • 插入排序的主要優點是實現簡單，且不需要額外的記憶體空間，因此適用於一些特殊應用場景。

插入排序雖然不是最高效的排序方法，但它是一種重要的排序演算法，有助於理解排序的基本概念。在某些情況下，它仍然是一個有用的工具，特別是當處理小型數據集或需要在數列已經部分有序時進行排序時。

實際應用

以下是使用 Python 實際應用插入排序的範例。我們將對一個數列進行插入排序，以升冪排序數字。

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):         
    # 待插入元素

    key = arr[i]                  
    # 將元素插入到已排序部分的適當位置         
    j = i - 1         
    while j >= 0 and key < arr[j]:             
        arr[j + 1] = arr[j]             
        j -= 1         
    arr[j + 1] = key 

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

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

在這個範例中，我們定義了一個名為 insertion_sort 的函數，它接受一個數列 arr 並執行插入排序。在排序過程中，我們從第二個元素（索引1）開始遍歷未排序部分。將當前元素視為“待插入元素”（key），然後將它插入到已排序部分的適當位置。

我們使用一個 while 迴圈來逐步尋找待插入元素的正確位置，並將大於待插入元素的元素向右移動，以為待插入元素腾出位置。最終，將待插入元素插入到已排序部分的正確位置。

重複這個過程，直到整個數列都已經排序完成。

其他演算法快速通道：

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

雖然內容並沒有程式實作

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

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

前往博客來購買 — 中文版

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

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

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

之前這本書只有英文版

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

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

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

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

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

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

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

前往博客來購買 — 中文版
前往博客來購買 — 英文版

發佈留言

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