Sorting Algorithm 排序演算法介紹
前言 在本部落格的文章: Python 排序演算法範例 ( Sorting Algorithms in Python ) 有介紹一些常見的四種排序演算法:插入排序、選擇排序、合併排序、氣泡排序。除了這四種之外還有其他的嗎? 當然有!!! 1. 什麼是排序演算法?(排序在做什麼) 排序(Sorting)是指將一組資料(元素)依照 特定的規則 重新排列組合。 日常生活中: 例如將考卷依分數「由低到高」排列,或是將包裹依體積「由大到小」放置。 電腦科學中: 排序是資訊處理的核心基礎。主要是將資料依照「數值大小」(如整數、浮點數)或「字典順序」(如英文字母 A~Z、中文編碼)進行排列。 2. 為什麼會有這麼多種排序演算法? 既然目的都是為了「排好資料」,為什麼科學家要發明幾十種不同的方法?主要原因在於「沒有任何一種演算法在所有情境下都是完美的」。選擇演算法時通常會考量以下關鍵因素: 資料量的大小: 有些演算法(如氣泡排序、選擇排序)程式碼非常簡單,在資料量極小(例如 10 筆資料)時效率很高;但當資料量極大(例如 100 萬筆資料)時,計算時間會暴增,這時就必須使用高效能的演算法(如快速排序、合併排序)。 時間複雜度(計算量): 評估演算法執行速度的指標。例如: 平方時間複雜度 $O(n^2)$ :資料量增加 10 倍,執行時間可能增加 100 倍(如氣泡、選擇、插入排序)。 線性對數時間複雜度 $O(n \log n)$ :效能較佳,適合處理大數據(如快速、合併、堆積排序)。 資料的實際分佈狀況: 資料是已經「幾乎排好」還是「完全混亂」? 例如: 插入排序法 在面對「幾乎已經排好」的資料時,速度非常快。 空間複雜度(記憶體佔用): 有些演算法在排序過程中需要額外的記憶體空間來暫存資料(如合併排序),在記憶體受限的嵌入式系統中就需要謹慎使用。 穩定性(Stability): 如果資料中有兩個數值相同的元素,排序後它們的相對前後順序是否會改變?這在某些商用資料處理中非常重要。 3. 常見的排序演算法分類 根據文中提及的演算法,我們可以依據其運作原理(比較式 vs 非比較式)來分類: 核心分類:比較式排序 (Comparison-based) 這類演算法是透過「兩兩比較資料的大小」來決定順序,也是最常見的類型。 基礎四種(文中提及 Python ...