# 演算法 in Golang：Quicksort（快速排序） ## Quicksort（快速排序） - 快速排序 O(nlog2^n)，比選擇排序要快 O(n²) - 在日常生活中經常使用 - 使用了 D & C 策略（分而治之） ## 使用 Quicksort 排序數組 - 不需要排序的數組（也就 ...
演算法 in Golang：Quicksort（快速排序）
Quicksort（快速排序）
- 快速排序 O(nlog2^n)，比選擇排序要快 O(n²)
- 在日常生活中經常使用
- 使用了 D & C 策略（分而治之）
使用 Quicksort 排序數組
- 不需要排序的數組（也就是 Base Case 基線條件）：
- []，空數組
- [s]，單元素數組
- 很容易排序的數組：
- [a, b]，兩個元素的數組，只需檢查它們之間的大小即可，調換位置
- 3 個元素的數組（例如 [23, 19, 35]）：
- 使用 D & C 策略，簡化至基線條件（Base case）
-
從數組中隨便選一個元素，例如 35，這個元素叫做 pivot（基準元素）
-
找到比 pivot 小的元素，找到比 pivot 大的元素，這叫做分區：[23, 19], (35), []
-
如果左右兩個子數組已排好序（達到基線條件），結果：左邊 + [pivot] + 右邊
-
如果左右兩個子數組沒排好序（沒達到基線條件），那麼：
quicksort(左邊) + [pivot] + quicksort(右邊)
使用 Quicksort 排序數組的步驟
- 選擇一個 pivot
- 將數組分為兩個子數組：
- 左側數組的元素都比 pivot 小
- 右側數組的元素都比 pivot 大
- 在兩個子數組上遞歸的調用 quicksort
創建項目
~/Code/go via
