HOME
ABOUT
CONTACT
Rain
November 6, 2026
1. Quick Sort 快速排序法
2. Merge Sort 合併排序法
3. Selection Sort 選擇排序法
4. Insertion Sort 插入排序法
5. Bubble Sort 氣泡排序法
6. Heap Sort 堆積排序法
7. 常見排序法比較
Quick Sort 是 Divide and Conquer（分治法）演算法。它選擇 Pivot，透過 partition 將元素分到 Pivot 兩側，再遞迴排序子陣列。Partition 完成時，Pivot 到達最終排序位置，但兩側子陣列本身尚不一定有序。
範例：初始陣列為 [6, 3, 8, 2, 7, 1, 5]，選最後一個元素 5 為 Pivot，以上述 Lomuto 實作 partition 後得到 [3, 2, 1, 5, 7, 8, 6]。此時左右兩側仍未排序；接著分別排序 [3, 2, 1] 和 [7, 8, 6]，最後得到 [1, 2, 3, 5, 6, 7, 8]。
以下為使用 Lomuto partition、以最後一個元素作 Pivot 的簡化實作：
#include <utility>
#include <vector>
int partition(std::vector<int>& arr, int low, int high) {
const int pivot = arr[high];
int boundary = low;
for (int current = low; current < high; ++current) {
if (arr[current] <= pivot) {
std::swap(arr[boundary], arr[current]);
++boundary;
}
}
std::swap(arr[boundary], arr[high]);
return boundary;
}
void quickSort(std::vector<int>& arr, int low, int high) {
if (low >= high) return;
const int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
呼叫範例：quickSort(arr, 0, static_cast<int>(arr.size()) - 1);。空陣列會以 high == -1 進入函式並立即返回。
如何降低最壞情況機率？可隨機選 Pivot 或使用 median-of-three 等策略；它們降低遭遇極端分區的機率，但不改變最壞時間複雜度仍為 O(N^2) 的事實。
Merge Sort 同樣採用 Divide and Conquer，但先遞迴切分，再於合併階段將有序子陣列合成較大的有序陣列。
範例：[6, 3, 8, 2] 先切成 [6, 3] 與 [8, 2]，再切成單一元素；合併為 [3, 6]、[2, 8]，最後合併成 [2, 3, 6, 8]。合併需使用暫存空間，避免覆寫尚未比較的元素。
以下範例在左右元素相等時先取左側元素，因此排序具穩定性：
#include <vector>
void merge(std::vector<int>& arr, std::vector<int>& temp,
int low, int mid, int high) {
int left = low;
int right = mid + 1;
int output = low;
while (left <= mid && right <= high) {
if (arr[left] <= arr[right]) {
temp[output++] = arr[left++];
} else {
temp[output++] = arr[right++];
}
}
while (left <= mid) temp[output++] = arr[left++];
while (right <= high) temp[output++] = arr[right++];
for (int index = low; index <= high; ++index) {
arr[index] = temp[index];
}
}
void mergeSort(std::vector<int>& arr, std::vector<int>& temp,
int low, int high) {
if (low >= high) return;
const int mid = low + (high - low) / 2;
mergeSort(arr, temp, low, mid);
mergeSort(arr, temp, mid + 1, high);
merge(arr, temp, low, mid, high);
}
呼叫範例：std::vector<int> temp(arr.size());，若陣列非空，再呼叫 mergeSort(arr, temp, 0, static_cast<int>(arr.size()) - 1);。
適合應用：外部排序可將大型資料分批讀入記憶體排序、寫出有序 runs，再以多路合併完成整體排序；這不是把整個 Merge Sort 的 O(N) 記憶體需求消除，而是將暫存資料放到外部儲存裝置。
每一輪從未排序區域找出最小元素，與該區域第一個元素交換。以 [6, 3, 8, 2, 7] 為例，依序放置最小值後為 [2, 3, 6, 8, 7]，再將最後兩個元素排成 [2, 3, 6, 7, 8]。
#include <utility>
#include <vector>
void selectionSort(std::vector<int>& arr) {
const int size = static_cast<int>(arr.size());
for (int start = 0; start < size - 1; ++start) {
int minIndex = start;
for (int current = start + 1; current < size; ++current) {
if (arr[current] < arr[minIndex]) {
minIndex = current;
}
}
if (minIndex != start) {
std::swap(arr[start], arr[minIndex]);
}
}
}
Insertion Sort 像整理手上的撲克牌：維持左側已排序區域，每次取出下一個元素，將較大的元素往右移，再把該元素插入正確位置。從 index 1 開始向左比較；若只在前方元素大於 key 時移動，演算法具有穩定性。
#include <vector>
void insertionSort(std::vector<int>& arr) {
for (std::size_t index = 1; index < arr.size(); ++index) {
const int key = arr[index];
std::size_t position = index;
while (position > 0 && arr[position - 1] > key) {
arr[position] = arr[position - 1];
--position;
}
arr[position] = key;
}
}
標準函式庫的 std::sort 常見實作採用 introsort，並可能在小型分區改用 Insertion Sort；實作細節由標準函式庫決定，不是 C++ 標準所規定的唯一策略。
Insertion Sort vs. Selection Sort：Insertion Sort 對已排序或近乎排序資料通常很有效，且穩定，但最壞需要大量移動；Selection Sort 比較次數固定為 O(N^2)，通常交換次數較少，但一般實作不穩定。兩者都適合小型資料集的特定情境。
反覆比較相鄰元素，若順序錯誤就交換。每一輪結束後，未排序區域中的最大元素會移到最右側。使用 swapped 標記可在某一輪完全沒有交換時提早結束。
#include <utility>
#include <vector>
void bubbleSort(std::vector<int>& arr) {
const std::size_t size = arr.size();
for (std::size_t end = size; end > 1; --end) {
bool swapped = false;
for (std::size_t index = 0; index + 1 < end; ++index) {
if (arr[index] > arr[index + 1]) {
std::swap(arr[index], arr[index + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}
Heap 是一種符合堆積性質的完全二元樹，可用陣列表示。Max Heap 中，每個父節點都大於或等於子節點；Min Heap 則相反。對 0-based index，節點 i 的父節點為 (i - 1) / 2，左子節點為 2i + 1，右子節點為 2i + 2。
若要由小到大排序，建立 Max Heap 後，每輪將根節點（最大值）與目前 heap 範圍的最後一個元素交換，縮小 heap 範圍，再對新的根節點執行 SiftDown，直到排序完成。
#include <utility>
#include <vector>
void siftDown(std::vector<int>& arr, int root, int heapSize) {
while (root < heapSize / 2) {
const int left = root * 2 + 1;
const int right = left + 1;
int largest = root;
if (arr[left] > arr[largest]) largest = left;
if (right < heapSize && arr[right] > arr[largest]) largest = right;
if (largest == root) return;
std::swap(arr[root], arr[largest]);
root = largest;
}
}
void heapSort(std::vector<int>& arr) {
const int size = static_cast<int>(arr.size());
for (int root = size / 2 - 1; root >= 0; --root) {
siftDown(arr, root, size);
}
for (int end = size - 1; end > 0; --end) {
std::swap(arr[0], arr[end]);
siftDown(arr, 0, end);
}
}
Last updated: