本文提供八種常用排序算法的 C++ 泛型實現，涵蓋從基礎的 O(n²) 算法到高效的 O(n log n) 算法，以及非比較排序的基數排序。所有算法均以模板形式實現，支援任意可比較類型。
| 算法 | 平均時間 | 最壞時間 | 空間 | 穩定性 |
|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | 穩定 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 穩定 |
| 選擇排序 | O(n²) | O(n²) | O(1) | 不穩定 |
| 希爾排序 | O(n1.3) | O(n²) | O(1) | 不穩定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不穩定 |
| 歸並排序 | O(n log n) | O(n log n) | O(n) | 穩定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不穩定 |
| LSD 基數排序 | O(d(n+r)) | O(d(n+r)) | O(n+r) | 穩定 |
template <class T>
int _partition(T a[], int left, int right) {
T pivot = a[left];
while (left < right) {
while (left < right && a[right] >= pivot) --right;
a[left] = a[right];
while (left < right && a[left] <= pivot) ++left;
a[right] = a[left];
}
a[left] = pivot;
return left;
}
template <class T>
void _merge(T a[], int left, int mid, int right) {
int len = right - left + 1;
T* tmp = new T[len];
for (int i = 0, j = left; i < len; ++i, ++j) tmp[i] = a[j];
int i = 0, j = mid - left + 1, k = left;
while (i <= mid - left && j <= len - 1) {
a[k++] = (tmp[i] < tmp[j]) ? tmp[i++] : tmp[j++];
}
while (i <= mid - left) a[k++] = tmp[i++];
while (j <= len - 1) a[k++] = tmp[j++];
delete[] tmp;
}
template <class T>
void adjust_node(T a[], int n, int i) {
int largest = i;
int l = 2 * i + 1, r = 2 * i + 2;
if (l < n && a[l] > a[largest]) largest = l;
if (r < n && a[r] > a[largest]) largest = r;
if (largest != i) {
swap(a[i], a[largest]);
adjust_node(a, n, largest);
}
}
template <class T>
void lst_radix_sort(T a[], int n, int radix, int distance) {
T* tmp = new T[n];
int* cnt = new int[radix];
int div = 1;
for (int d = 0; d < distance; ++d, div *= radix) {
fill(cnt, cnt + radix, 0);
for (int i = 0; i < n; ++i) cnt[(a[i] / div) % radix]++;
for (int i = 1; i < radix; ++i) cnt[i] += cnt[i-1];
for (int i = n - 1; i >= 0; --i) {
int idx = (a[i] / div) % radix;
tmp[--cnt[idx]] = a[i];
}
copy(tmp, tmp + n, a);
}
delete[] tmp; delete[] cnt;
}
主程序對包含重複元素、大數值的測試數組 {45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128} 依次應用八種算法，均正確輸出有序序列。
