排序算法是計算機科學中最基礎也是最重要的知識之一。快速排序（Quicksort）因其平均時間復雜度為?O(n log n)?而廣受歡迎，但在最壞情況下會退化到?O(n2)。為了克服這一缺點，自省排序（Introsort）?應運而生，它結合了快速排序、堆排序和插入排序的優點，成為C++標準庫（std::sort）的默認實現。

本文將詳細介紹：

1. 快速排序的原理與優化

2. 自省排序的設計思想

3. C語言實現自省排序

4. 性能分析與對比

---

1. 快速排序（Quicksort）回顧

快速排序由Tony Hoare于1959年提出，采用?分治法（Divide and Conquer）：

1. 選擇基準值（Pivot）：通常取第一個、最后一個或隨機元素。

2. 分區（Partition）：將數組分為兩部分，左邊 ≤ pivot，右邊 ≥ pivot。

3. 遞歸排序：對左右子數組重復上述過程。

C語言實現（經典快速排序）

c

void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}int partition(int arr[], int low, int high) {int pivot = arr[high]; // 選擇最后一個元素作為基準int i = low - 1;       // i 指向小于pivot的區域的末尾for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]); // 將pivot放到正確位置return i + 1;
}void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}

快速排序的缺點

• 最壞情況（如數組已有序或逆序）：遞歸深度?O(n)，時間復雜度?O(n2)。

• 對小數組效率低：遞歸調用開銷大。

---

2. 自省排序（Introsort）

自省排序由David Musser于1997年提出，結合了：

1. 快速排序（主算法，高效分區）

2. 堆排序（防止最壞情況）

3. 插入排序（優化小數組）

核心思想

1. 遞歸深度限制：

   • 如果遞歸深度超過?2 log?n，切換到堆排序（保證最壞情況?O(n log n)）。

2. 小數組優化：

   • 當子數組大小 ≤?16（經驗值），改用插入排序（減少遞歸開銷）。

3. 三數取中法（Median-of-Three）：

   • 優化基準值選擇，減少最壞情況概率。

---

3. C語言實現自省排序

c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>// 交換兩個元素
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 插入排序（用于小數組優化）
void insertionSort(int arr[], int low, int high) {for (int i = low + 1; i <= high; i++) {int key = arr[i];int j = i - 1;while (j >= low && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}// 堆排序（用于防止快速排序退化）
void heapify(int arr[], int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest])largest = left;if (right < n && arr[right] > arr[largest])largest = right;if (largest != i) {swap(&arr[i], &arr[largest]);heapify(arr, n, largest);}
}void heapSort(int arr[], int low, int high) {int n = high - low + 1;for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);for (int i = n - 1; i > 0; i--) {swap(&arr[0], &arr[i]);heapify(arr, i, 0);}
}// 三數取中法選擇基準值
int medianOfThree(int arr[], int low, int high) {int mid = low + (high - low) / 2;if (arr[low] > arr[mid])swap(&arr[low], &arr[mid]);if (arr[low] > arr[high])swap(&arr[low], &arr[high]);if (arr[mid] > arr[high])swap(&arr[mid], &arr[high]);return mid; // 返回中間值的索引
}// 自省排序核心
void introSortUtil(int arr[], int low, int high, int depthLimit) {int size = high - low + 1;// 小數組優化：改用插入排序if (size <= 16) {insertionSort(arr, low, high);return;}// 遞歸深度超限：改用堆排序if (depthLimit == 0) {heapSort(arr, low, high);return;}// 三數取中法選擇基準值int pivotIdx = medianOfThree(arr, low, high);swap(&arr[pivotIdx], &arr[high]);// 快速排序分區int pi = partition(arr, low, high);// 遞歸排序左右子數組introSortUtil(arr, low, pi - 1, depthLimit - 1);introSortUtil(arr, pi + 1, high, depthLimit - 1);
}// 自省排序入口
void introSort(int arr[], int n) {int depthLimit = 2 * log2(n); // 計算最大遞歸深度introSortUtil(arr, 0, n - 1, depthLimit);
}

---

4. 性能對比

算法	最佳	平均	最壞	適用場景
快速排序	O(n log n)	O(n log n)	O(n2)	通用排序
堆排序	O(n log n)	O(n log n)	O(n log n)	最壞情況保證
插入排序	O(n)	O(n2)	O(n2)	小數組優化
自省排序	O(n log n)	O(n log n)	O(n log n)	綜合最優

---

5. 總結

• 自省排序 = 快速排序 + 堆排序 + 插入排序，綜合了三種算法的優勢。

• 防止快速排序退化：遞歸深度超限時切換堆排序。

• 優化小數組：改用插入排序減少遞歸開銷。

• C++ STL的std::sort就是基于自省排序，適用于絕大多數場景。

適用場景：

• 大規模數據排序（如數據庫、科學計算）。

• 需要穩定高效排序（避免最壞情況）。