Jimmy 的架站筆記

嗨~我是 Jimmy!我可能不是你認識的第 1 個 Jimmy,但一定是最帥的那個。


排序演算法筆記 0 - 排序演算法介紹與種類

By Jimmy 2022-04-14
發表於 演算法 資工
排序演算法筆記 0 - 排序演算法介紹與種類

1. 使用時機

Sorting algorithms (排序演算法) 可以說是最常用到的演算法之一,主要有兩個原因:

2. 分類

一般來說可以依照幾種方法來分類:

2.1 Stability (穩定性)

2.1.1 Stable Sorting

兩個 value 相同的元素,在排列前後的相對位置一樣,稱為 stable sorting (穩定排序法)

2.1.2 Unstable Sorting

兩個 value 相同的元素,在排列前後的相對位置改變,稱謂 unstable sorting (不穩定排序法)

stable sorting and unstable sorting

2.2 Internal and External Sorting

2.2.1 Internal Sorting (內部排序)

排序的過程中,將待排序的所有元素放置在主記憶體 (RAM)

2.2.2 External Sorting (外部排序)

需要排序的元素太多,無法全部置於主記憶體,整個排序過程需要在主記憶體與硬碟之中多次交換資料才能完成,external sorting 又可再分為 distribution sorting 和 external merge sort:

排序演算法

▲ External Merge Sort
圖片來源:External Sorting vs Internal Sorting

一般來說我們學習的排序演算法都是 internal sorting。

2.3 Complexity

可以按照演算法的複雜度分為以下兩種:

2.3.1 Simple Sorts

Simple sorts,顧名思義,很 simple,可能你我都可以自己想出來,不過相對來說時間複雜度較差,通常來說為 O(n2)

2.3.2 Efficient Sorts

Efficient sorts 較為複雜,但時間複雜度較 simple sorts 好,通常為 O(n log n)

3. 總結

雖然以上提到了這麼多演算法,但只會介紹比較常用的 7 種演算法,也就是 internal sorting 的那 7 種。你可能會想說學這麼多排序演算法有意義嗎?以 JavaSciprt 來說不就一個 Array.prototype.sort() (使用 quick sort implement) 就能解決所有事情了?然而,不同的排序演算法還是有它不同的應用場景。

舉例來說,今天有個社群軟體的首頁要展示前一天最熱門的 10 篇貼文,在資料庫極為龐大的情況下,就可以選擇使用 selection sort,因為它的原理是每次選擇最小的(或最大的)放在元素的最前面,如此一來就不用把所有元素排序完再取前 10,而是直接把前 10 熱門的文章排序完後,就不用再繼續排序了。

4. 參考資料

External Sorting vs Internal Sorting
External sorting - Wikipedia


你可能也會喜歡

演算法筆記 0 – 演算法定義與 Big O Notation

演算法筆記 0 – 演算法定義與 Big O Notation

1. 演算法定義 一般來說,符合以下這 5 種特性(Characteristics)就可以稱為演算法: 1.1 輸入(Input) An algorithm may have many inputs or no inputs at all. 演算法應該具有 0 個或多個輸入。 1.2 輸出(Output) An algorithm should result at least one outpu

Read More
資料結構筆記 4 - Binary Tree (二元樹)

資料結構筆記 4 - Binary Tree (二元樹)

1. Binary Tree 定義 Binary tree 是定義更狹窄的 tree,一棵 binary tree 的定義如下: - 每個 node 最多有兩個 subTree (也就是最多有兩個 child node) - Left subTree (左子樹) 和 right subTree (右子樹) 是有順序的,順序不能任意顛倒 - 即使某個 node 只有一個 subTree,也必須區分

Read More