C++十大排序详解（包括变种优化）

排序

**基础排序算法**
- 1. **冒泡排序（Bubble Sort）**
- 冒泡排序优化
- - **1. 提前终止优化（标志位优化）**
  - - **原理**：
    - **实现示例**（以C++为例）：
    - **优点**：
  - **2. 双向冒泡排序（鸡尾酒排序，Cocktail Shaker Sort）**
  - - **原理**：
    - **实现示例**（以C++为例）：
    - **优点**：
  - **3. 记录最后交换位置优化**
  - - **原理**：
    - **实现示例**（C++）：
    - **优点**：
  - **4. 间隔优化（跳跃式扫描）**
  - - **原理**：
    - **实现示例**（C++）：
    - **优点**：
  - **5. 并行化优化**
  - - **原理**：
    - **实现示例**（概念性C++伪代码）：
    - **优点**：
  - **总结与适用场景**
- 2. **选择排序（Selection Sort）**
- - 1. **避免无效交换的优化**
  - - 原理：
    - 实现示例（C++）：
    - 优点：
  - 2. **双向选择排序（双指针法）**
  - - 原理：
    - 实现示例（C++）：
    - 优点：
  - 3. **提前终止优化**
  - - 原理：
    - 实现示例（C++）：
    - 优点：
  - 4. **混合排序策略**
  - - 原理：
    - 优点：
  - 总结与适用场景
- 3. **插入排序（Insertion Sort）**
- - **1. 二分插入排序（Binary Insertion Sort）**
  - - **原理**：
    - **实现示例**（C++）：
    - **优点**：
  - **2. 希尔排序（Shell Sort）**
  - - **原理**：
    - **实现示例**（C++）：
    - **优点**：
  - **3. 减少元素移动的优化**
  - - **原理**：
    - **实现示例**（C++）：
    - **优点**：
  - **4. 递归实现（Recursive Insertion Sort）**
  - - **原理**：
    - **实现示例**（C++）：
    - **优点**：
  - **总结与适用场景**
- 4. **快速排序（Quick Sort）**
- - **基准选择优化**
  - **分区策略优化**
  - **小规模数组优化**
  - **递归与并行优化**
  - **其他优化**
  - **分区函数实现**
  - **总结与适用场景**
- 5. **归并排序（Merge Sort）**
- - **1. 小规模子数组优化**
  - - **原理**：
    - **实现示例**（C++）：
    - **优点**：
  - **2. 合并过程优化**
  - - **原理**：
    - **实现示例**（C++）：
    - **优点**：
  - **3. 空间优化：原地归并**
  - - **原理**：
    - **实现示例**（C++）：
    - **优点**：
  - **4. 非递归（自底向上）归并排序**
  - - **原理**：
    - **实现示例**（C++）：
    - **优点**：
  - **5. 外部排序（处理超大数据集）**
  - - **原理**：
    - **实现示例**（C++伪代码）：
    - **优点**：
  - **6. 不均衡分割变体（a-to-b Split）**
  - - **原理**：
    - **实现示例**（C++）：
    - **时间复杂度**：
    - **适用场景**：
  - **辅助函数实现**
  - **总结与适用场景**
- 6. **堆排序（Heap Sort）**
- - **1. 建堆优化：线性时间建堆**
  - - **原理**：
    - **实现要点**（C++）：
    - **优势**：
  - **2. Sift过程优化：减少比较次数**
  - - **原理**：
    - **实现要点**（C++）：
    - **优势**：
  - **3. 混合排序策略：小堆切换插入排序**
  - - **原理**：
    - **实现要点**（C++）：
    - **优势**：
  - **4. 缓存优化：提升数据局部性**
  - - **原理**：
    - **实现要点**（C++）：
    - **优势**：
  - **5. 并行化建堆与调整**
  - - **原理**：
    - **实现要点**（C++伪代码）：
    - **优势**：
  - **6. 非递归实现：减少函数调用开销**
  - - **原理**：
    - **实现要点**（C++）：
    - **优势**：
  - **辅助函数实现**
  - **总结与适用场景**
- 7. **计数排序（Counting Sort）**
- - **1. 支持负数的计数排序**
  - - **原理**：
    - **实现要点**：
    - **代码示例**（C++）：
    - **适用场景**：
  - **2. 哈希表优化：稀疏数据的空间压缩**
  - - **原理**：
    - **实现要点**：
    - **代码示例**（C++）：
    - **适用场景**：
  - **3. 原地计数排序：减少额外空间**
  - - **原理**：
    - **实现要点**：
    - **代码示例**（C++）：
    - **适用场景**：
  - **4. 并行计数排序：加速大数据集**
  - - **原理**：
    - **实现要点**：
    - **代码示例**（C++）：
    - **适用场景**：
  - **5. 位压缩优化：极端空间节约**
  - - **原理**：
    - **实现要点**：
    - **代码示例**（C++）：
    - **适用场景**：
  - **6. 动态范围调整：适应实际数据分布**
  - - **原理**：
    - **实现要点**：
    - **代码示例**（C++）：
    - **适用场景**：
  - **总结与选择建议**
- 8. **桶排序（Bucket Sort）**
- - **1. 动态桶划分优化**
  - - **核心思想**：
    - **实现方法**（C++）：
    - **优势**：
  - **2. 并行化桶排序**
  - - **核心思想**：
    - **实现方法**（C++）：
    - **优势**：
  - **3. 链表优化桶存储**
  - - **核心思想**：
    - **实现方法**（C++）：
    - **优势**：
  - **4. 哈希表优化稀疏数据**
  - - **核心思想**：
    - **实现方法**（C++）：
    - **优势**：
  - **5. 混合排序策略**
  - - **核心思想**：
    - **实现方法**（C++）：
    - **优势**：
  - **总结与选择建议**
- 9. **基数排序（Radix Sort）**
- - 一、**基数选择优化**
  - 二、**空间优化**
  - 五、**数据类型扩展**
  - 六、**稳定性保障**
**特殊场景算法**
- - MSD（最高位优先）基数排序
  - LSD（最低位优先）基数排序
  - 性能优化：多基数处理
  - 惰性排序（Lazy Sorting）**
  - **总结与分类**

基础排序算法

1. 冒泡排序（Bubble Sort）

原理：通过相邻元素比较，逐步将最大元素“冒泡”到序列末尾。
稳定性：稳定
时间复杂度：O(n²)

示例代码：

void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(arr[j], arr[j + 1]);}}}
}

冒泡排序优化

1. 提前终止优化（标志位优化）

原理：

在每一轮遍历中，若未发生任何元素交换，说明数组已有序，可直接终止排序，避免无效遍历。

实现示例（以C++为例）：

void optimizedBubbleSort(int arr[], int n) {bool swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);swapped = true;}}if (!swapped) break;}
}

优点：

对部分有序的数组效率显著提升（时间复杂度可降为O(n)）。
简单易实现，仅需增加一个标志位。

2. 双向冒泡排序（鸡尾酒排序，Cocktail Shaker Sort）

原理：

在传统单方向冒泡的基础上，增加从右到左的逆向扫描，将较小的元素逐步移到左侧。每轮交替进行双向扫描，减少遍历次数。

实现示例（以C++为例）：

void cocktailShakerSort(int arr[], int n) {int left = 0, right = n - 1;bool swapped;while (left < right) {swapped = false;for (int i = left; i < right; i++) {if (arr[i] > arr[i + 1]) {std::swap(arr[i], arr[i + 1]);swapped = true;}}if (!swapped) break;right--;swapped = false;for (int i = right; i > left; i--) {if (arr[i] < arr[i - 1]) {std::swap(arr[i], arr[i - 1]);swapped = true;}}if (!swapped) break;left++;}
}

优点：

适用于反向有序的数组（如完全降序），效率优于传统冒泡排序。
减少单向扫描的盲区，更适合数据分布不均匀的场景。

3. 记录最后交换位置优化

原理：

在每轮遍历中，记录最后一次发生交换的位置，下一轮只需扫描到此位置之前的元素，减少冗余比较。

实现示例（C++）：

void bubbleSortWithLastSwap(int arr[], int n) {int lastSwap = n - 1;for (int i = 0; i < n; i++) {bool swapped = false;int currentLast = 0;for (int j = 0; j < lastSwap; j++) {if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);swapped = true;currentLast = j;}}lastSwap = currentLast;if (!swapped) break;}
}

优点：

进一步减少比较次数，尤其在部分有序时效率更高。
可与提前终止结合使用，形成双重优化。

4. 间隔优化（跳跃式扫描）

原理：

类似于希尔排序的思想，通过设置间隔（如每隔k个元素）进行分组冒泡，减少初期数据的无序性，从而加速后续排序。

实现示例（C++）：

void gapBubbleSort(int arr[], int n, int gap = 2) {for (int i = 0; i < n; i++) {for (int j = 0; j + gap < n; j += gap) {if (arr[j] > arr[j + gap]) {std::swap(arr[j], arr[j + gap]);}}}
}

优点：

前期通过大步长快速排列，后期逐步缩小步长，适合大规模数据。
结合了冒泡排序的稳定性和希尔排序的高效性。

5. 并行化优化

原理：

将数组分段，每段独立进行冒泡排序，最后合并结果。适用于多核处理器或分布式环境。

实现示例（概念性C++伪代码）：

#include <thread>void parallelBubbleSort(int arr[], int start, int end) {// 实际实现需考虑线程同步和任务划分// 此处为简化示例for (int i = start; i < end; i++) {for (int j = start; j < end - i - 1; j++) {if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);}}}
}// 主函数中调用
void sortWrapper(int arr[], int n) {int mid = n / 2;std::thread t1(parallelBubbleSort, arr, 0, mid);std::thread t2(parallelBubbleSort, arr, mid, n);t1.join();t2.join();// 合并结果（实际需要合并算法）
}

优点：

充分利用多核资源，缩短大规模数据排序时间。
可结合提前终止或双向扫描进一步优化。

总结与适用场景

优化方式	适用场景	优点
提前终止	部分有序、近乎有序的数组	极简实现，效率提升显著
双向冒泡（鸡尾酒排序）	反向有序、数据分布不均匀的数组	减少单向扫描盲区，适应性强
记录最后交换位置	部分有序且需极致优化的场景	减少冗余比较，双重优化效果
间隔优化	大规模数据预处理	结合希尔排序思想，提升初期排序效率
并行化	多核/分布式环境下的超大规模数据	充分利用硬件资源，缩短整体耗时

通过合理选择变体优化，冒泡排序可在特定场景下接近甚至超越更高阶算法（如插入排序）的性能，同时保持代码简洁性。

2. 选择排序（Selection Sort）

原理：每次选择最小（或最大）元素放到已排序序列的末尾。
稳定性：不稳定
时间复杂度：O(n²)
示例代码：

// 选择排序函数，对整型数组进行升序排列
void selectSort(int unordered[], int len) {// 遍历数组的每一个位置（除最后一个）for (int i = 0; i < len - 1; ++i) {int minIndex = i; // 初始化当前最小值索引// 在剩余未排序部分寻找最小值for (int k = i + 1; k < len; ++k) {if (unordered[k] < unordered[minIndex]) {minIndex = k; // 更新最小值索引}}// 如果发现更小的元素则交换if (minIndex != i) {std::swap(unordered[i],unordered[minIndex]);}}
}

1. 避免无效交换的优化

原理：

在每轮遍历中，若发现当前轮次的最小元素已位于正确位置（即minIndex == i），则无需执行交换操作，减少不必要的赋值和交换。

实现示例（C++）：

void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex != i) { // 仅当需要交换时执行std::swap(arr[i], arr[minIndex]);}}
}

优点：

减少交换次数：尤其适用于部分有序的数组，可显著降低时间消耗。
实现简单：仅需增加一个条件判断，逻辑清晰。

2. 双向选择排序（双指针法）

原理：

每轮遍历中，同时从数组的两端出发，分别选择当前未排序部分的最小值和最大值，将其放到已排序部分的起始和末尾。通过双向扫描，减少遍历次数。

实现示例（C++）：

void dualSelectionSort(int arr[], int n) {int left = 0, right = n - 1;while (left < right) {int minIdx = left, maxIdx = left;for (int i = left + 1; i <= right; i++) {if (arr[i] < arr[minIdx]) minIdx = i;if (arr[i] > arr[maxIdx]) maxIdx = i;}// 交换最小值到左端if (minIdx != left) {std::swap(arr[left], arr[minIdx]);}// 处理最大值交换（需考虑最大值可能在左端的情况）if (maxIdx == left) maxIdx = minIdx;if (maxIdx != right) {std::swap(arr[right], arr[maxIdx]);}left++;right--;}
}

优点：

减少遍历次数：每轮遍历只需覆盖未排序部分一次，效率接近O(n²/2)。
适应多种数据分布：对反向有序或部分有序的数组效率更高。

3. 提前终止优化

原理：

若在某轮遍历中，未找到比当前轮次最小值更小的元素（即数组已有序），则提前终止排序。尽管选择排序通常无法像冒泡排序一样高效提前终止，但在某些变体中可通过额外判断实现。

实现示例（C++）：

void selectionSortWithEarlyTerm(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex == i) {break;  // 提前终止}std::swap(arr[i], arr[minIndex]);}
}

优点：

适合部分有序数组：若数组已基本有序，可显著减少遍历轮次。
逻辑简单：仅需增加一个终止条件。

4. 混合排序策略

原理：

将选择排序与其他算法（如插入排序、快速排序）结合，在小规模数据中使用选择排序，大规模数据中切换为更高效的算法。例如：

小规模数据：选择排序因实现简单且空间复杂度低（O(1)）而适用。
大规模数据：结合快速排序的分治思想，减少时间复杂度。

优点：

灵活性高：根据数据规模动态选择算法。
空间效率高：选择排序的原地特性适合内存受限场景。

总结与适用场景

优化方式	适用场景	优点
避免无效交换	部分有序、交换成本高的数组	减少赋值和交换操作，提升效率
双向选择排序	反向有序、数据分布不均匀的数组	减少遍历次数，效率接近O(n²/2)
提前终止	已基本有序的数组	避免冗余遍历，简化逻辑
混合排序	数据规模动态变化的场景	结合不同算法优势，灵活高效

这些优化在保持选择排序简单性的同时，通过减少交换或遍历次数提升了性能，尤其适用于小规模或部分有序的数据集。

3. 插入排序（Insertion Sort）

原理：将元素逐个插入到已排序序列的适当位置。
稳定性：稳定
时间复杂度：O(n²)

示例代码：

void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int temp = arr[i];int j = i - 1;while (j >= 0 && arr[j] > temp) {arr[j + 1] = arr[j];j--;}arr[j + 1] = temp;}
}

1. 二分插入排序（Binary Insertion Sort）

原理：

在传统插入排序中，寻找插入位置时采用线性搜索，时间复杂度为O(n)。二分插入排序通过二分查找确定插入位置，将比较次数从O(n)降为O(log n)，从而减少时间复杂度。

实现示例（C++）：

int binary_search(int arr[], int val, int start, int end) {while (start < end) {int mid = start + (end - start) / 2;if (arr[mid] <= val) {start = mid + 1;} else {end = mid;}}return start;
}void binary_insertion_sort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int pos = binary_search(arr, key, 0, i);// 移动元素并插入for (int j = i; j > pos; j--) {arr[j] = arr[j - 1];}arr[pos] = key;}
}

优点：

减少比较次数：适用于大规模数据，尤其是当数据分布较随机时。
稳定性：保持相等元素的相对顺序，与基础插入排序一致。

2. 希尔排序（Shell Sort）

原理：

希尔排序是插入排序的扩展，通过分组间隔排序减少初期数据的无序性。具体步骤如下：

设定初始间隔（如gap = n//2），将数组分为若干子序列。
对每个子序列进行插入排序。
逐步缩小间隔（如gap //= 2），重复上述过程，直到gap=1（即全局插入排序）。

实现示例（C++）：

void shell_sort(int arr[], int n) {for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j = i;while (j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap];j -= gap;}arr[j] = temp;}}
}

优点：

效率提升：时间复杂度介于O(n log² n)到O(n^1.5)，远优于基础插入排序。
适应大规模数据：通过间隔分组，减少早期元素的移动次数。

3. 减少元素移动的优化

原理：

传统插入排序在移动元素时，每次仅后移一个位置。优化思路是一次性移动多个元素，减少内层循环的赋值操作次数。

实现示例（C++）：

void optimized_insertion_sort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;// 找到插入位置while (j >= 0 && arr[j] > key) {j--;}j++; // 插入位置// 一次性移动元素if (i != j) {for (int k = i; k > j; k--) {arr[k] = arr[k - 1];}arr[j] = key;}}
}

优点：

降低赋值次数：尤其在数据接近有序时，效率显著提升。
代码简洁：仅需修改内层循环的移动逻辑。

4. 递归实现（Recursive Insertion Sort）

原理：

将插入排序的迭代过程改为递归，通过不断对前n-1个元素排序，再插入第n个元素。逻辑更清晰，但栈空间开销较大。

实现示例（C++）：

void recursive_insertion_sort(int arr[], int n) {if (n <= 1) return;// 先对前n-1个元素排序recursive_insertion_sort(arr, n - 1);// 插入第n个元素int key = arr[n - 1];int j = n - 2;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;
}

优点：

代码可读性高：递归结构更符合分治思想。
适用教学场景：帮助理解插入排序的分步过程。

总结与适用场景

优化方式	时间复杂度	适用场景	优点
二分插入排序	O(n²)/O(n log n)	大规模数据或随机分布数据	减少比较次数，适合数据分布分散的场景
希尔排序	O(n log² n)	大规模数据或需要高效预处理的场景	通过间隔分组减少初期无序性，效率显著
减少元素移动优化	O(n²)	数据接近有序或赋值操作耗时的场景	降低赋值次数，提升实际运行速度
递归实现	O(n²)	教学或代码风格偏好递归的场景	逻辑清晰，便于理解递归思想

这些变体在不同场景下各有优势，实际应用中需根据数据规模、有序性和性能需求选择合适的优化策略。

4. 快速排序（Quick Sort）

原理：通过枢轴划分序列，递归排序左右子序列。
稳定性：不稳定
时间复杂度：O(n log n)

示例代码：

void quickSort(int a[], int l, int r) {if (l >= r) return;int i = l, j = r, key = a[l];while (i < j) {while (i < j && a[j] >= key) j--;if (i < j) a[i++] = a[j];while (i < j && a[i] < key) i++;if (i < j) a[j--] = a[i];}a[i] = key;quickSort(a, l, i - 1);quickSort(a, i + 1, r);
}

基准选择优化

随机基准（Randomized Pivot）

原理：随机选择基准元素，避免最坏情况下的时间复杂度退化（如已有序数组）。
实现（C++）：

#include <cstdlib>
#include <ctime>int partition(int arr[], int low, int high);void randomized_quicksort(int arr[], int low, int high) {if (low < high) {// 随机选择基准并交换到末尾srand(time(NULL));int random_idx = low + rand() % (high - low + 1);std::swap(arr[random_idx], arr[high]);int pi = partition(arr, low, high);randomized_quicksort(arr, low, pi - 1);randomized_quicksort(arr, pi + 1, high);}
}

优势：平均时间复杂度稳定在O(n log n)，适用于各种数据分布。

三数取中法（Median-of-Three）

原理：选择左端、右端和中间位置的三个元素的中位数作为基准，减少极端情况的概率。
实现（C++）：

int median_of_three(int arr[], int low, int high) {int mid = low + (high - low) / 2;// 找出三个元素的中位数if (arr[low] > arr[mid]) std::swap(arr[low], arr[mid]);if (arr[low] > arr[high]) std::swap(arr[low], arr[high]);if (arr[mid] > arr[high]) std::swap(arr[mid], arr[high]);return mid; // 返回中位数的索引
}void median_quicksort(int arr[], int low, int high) {if (low < high) {int median = median_of_three(arr, low, high);std::swap(arr[median], arr[high]); // 将中位数移到末尾int pi = partition(arr, low, high);median_quicksort(arr, low, pi - 1);median_quicksort(arr, pi + 1, high);}
}

优势：适应部分有序数据，降低分区不均衡的风险。

中位数基准（Median-of-Medians）

原理：将数组划分为长度为5的子数组，计算各子数组的中位数，再取这些中位数的中位数作为基准。
实现（C++）：

int median_of_medians(int arr[], int low, int high);void mom_quicksort(int arr[], int low, int high) {if (low < high) {int pivot_idx = median_of_medians(arr, low, high);std::swap(arr[pivot_idx], arr[high]);int pi = partition(arr, low, high);mom_quicksort(arr, low, pi - 1);mom_quicksort(arr, pi + 1, high);}
}

优势：保证最坏时间复杂度为O(n log n)，但实现较复杂。

分区策略优化

三向切分（Three-Way Partitioning）

原理：将数组分为小于、等于和大于基准的三部分，避免重复元素多次参与排序。
实现（C++）：

void three_way_quicksort(int arr[], int low, int high) {if (high <= low) return;int lt = low;    // 小于基准的右边界int gt = high;   // 大于基准的左边界int i = low + 1; // 当前元素指针int pivot = arr[low];while (i <= gt) {if (arr[i] < pivot) {std::swap(arr[lt++], arr[i++]);} else if (arr[i] > pivot) {std::swap(arr[i], arr[gt--]);} else {i++;}}three_way_quicksort(arr, low, lt - 1);three_way_quicksort(arr, gt + 1, high);
}

优势：适用于包含大量重复元素的数组（如字符串、数据库查询），效率显著提升。

双轴快速排序（Dual-Pivot Quick Sort）

原理：选择两个基准值（如数组两端的元素），将数组分为三部分：小于第一个基准、介于两基准之间、大于第二个基准。
实现（C++）：

void dual_pivot_quicksort(int arr[], int low, int high) {if (low < high) {// 确保pivot1 <= pivot2if (arr[low] > arr[high]) {std::swap(arr[low], arr[high]);}int pivot1 = arr[low];int pivot2 = arr[high];int lt = low + 1;   // 小于pivot1的右边界int gt = high - 1;  // 大于pivot2的左边界int i = low + 1;    // 当前指针while (i <= gt) {if (arr[i] < pivot1) {std::swap(arr[i++], arr[lt++]);} else if (arr[i] > pivot2) {std::swap(arr[i], arr[gt--]);} else {i++;}}// 放置基准到正确位置std::swap(arr[low], arr[lt - 1]);std::swap(arr[high], arr[gt + 1]);// 递归排序三个分区dual_pivot_quicksort(arr, low, lt - 2);dual_pivot_quicksort(arr, lt, gt);dual_pivot_quicksort(arr, gt + 2, high);}
}

优势：减少递归深度，尤其适合大规模数据排序。

小规模数组优化

插入排序替代

原理：当子数组规模小于阈值（如10-20）时，切换为插入排序。
实现（C++）：

void insertion_sort(int arr[], int low, int high);void hybrid_quicksort(int arr[], int low, int high) {const int THRESHOLD = 16;if (high - low + 1 < THRESHOLD) {insertion_sort(arr, low, high);return;}int pi = partition(arr, low, high);hybrid_quicksort(arr, low, pi - 1);hybrid_quicksort(arr, pi + 1, high);
}

优势：减少递归调用开销，提升小数组排序效率。

递归与并行优化

尾递归优化（Tail Recursion Elimination）

原理：优先处理较短的子数组，并将递归调用限制为一次，减少栈空间占用。
实现（C++）：

void tail_recursive_quicksort(int arr[], int low, int high) {while (low < high) {int pi = partition(arr, low, high);// 优先处理较小的子数组if (pi - low < high - pi) {tail_recursive_quicksort(arr, low, pi - 1);low = pi + 1;} else {tail_recursive_quicksort(arr, pi + 1, high);high = pi - 1;}}
}

并行快速排序

原理：对左右子数组的排序任务进行并行处理，利用多核处理器加速。
实现（C++伪代码）：

#include <thread>void parallel_quicksort(int arr[], int low, int high, int depth = 0) {if (low >= high) return;const int MAX_DEPTH = 7;int pi = partition(arr, low, high);if (depth < MAX_DEPTH) {std::thread left(parallel_quicksort, arr, low, pi - 1, depth + 1);std::thread right(parallel_quicksort, arr, pi + 1, high, depth + 1);left.join();right.join();} else {parallel_quicksort(arr, low, pi - 1, depth + 1);parallel_quicksort(arr, pi + 1, high, depth + 1);}
}

优势：适用于大规模数据，但需权衡线程创建开销。

其他优化

缓存优化
- 原理：优化数据访问模式，提高缓存命中率。
- 实现：优先处理局部数据，减少跨缓存行的跳跃访问。（代码实现依赖具体硬件架构）

聚集基准与稳定性改进

原理：结合三向切分和中位数基准，保持相等元素的相对顺序。
实现（C++）：

void stable_quicksort(int arr[], int low, int high) {if (high <= low) return;// 使用三数取中法选择基准int median = median_of_three(arr, low, high);int pivot = arr[median];// 三向切分int lt = low, gt = high, i = low;while (i <= gt) {if (arr[i] < pivot) {std::swap(arr[lt++], arr[i++]);} else if (arr[i] > pivot) {std::swap(arr[i], arr[gt--]);} else {i++;}}stable_quicksort(arr, low, lt - 1);stable_quicksort(arr, gt + 1, high);
}

适用场景：需要稳定排序的场景（如多键排序）。

分区函数实现

// Lomuto分区方案（基础实现）
int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j <= high - 1; j++) {if (arr[j] <= pivot) {i++;std::swap(arr[i], arr[j]);}}std::swap(arr[i + 1], arr[high]);return i + 1;
}// Hoare分区方案（更高效）
int hoare_partition(int arr[], int low, int high) {int pivot = arr[low + (high - low) / 2];int i = low - 1;int j = high + 1;while (true) {do { i++; } while (arr[i] < pivot);do { j--; } while (arr[j] > pivot);if (i >= j) return j;std::swap(arr[i], arr[j]);}
}

总结与适用场景

优化方式	时间复杂度	适用场景	优点
随机基准	O(n log n)	一般数据分布	避免最坏情况，实现简单
三向切分	O(n log n)	大量重复元素	减少重复比较，效率高
双轴快速排序	O(n log n)	超大规模数据	分区更细致，递归深度低
插入排序替代	O(n log n)	小数组或递归深层	减少递归开销，提升实际速度
并行快速排序	O(n log n)/线性	多核处理器环境	充分利用硬件资源，速度倍增

以上优化方法可单独使用，也可组合应用。例如，结合三向切分与随机基准处理重复数据，或搭配并行优化加速大规模排序。实际应用中需根据数据特性和硬件环境选择合适策略。

5. 归并排序（Merge Sort）

原理：分治法，将序列分为子序列排序后合并。
稳定性：稳定
时间复杂度：O(n log n)
示例代码：

void merge_sort(int arr[], int left, int right) {if (left < right) {// 计算中间点，防止整数溢出int mid = left + (right - left) / 2;// 递归排序左半部分merge_sort(arr, left, mid);// 递归排序右半部分merge_sort(arr, mid + 1, right);// 合并两个有序子数组merge(arr, left, mid, right);}
}//合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {int i, j, k;int n1 = mid - left + 1;  // 左子数组长度int n2 = right - mid;     // 右子数组长度// 动态分配临时数组存储左右子数组int *L = (int *)malloc(n1 * sizeof(int));int *R = (int *)malloc(n2 * sizeof(int));// 检查内存分配是否成功if (L == NULL || R == NULL) {printf("Memory allocation failed!
");exit(EXIT_FAILURE);}// 拷贝数据到临时数组for (i = 0; i < n1; i++) {L[i] = arr[left + i];}for (j = 0; j < n2; j++) {R[j] = arr[mid + 1 + j];}// 合并临时数组到原数组i = 0;   // 左子数组索引j = 0;   // 右子数组索引k = left; // 原数组索引while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k++] = L[i++];} else {arr[k++] = R[j++];}}// 复制剩余元素（如果有）while (i < n1) {arr[k++] = L[i++];}while (j < n2) {arr[k++] = R[j++];}// 释放动态分配的内存free(L);free(R);
}

1. 小规模子数组优化

原理：

当子数组规模较小时（如长度小于15），递归调用的开销可能超过排序本身的时间。此时改用插入排序，利用其对小规模数据的高效性，可减少递归深度和函数调用开销。

实现示例（C++）：

#include <algorithm>
#include <vector>void insertion_sort(std::vector<int>& arr, int low, int high);
void merge(std::vector<int>& arr, int low, int mid, int high);void merge_sort(std::vector<int>& arr, int low, int high) {const int THRESHOLD = 15;if (high - low < THRESHOLD) {insertion_sort(arr, low, high);return;}int mid = low + (high - low) / 2;merge_sort(arr, low, mid);merge_sort(arr, mid + 1, high);merge(arr, low, mid, high);
}

优点：

减少递归开销：避免深度递归调用的栈空间消耗。
提升小数组效率：插入排序对小规模数据更高效。

2. 合并过程优化

原理：

在合并前检查子数组是否已有序（如左半部分最大值≤右半部分最小值），若有序则跳过合并步骤，减少不必要的操作。

实现示例（C++）：

void merge(std::vector<int>& arr, int low, int mid, int high) {// 检查是否已有序if (arr[mid] <= arr[mid + 1]) {return;}// 正常合并逻辑std::vector<int> temp(high - low + 1);int i = low, j = mid + 1, k = 0;while (i <= mid && j <= high) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}while (i <= mid) temp[k++] = arr[i++];while (j <= high) temp[k++] = arr[j++];for (int idx = 0; idx < k; idx++) {arr[low + idx] = temp[idx];}
}

优点：

减少冗余操作：在部分有序数组中显著提升效率。

3. 空间优化：原地归并

原理：

传统归并排序需额外空间存储临时数组。通过交替使用原数组和辅助数组作为目标，可减少内存分配次数，提升缓存命中率。

实现示例（C++）：

void merge_sort_optimized(std::vector<int>& arr) {int n = arr.size();std::vector<int> temp(n); // 预先分配辅助数组for (int width = 1; width < n; width *= 2) {for (int i = 0; i < n; i += 2 * width) {int left = i;int mid = std::min(i + width, n);int right = std::min(i + 2 * width, n);// 交替使用原数组和辅助数组if (width % 2 == 1) {merge(arr, temp, left, mid, right);} else {merge(temp, arr, left, mid, right);}}}// 最终结果在原始数组中if ((n & (n - 1)) != 0) { // 如果不是2的幂次方arr = temp;}
}

优点：

降低空间复杂度：仅需O(n)辅助空间，且可重复利用。
提升缓存效率：减少动态内存分配，提高局部性。

4. 非递归（自底向上）归并排序

原理：

传统的归并排序是递归实现的，对于大数组可能会导致栈溢出。自底向上的方式从最小的子数组开始逐步合并，避免了递归调用。

实现示例（C++）：

void merge_sort_bottom_up(std::vector<int>& arr) {int n = arr.size();std::vector<int> temp(n);for (int curr_size = 1; curr_size < n; curr_size *= 2) {for (int left = 0; left < n - 1; left += 2 * curr_size) {int mid = std::min(left + curr_size - 1, n - 1);int right = std::min(left + 2 * curr_size - 1, n - 1);if (mid < right) {// 合并子数组int i = left, j = mid + 1, k = left;while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}while (i <= mid) temp[k++] = arr[i++];while (j <= right) temp[k++] = arr[j++];for (k = left; k <= right; k++) {arr[k] = temp[k];}}}}
}

优点：

避免栈溢出：适合处理超大规模数据。
迭代高效：减少递归的函数调用开销。

5. 外部排序（处理超大数据集）

原理：

当数据无法全部加载到内存时，将数组分块排序后写入磁盘，再逐块合并。归并排序天然适合此场景，因其合并步骤可处理外部存储。

实现示例（C++伪代码）：

#include <fstream>
#include <queue>
#include <vector>struct Chunk {std::ifstream file;int current;bool operator>(const Chunk& other) const {return current > other.current;}
};void external_sort(const std::string& input_file, const std::string& output_file, int chunk_size) {// 1. 分块排序std::ifstream in(input_file, std::ios::binary);std::vector<std::string> temp_files;std::vector<int> buffer(chunk_size);while (in) {// 读取块数据int count = 0;while (count < chunk_size && in.read(reinterpret_cast<char*>(&buffer[count]), sizeof(int))) {count++;}// 内存排序std::sort(buffer.begin(), buffer.begin() + count);// 写入临时文件std::string temp_name = "temp_" + std::to_string(temp_files.size());std::ofstream out(temp_name, std::ios::binary);out.write(reinterpret_cast<char*>(buffer.data()), count * sizeof(int));temp_files.push_back(temp_name);}// 2. 多路归并std::priority_queue<Chunk, std::vector<Chunk>, std::greater<Chunk>> min_heap;std::ofstream out(output_file, std::ios::binary);// 初始化堆for (const auto& file : temp_files) {std::ifstream in(file, std::ios::binary);int value;if (in.read(reinterpret_cast<char*>(&value), sizeof(int))) {min_heap.push({std::move(in), value});}}// 归并排序while (!min_heap.empty()) {Chunk top = min_heap.top();min_heap.pop();int value = top.current;out.write(reinterpret_cast<char*>(&value), sizeof(int));if (top.file.read(reinterpret_cast<char*>(&value), sizeof(int))) {top.current = value;min_heap.push(std::move(top));}}// 清理临时文件for (const auto& file : temp_files) {std::remove(file.c_str());}
}

优点：

处理超大数据集：突破内存限制，适用于数据库排序等场景。

6. 不均衡分割变体（a-to-b Split）

原理：

传统归并排序均分数组，可能导致递归深度不平衡。采用不均衡分割（如按比例a:b划分），可优化递归树结构，降低时间复杂度。

实现示例（C++）：

void unbalanced_merge_sort(std::vector<int>& arr, int low, int high, double split_ratio = 0.3) {if (low >= high) return;// 不均衡分割int split = low + static_cast<int>((high - low) * split_ratio);unbalanced_merge_sort(arr, low, split, split_ratio);unbalanced_merge_sort(arr, split + 1, high, split_ratio);merge(arr, low, split, high);
}

时间复杂度：

若分割比例为ε:(1-ε)，则时间复杂度为O(n log n)（与均衡分割相同，但常数因子更优）。

适用场景：

适用于数据分布不均匀或硬件缓存特性特殊的场景（如GPU并行计算）。

辅助函数实现

void insertion_sort(std::vector<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 merge(std::vector<int>& src, std::vector<int>& dest, int low, int mid, int high) {int i = low, j = mid, k = low;while (i < mid && j < high) {if (src[i] <= src[j]) {dest[k++] = src[i++];} else {dest[k++] = src[j++];}}while (i < mid) dest[k++] = src[i++];while (j < high) dest[k++] = src[j++];
}

总结与适用场景

优化方式	核心思想	适用场景
小规模插入排序	替换递归基准条件	递归深层或部分有序数组
合并前有序性检查	减少冗余合并操作	部分有序或近乎有序的数组
原地归并	交替使用辅助数组	内存受限或需高频调用的场景
非递归归并	自底向上迭代	超大规模数据或栈空间有限的环境
外部排序	分块+多路归并	超大数据集（如数据库、文件排序）
不均衡分割	按比例划分数组	数据分布不均或硬件特性优化场景

实际应用中，常组合多种优化策略。例如，自底向上归并配合插入排序和空间优化，既能提升效率，又能控制内存使用。

6. 堆排序（Heap Sort）

原理：利用堆数据结构（最大堆/最小堆）选择元素。
稳定性：不稳定
时间复杂度：O(n log n)
示例代码：

// 堆调整函数（维护最大堆性质）
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 buildMaxHeap(int arr[], int n){// 从最后一个非叶子节点开始向上调整for(int i = n/2 - 1; i >= 0; --i){heapify(arr, n, i);}
}// 堆排序主函数
void heapSort(int arr[], int n){// Step 1: 构建最大堆buildMaxHeap(arr, n);// Step 2: 逐个提取元素for(int i = n-1; i > 0; --i){// 将当前堆顶（最大值）移到数组末尾swap(arr[0], arr[i]);// 调整剩余元素使其成为新的最大堆heapify(arr, i, 0);}
}

1. 建堆优化：线性时间建堆

原理：

传统建堆方法从最后一个非叶子节点开始，逐层向上调整堆结构。Floyd建堆算法通过一次性遍历数组，将元素逐步“上浮”到正确位置，时间复杂度为 (O(n))，且减少了递归或多次调整的开销。

实现要点（C++）：

#include <vector>
#include <algorithm>// Floyd线性时间建堆
void build_heap_floyd(std::vector<int>& arr) {int n = arr.size();// 从最后一个非叶子节点开始向前调整for (int i = (n - 2) / 2; i >= 0; i--) {sift_down(arr, i, n);}
}// 下沉调整
void sift_down(std::vector<int>& arr, int idx, int heap_size) {int largest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;// 找出当前节点和左右子节点中的最大值if (left < heap_size && arr[left] > arr[largest]) largest = left;if (right < heap_size && arr[right] > arr[largest]) largest = right;// 如果最大值不是当前节点，交换并继续调整if (largest != idx) {std::swap(arr[idx], arr[largest]);sift_down(arr, largest, heap_size);}
}

优势：

时间复杂度稳定为 (O(n))，优于传统的 (O(n \log n)) 建堆方法。
减少递归调用，适合大规模数据。

2. Sift过程优化：减少比较次数

原理：

在 sift down 或 sift up 过程中，通过提前终止条件减少不必要的比较和交换。例如：

提前终止：若父节点已满足堆性质（如父节点大于等于子节点），则无需继续调整。
三叉比较法：在 sift down 时，同时比较左右子节点，选择较大的子节点交换，减少比较次数。

实现要点（C++）：

// 优化后的下沉调整（使用三叉比较法）
void optimized_sift_down(std::vector<int>& arr, int idx, int heap_size) {while (idx < heap_size) {int largest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;// 三叉比较：同时比较左右子节点if (left < heap_size && arr[left] > arr[largest]) largest = left;if (right < heap_size && arr[right] > arr[largest]) largest = right;// 提前终止：如果不需要交换则退出if (largest == idx) break;std::swap(arr[idx], arr[largest]);idx = largest;  // 继续向下调整}
}

优势：

降低平均比较次数，提升实际运行效率。
适合部分有序或重复元素较多的数组。

3. 混合排序策略：小堆切换插入排序

原理：

当堆规模较小时（如长度小于某个阈值 (k)），切换为插入排序。因为插入排序对小规模数据的效率更高，且能减少递归深度。

实现要点（C++）：

// 混合堆排序（小堆时使用插入排序）
void hybrid_heap_sort(std::vector<int>& arr) {const int THRESHOLD = 15;int n = arr.size();// 构建最大堆build_heap_floyd(arr);// 逐步提取堆顶元素for (int i = n - 1; i > 0; i--) {std::swap(arr[0], arr[i]);// 小规模子堆使用插入排序if (i < THRESHOLD) {insertion_sort(arr, 0, i);break;}optimized_sift_down(arr, 0, i);}
}

优势：

减少递归调用开销，提升小堆排序效率。
结合两种算法的优势，适应不同规模数据。

4. 缓存优化：提升数据局部性

原理：

堆排序的 sift down 和 sift up 操作可能导致内存访问不连续，降低缓存命中率。通过优化数据访问顺序或存储结构，可提升缓存利用率。

实现要点（C++）：

// 缓存友好的堆排序
void cache_friendly_heap_sort(std::vector<int>& arr) {int n = arr.size();// 构建最大堆build_heap_floyd(arr);// 分层处理：优先处理深度较小的子树std::vector<int> levels;for (int depth = 0; (1 << depth) <= n; depth++) {levels.push_back(1 << depth);}// 从底层向上逐步提取堆顶for (int i = n - 1; i > 0; i--) {std::swap(arr[0], arr[i]);// 优先处理浅层子树for (int depth = levels.size() - 1; depth >= 0; depth--) {int start = levels[depth];if (start < i) {optimized_sift_down(arr, start, i);}}optimized_sift_down(arr, 0, i);}
}

优势：

提高缓存命中率，减少内存访问延迟。
提升对大规模数据的排序速度。

5. 并行化建堆与调整

原理：

利用多核处理器并行执行建堆和调整操作。例如：

并行建堆：将数组划分为多个子区间，分别建堆后合并。
并行 sift down：在堆调整时，对左右子树的调整任务并行执行。

实现要点（C++伪代码）：

#include <thread>
#include <vector>// 并行建堆
void parallel_build_heap(std::vector<int>& arr, int start, int end) {if (end - start <= 1000) { // 小规模子堆直接构建for (int i = (end - 2) / 2; i >= start; i--) {sift_down(arr, i, end);}return;}int mid = start + (end - start) / 2;std::thread left(parallel_build_heap, std::ref(arr), start, mid);std::thread right(parallel_build_heap, std::ref(arr), mid, end);left.join();right.join();// 合并子堆for (int i = mid - 1; i >= start; i--) {sift_down(arr, i, end);}
}

优势：

显著缩短排序时间，尤其适合超大规模数据。
充分利用多核资源，提升吞吐量。

6. 非递归实现：减少函数调用开销

原理：

通过迭代替代递归实现堆排序，避免递归栈的空间消耗和函数调用开销。

实现要点（C++）：

// 非递归堆排序
void iterative_heap_sort(std::vector<int>& arr) {int n = arr.size();// 迭代方式建堆for (int i = (n - 2) / 2; i >= 0; i--) {int idx = i;while (idx < n) {int largest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;if (left < n && arr[left] > arr[largest]) largest = left;if (right < n && arr[right] > arr[largest]) largest = right;if (largest == idx) break;std::swap(arr[idx], arr[largest]);idx = largest;}}// 迭代方式提取堆顶for (int i = n - 1; i > 0; i--) {std::swap(arr[0], arr[i]);int idx = 0;while (idx < i) {int largest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;if (left < i && arr[left] > arr[largest]) largest = left;if (right < i && arr[right] > arr[largest]) largest = right;if (largest == idx) break;std::swap(arr[idx], arr[largest]);idx = largest;}}
}

优势：

降低空间复杂度，适合嵌入式系统或栈空间有限的环境。
提升迭代效率，减少递归调用的额外开销。

辅助函数实现

// 插入排序（用于混合策略）
void insertion_sort(std::vector<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;}
}

总结与适用场景

优化方法	核心思想	适用场景
线性时间建堆	Floyd算法，单次遍历建堆	大规模数据，需快速建堆
Sift过程优化	提前终止或三叉比较	部分有序或重复元素多的数组
混合排序策略	小堆切换插入排序	小规模数据或递归深层
缓存优化	层序存储或块状调整	内存受限或需高频缓存的场景
并行化	多核并行建堆与调整	超大规模数据或多核处理器环境
非递归实现	迭代替代递归	嵌入式系统或栈空间有限的环境

实际应用中，常组合多种优化策略。例如，并行建堆 + 混合排序 + 缓存优化 可大幅提升效率，而 非递归实现 + Sift优化 适合资源受限的场景。根据数据规模、硬件环境和性能需求选择合适的变体，能有效发挥堆排序的优势。

7. 计数排序（Counting Sort）

原理：统计元素频率，直接按顺序填充结果。
稳定性：稳定
时间复杂度：O(n + k)
适用场景：整数且范围不大（k为元素范围）。

void countingSort(int arr[], int n) {if (n <= 1) return;// Step 1: Find the maximum and minimum elementsint max = arr[0], min = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) max = arr[i];if (arr[i] < min) min = arr[i];}// Step 2: Create and initialize the count arrayint range = max - min + 1;int *count = (int *)calloc(range, sizeof(int));if (!count) {exit(EXIT_FAILURE);}// Step 3: Populate the count array with frequenciesfor (int i = 0; i < n; i++) {count[arr[i] - min]++;}// Step 4: Modify count array to store cumulative countsfor (int i = 1; i < range; i++) {count[i] += count[i - 1];}// Step 5: Create an output array and place elements in correct orderint *output = (int *)malloc(n * sizeof(int));if (!output) {free(count);exit(EXIT_FAILURE);}// Traverse the original array from end to start for stable sortfor (int i = n - 1; i >= 0; i--) {int x = arr[i];int index = x - min;int pos = count[index] - 1; // Get the position in output arrayoutput[pos] = x;            // Place the elementcount[index]--;            // Decrement the count for next occurrence}// Copy the sorted data back to the original arraymemcpy(arr, output, n * sizeof(int));// Free allocated memoryfree(count);free(output);
}

计数排序是鸽巢排序的改良版

1. 支持负数的计数排序

原理：

通过偏移量将负数转换为非负数，扩展算法对包含负数的数组的适用性。具体步骤为：

找到数组中的最小值 ( \text{min} ) 和最大值 ( \text{max} )。
计算值域范围 ( k = \text{max} - \text{min} + 1 )。
创建大小为 ( k ) 的计数数组，索引为 ( \text{num} - \text{min} )。

实现要点：

偏移量调整：将所有元素减去最小值，使最小值变为0。
稳定性：反向遍历原数组，保证相同元素的相对顺序。

代码示例（C++）：

#include <vector>
#include <algorithm>
#include <climits>void counting_sort_with_negatives(std::vector<int>& arr) {if (arr.empty()) return;// 查找最小值和最大值int min_val = *std::min_element(arr.begin(), arr.end());int max_val = *std::max_element(arr.begin(), arr.end());int range = max_val - min_val + 1;// 创建计数数组std::vector<int> count(range, 0);// 统计频率for (int num : arr) {count[num - min_val]++;}// 计算累计频率for (int i = 1; i < range; i++) {count[i] += count[i - 1];}// 创建输出数组（保持稳定性）std::vector<int> output(arr.size());for (int i = arr.size() - 1; i >= 0; i--) {int num = arr[i];output[count[num - min_val] - 1] = num;count[num - min_val]--;}// 复制回原数组arr = output;
}

适用场景：

数据包含负值的场景（如温度、海拔等）。

2. 哈希表优化：稀疏数据的空间压缩

原理：

当元素值域范围 ( k ) 极大但实际元素种类较少时，用哈希表替代计数数组，仅存储存在的元素及其频次，减少空间浪费。

实现要点：

哈希表存储：键为元素值，值为出现次数。
累加计数：遍历哈希表的键，按顺序累加频次。
输出填充：根据累加结果将元素放入正确位置。

代码示例（C++）：

#include <vector>
#include <map>
#include <algorithm>void counting_sort_with_hash(std::vector<int>& arr) {if (arr.empty()) return;// 使用map存储频率std::map<int, int> freq_map;for (int num : arr) {freq_map[num]++;}// 计算累计频率int total = 0;for (auto& pair : freq_map) {total += pair.second;pair.second = total;}// 创建输出数组std::vector<int> output(arr.size());// 反向填充（保持稳定性）for (int i = arr.size() - 1; i >= 0; i--) {int num = arr[i];output[freq_map[num] - 1] = num;freq_map[num]--;}arr = output;
}

适用场景：

数据范围极大但元素种类稀疏（如ID排序、IP地址排序）。

3. 原地计数排序：减少额外空间

原理：

通过直接在原数组上修改，省去输出数组的空间开销。但需牺牲稳定性或增加时间复杂度。

实现要点：

正向填充：从小到大遍历计数数组，将元素依次填入原数组。
稳定性处理：需结合特殊标记或额外的逻辑保持稳定性（复杂且较少使用）。

代码示例（C++）：

#include <vector>
#include <algorithm>void in_place_counting_sort(std::vector<int>& arr) {if (arr.empty()) return;// 查找最小值和最大值int min_val = *std::min_element(arr.begin(), arr.end());int max_val = *std::max_element(arr.begin(), arr.end());int range = max_val - min_val + 1;// 创建计数数组std::vector<int> count(range, 0);// 统计频率for (int num : arr) {count[num - min_val]++;}// 直接填充原数组（牺牲稳定性）int index = 0;for (int i = 0; i < range; i++) {while (count[i] > 0) {arr[index++] = i + min_val;count[i]--;}}
}

适用场景：

内存受限且允许修改原数组的场景（如嵌入式系统）。

4. 并行计数排序：加速大数据集

原理：

利用多线程并行化统计和累加步骤，缩短处理超大数据集的时间。

实现要点：

分块统计：将数组划分为多个子块，分别统计频次。
合并累加：并行归约累加结果，生成全局计数数组。
并行填充：按计数数组分配元素位置。

代码示例（C++）：

#include <vector>
#include <algorithm>
#include <thread>
#include <mutex>
#include <atomic>void parallel_counting_sort(std::vector<int>& arr) {if (arr.empty()) return;// 查找最小值和最大值int min_val = *std::min_element(arr.begin(), arr.end());int max_val = *std::max_element(arr.begin(), arr.end());int range = max_val - min_val + 1;// 创建计数数组std::vector<int> global_count(range, 0);std::mutex mtx;// 并行统计频率auto worker = [&](int start, int end) {std::vector<int> local_count(range, 0);for (int i = start; i < end; i++) {local_count[arr[i] - min_val]++;}std::lock_guard<std::mutex> lock(mtx);for (int i = 0; i < range; i++) {global_count[i] += local_count[i];}};// 划分任务const int num_threads = std::thread::hardware_concurrency();const int block_size = arr.size() / num_threads;std::vector<std::thread> threads;for (int i = 0; i < num_threads; i++) {int start = i * block_size;int end = (i == num_threads - 1) ? arr.size() : start + block_size;threads.emplace_back(worker, start, end);}// 等待所有线程完成for (auto& t : threads) t.join();// 累加计数for (int i = 1; i < range; i++) {global_count[i] += global_count[i - 1];}// 创建输出数组std::vector<int> output(arr.size());// 原子计数器用于并行填充std::vector<std::atomic<int>> positions(range);for (int i = 0; i < range; i++) {positions[i] = global_count[i];}// 并行填充auto filler = [&](int start, int end) {for (int i = end - 1; i >= start; i--) {int num = arr[i];int idx = --positions[num - min_val];output[idx] = num;}};threads.clear();for (int i = 0; i < num_threads; i++) {int start = i * block_size;int end = (i == num_threads - 1) ? arr.size() : start + block_size;threads.emplace_back(filler, start, end);}for (auto& t : threads) t.join();arr = output;
}

适用场景：

超大规模数据且支持多线程的环境（如分布式计算）。

5. 位压缩优化：极端空间节约

原理：

当元素重复次数已知且有限时，用位图（BitSet）或压缩编码存储计数，减少内存占用。

实现要点：

位图存储：每个元素用1位表示是否存在（仅适用于二元判断）。
压缩计数：用更小的数据类型（如uint8_t）存储高频元素的计数。

代码示例（C++）：

#include <vector>
#include <algorithm>
#include <cstdint>void bit_compressed_counting_sort(std::vector<int>& arr) {if (arr.empty()) return;// 查找最小值和最大值int min_val = *std::min_element(arr.begin(), arr.end());int max_val = *std::max_element(arr.begin(), arr.end());int range = max_val - min_val + 1;// 使用uint8_t节省空间std::vector<uint8_t> count(range, 0);// 统计频率for (int num : arr) {if (count[num - min_val] < UINT8_MAX) {count[num - min_val]++;}}// 直接填充原数组int index = 0;for (int i = 0; i < range; i++) {while (count[i] > 0) {arr[index++] = i + min_val;count[i]--;}}
}

适用场景：

数据范围小且重复次数低（如布尔值、少量类别排序）。

6. 动态范围调整：适应实际数据分布

原理：

根据实际数据的最大值和最小值动态调整计数数组大小，而非依赖预设范围。

实现要点：

动态计算范围：( k = \text{max} - \text{min} + 1 )。
复用空间：若 ( k \ll n )，则空间复杂度显著降低。

代码示例（C++）：

#include <vector>
#include <algorithm>void dynamic_range_counting_sort(std::vector<int>& arr) {if (arr.empty()) return;// 动态查找范围int min_val = *std::min_element(arr.begin(), arr.end());int max_val = *std::max_element(arr.begin(), arr.end());int range = max_val - min_val + 1;// 仅当范围合理时使用计数排序if (range > 1000000) {std::sort(arr.begin(), arr.end());return;}// 标准计数排序流程std::vector<int> count(range, 0);for (int num : arr) count[num - min_val]++;int index = 0;for (int i = 0; i < range; i++) {while (count[i] > 0) {arr[index++] = i + min_val;count[i]--;}}
}

适用场景：

数据分布集中且范围远小于理论值的场景。

总结与选择建议

变体	核心优化点	适用场景
支持负数	偏移量转换	数据包含负值（如温度、海拔）
哈希表优化	稀疏数据的空间压缩	大范围但元素种类少（如ID、IP地址）
原地排序	省去输出数组	内存受限且允许修改原数组
并行排序	多线程加速统计与填充	超大规模数据且支持并行计算
位压缩	极端空间节约	小范围数据且重复次数少（如布尔值）
动态范围调整	按需分配计数数组	数据分布集中，范围远小于理论值

选择原则：

优先基础版：若数据为非负整数且范围较小。
处理负数：包含负值时使用偏移量。
大范围稀疏数据：采用哈希表优化。
内存敏感场景：尝试原地排序或位压缩。
超大数据：并行化处理提升效率。

8. 桶排序（Bucket Sort）

原理：将元素分配到桶中，对每个桶内排序后合并。
稳定性：稳定
时间复杂度：O(n + k)
适用场景：均匀分布的数据。

// 插入排序辅助函数
void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}// 桶排序主函数
void bucketSort(int arr[], int n) {if (n <= 1) return;// 1. 查找最大值和最小值int max = arr[0], min = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) max = arr[i];if (arr[i] < min) min = arr[i];}// 特殊情况处理：所有元素相同if (max == min) return;// 2. 计算桶的数量（取平方根向下取整）int num_buckets = (int)sqrt(n);num_buckets = num_buckets > 0 ? num_buckets : 1; // 确保至少一个桶// 3. 计算每个桶的区间大小（向上取整）int range = max - min;int interval = (range + num_buckets - 1) / num_buckets; // 等价于ceil(range/num_buckets)// 4. 创建桶数组（使用动态数组）int **buckets = (int **)malloc(num_buckets * sizeof(int *));int *counts = (int *)calloc(num_buckets, sizeof(int)); // 记录每个桶的元素数量// 分配内存给每个桶for (int i = 0; i < num_buckets; i++) {buckets[i] = (int *)malloc((n + 1) * sizeof(int)); // 预分配最大可能空间if (!buckets[i]) {exit(EXIT_FAILURE);}}// 5. 分配元素到各桶for (int i = 0; i < n; i++) {int index = (arr[i] - min) / interval;// 处理边界情况，确保索引不越界if (index >= num_buckets) index = num_buckets - 1;buckets[index][counts[index]++] = arr[i];}// 6. 对每个桶单独排序for (int i = 0; i < num_buckets; i++) {if (counts[i] > 0) {insertionSort(buckets[i], counts[i]);}}// 7. 合并所有桶到原数组int pos = 0;for (int i = 0; i < num_buckets; i++) {for (int j = 0; j < counts[i]; j++) {arr[pos++] = buckets[i][j];}free(buckets[i]); // 释放桶内存}free(buckets);free(counts);
}

1. 动态桶划分优化

核心思想：

根据数据分布动态调整桶的数量和范围，避免固定桶数导致的数据倾斜问题。

实现方法（C++）：

#include <vector>
#include <algorithm>
#include <cmath>
#include <list>void adaptive_bucket_sort(std::vector<float>& arr) {if (arr.empty()) return;// 计算数据范围float min_val = *std::min_element(arr.begin(), arr.end());float max_val = *std::max_element(arr.end(), arr.end());float range = max_val - min_val;// 动态桶数量int bucket_count = arr.size();float bucket_size = range / bucket_count;// 创建桶std::vector<std::vector<float>> buckets(bucket_count);// 分配数据到桶for (float num : arr) {int index = static_cast<int>((num - min_val) / bucket_size);if (index >= bucket_count) index = bucket_count - 1;buckets[index].push_back(num);}// 对每个桶排序并合并结果int idx = 0;for (auto& bucket : buckets) {std::sort(bucket.begin(), bucket.end());for (float num : bucket) {arr[idx++] = num;}}
}

优势：

适应数据分布不均匀的场景，减少某些桶过载的情况。
支持负数和浮点数排序[⁵]。

2. 并行化桶排序

核心思想：

利用多线程对多个桶同时进行排序，提升大数据量下的处理效率。

实现方法（C++）：

#include <vector>
#include <algorithm>
#include <thread>
#include <mutex>
#include <future>void parallel_bucket_sort(std::vector<float>& arr) {if (arr.empty()) return;// 桶数量int bucket_count = arr.size();std::vector<std::vector<float>> buckets(bucket_count);// 分配数据到桶for (float num : arr) {int index = static_cast<int>(num * bucket_count);if (index >= bucket_count) index = bucket_count - 1;buckets[index].push_back(num);}// 并行排序每个桶std::vector<std::future<void>> futures;for (auto& bucket : buckets) {futures.push_back(std::async(std::launch::async, [&] {std::sort(bucket.begin(), bucket.end());}));}// 等待所有桶排序完成for (auto& fut : futures) fut.wait();// 合并结果int idx = 0;for (auto& bucket : buckets) {for (float num : bucket) {arr[idx++] = num;}}
}

优势：

显著缩短排序时间，尤其适用于超大规模数据[¹]。
可扩展性强，适合分布式计算环境。

3. 链表优化桶存储

核心思想：

用链表替代动态数组存储桶内元素，减少内存分配和扩容开销。

实现方法（C++）：

#include <vector>
#include <list>
#include <algorithm>void linked_list_bucket_sort(std::vector<float>& arr) {if (arr.empty()) return;// 桶数量int bucket_count = arr.size();std::vector<std::list<float>> buckets(bucket_count);// 分配数据到桶for (float num : arr) {int index = static_cast<int>(num * bucket_count);if (index >= bucket_count) index = bucket_count - 1;buckets[index].push_back(num);}// 对每个桶排序并合并结果int idx = 0;for (auto& bucket : buckets) {bucket.sort(); // 链表专用排序for (float num : bucket) {arr[idx++] = num;}}
}

优势：

降低内存分配频率，适合频繁插入的场景。
减少缓存未命中开销，提升写入效率。

4. 哈希表优化稀疏数据

核心思想：

当数据分布极稀疏时，用哈希表替代数组存储桶，仅记录非空桶。

实现方法（C++）：

#include <vector>
#include <map>
#include <algorithm>
#include <cmath>void sparse_bucket_sort(std::vector<float>& arr) {if (arr.empty()) return;// 计算数据范围float min_val = *std::min_element(arr.begin(), arr.end());float max_val = *std::max_element(arr.begin(), arr.end());float range = max_val - min_val;// 桶大小float bucket_size = range / arr.size() + 1e-5; // 避免除零// 哈希表存储桶std::map<int, std::vector<float>> bucket_map;// 分配数据到桶for (float num : arr) {int bucket_idx = static_cast<int>((num - min_val) / bucket_size);bucket_map[bucket_idx].push_back(num);}// 对每个桶排序并合并结果int idx = 0;for (auto& pair : bucket_map) {auto& bucket = pair.second;std::sort(bucket.begin(), bucket.end());for (float num : bucket) {arr[idx++] = num;}}
}

优势：

大幅减少内存占用，适合数据范围大但实际元素少的场景（如 ID 排序）。

5. 混合排序策略

核心思想：

对小规模桶使用插入排序，大规模桶使用快速排序，平衡时间复杂度与递归深度。

实现方法（C++）：

#include <vector>
#include <algorithm>// 插入排序
void insertion_sort(std::vector<float>& arr, int low, int high) {for (int i = low + 1; i <= high; i++) {float key = arr[i];int j = i - 1;while (j >= low && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}void hybrid_bucket_sort(std::vector<float>& arr) {if (arr.empty()) return;// 桶数量int bucket_count = arr.size();std::vector<std::vector<float>> buckets(bucket_count);// 分配数据到桶for (float num : arr) {int index = static_cast<int>(num * bucket_count);if (index >= bucket_count) index = bucket_count - 1;buckets[index].push_back(num);}// 对每个桶排序const int THRESHOLD = 15;for (auto& bucket : buckets) {if (bucket.size() < THRESHOLD) {insertion_sort(bucket, 0, bucket.size() - 1);} else {std::sort(bucket.begin(), bucket.end());}}// 合并结果int idx = 0;for (auto& bucket : buckets) {for (float num : bucket) {arr[idx++] = num;}}
}

优势：

结合两种算法的优势，提升小数据量下的效率。
减少递归调用栈的开销。

总结与选择建议

优化变体	核心改进点	适用场景
动态桶划分	根据数据分布调整桶范围	数据分布不均匀或包含负数
并行化排序	多线程加速桶内排序	超大规模数据或多核处理器环境
链表优化	减少动态扩容开销	频繁插入或内存分配受限的场景
哈希表优化	稀疏数据的内存压缩	数据范围大但元素种类稀疏（如ID、IP地址）
混合排序策略	小桶用插入排序，大桶用快速排序	混合规模数据，需平衡效率与递归深度

选择原则：

通用场景：优先动态桶划分 + 混合排序策略。
大数据量：结合并行化与哈希表优化。
内存敏感：使用链表或哈希表减少空间开销。

9. 基数排序（Radix Sort）

原理：按位数（LSB到MSB）依次排序，使用计数或桶排序。
稳定性：稳定
时间复杂度：O(dn)
适用场景：整数或字符串排序。

// 获取数组最大值
int getMax(int arr[], int n) {int max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max)max = arr[i];}return max;
}// 计数排序辅助函数（按指定位数）
void countingSortForRadix(int arr[], int n, int exp) {int output[n];int count[10] = {0}; // 10个桶（0-9）// 统计当前位的数字频率for (int i = 0; i < n; i++) {int index = (arr[i] / exp) % 10;count[index]++;}// 计算前缀和for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 逆序遍历原数组，保持稳定排序for (int i = n - 1; i >= 0; i--) {int index = (arr[i] / exp) % 10;output[--count[index]] = arr[i];}// 将结果复制回原数组memcpy(arr, output, sizeof(int) * n);
}// 基数排序主函数
void radixSort(int arr[], int n) {// 处理空数组或单元素数组if (n <= 1) return;// 分离正数和负数int posCount = 0, negCount = 0;for (int i = 0; i < n; i++) {if (arr[i] >= 0) posCount++;else negCount++;}int *posArr = malloc(posCount * sizeof(int));int *negArr = malloc(negCount * sizeof(int));posCount = 0;negCount = 0;for (int i = 0; i < n; i++) {if (arr[i] >= 0) {posArr[posCount++] = arr[i];} else {negArr[negCount++] = -arr[i]; // 负数取绝对值}}// 对正数部分进行基数排序if (posCount > 0) {int maxPos = getMax(posArr, posCount);int exp = 1;while (maxPos / exp > 0) {countingSortForRadix(posArr, posCount, exp);exp *= 10;}}// 对负数部分进行基数排序if (negCount > 0) {int maxNeg = getMax(negArr, negCount);int exp = 1;while (maxNeg / exp > 0) {countingSortForRadix(negArr, negCount, exp);exp *= 10;}}// 合并结果：负数逆序 + 正数int index = 0;for (int i = negCount - 1; i >= 0; i--) {arr[index++] = -negArr[i];}for (int i = 0; i < posCount; i++) {arr[index++] = posArr[i];}free(posArr);free(negArr);
}

以下是在基数排序文章中新增的C++代码实现，保持原文结构和内容不变：

一、基数选择优化

多基数混合使用

// 使用256作为基数（1字节）进行32位整数排序
void radix_sort_256(std::vector<uint32_t>& arr) {const int radix = 256; // 基数const int passes = 4;  // 32位整数需要4轮排序std::vector<uint32_t> temp(arr.size());for (int pass = 0; pass < passes; pass++) {std::vector<int> count(radix, 0);int shift = pass * 8; // 每轮移动8位// 统计频率for (uint32_t num : arr) {uint8_t digit = (num >> shift) & 0xFF;count[digit]++;}// 计算累积计数for (int i = 1; i < radix; i++) {count[i] += count[i - 1];}// 反向填充（保持稳定性）for (int i = arr.size() - 1; i >= 0; i--) {uint8_t digit = (arr[i] >> shift) & 0xFF;temp[--count[digit]] = arr[i];}arr = temp;}
}

高位优先（MSD）变体

// MSD基数排序（递归实现）
void msd_radix_sort(std::vector<std::string>& arr, int low, int high, int depth = 0) {if (high - low <= 1) return;const int radix = 256; // ASCII字符范围std::vector<std::string> temp(high - low);std::vector<int> count(radix + 1, 0); // 多一位用于结束符// 统计频率for (int i = low; i < high; i++) {char c = depth < arr[i].size() ? arr[i][depth] : 0;count[c + 1]++; // +1处理空字符}// 计算累积计数for (int i = 1; i <= radix; i++) {count[i] += count[i - 1];}// 分配元素for (int i = low; i < high; i++) {char c = depth < arr[i].size() ? arr[i][depth] : 0;temp[count[c]++] = arr[i];}// 写回原数组std::copy(temp.begin(), temp.end(), arr.begin() + low);// 递归处理子桶int start = low;for (int i = 0; i < radix; i++) {int end = low + count[i];if (end - start > 1) {msd_radix_sort(arr, start, end, depth + 1);}start = end;}
}

二、空间优化

原地（In-place）基数排序

// 原地基数排序（仅需O(1)额外空间）
void in_place_radix_sort(std::vector<uint32_t>& arr) {const int bits = 32; // 32位整数const int radix = 2; // 二进制基数for (int shift = 0; shift < bits; shift++) {int left = 0;int right = arr.size() - 1;while (left <= right) {// 当前位为0的元素放左侧if (((arr[left] >> shift) & 1) == 0) {left++;}// 当前位为1的元素放右侧else {std::swap(arr[left], arr[right--]);}}}
}

五、数据类型扩展

支持浮点数与有符号整数

// 浮点数基数排序（IEEE754转换）
void radix_sort_float(std::vector<float>& arr) {// 将浮点数转换为可排序的整数表示auto to_uint = [](float f) -> uint32_t {if (f < 0) {return ~std::bit_cast<uint32_t>(-f) + 1;}return std::bit_cast<uint32_t>(f) | 0x80000000;};// 排序转换后的整数std::vector<uint32_t> int_arr(arr.size());std::transform(arr.begin(), arr.end(), int_arr.begin(), to_uint);radix_sort_256(int_arr);// 转换回浮点数auto to_float = [](uint32_t u) -> float {if (u & 0x80000000) {return std::bit_cast<float>(u & ~0x80000000);}return -std::bit_cast<float>(~u + 1);};std::transform(int_arr.begin(), int_arr.end(), arr.begin(), to_float);
}

六、稳定性保障

稳定排序机制

// 稳定的LSD基数排序
void stable_radix_sort(std::vector<uint32_t>& arr) {const int radix = 10; // 十进制基数std::vector<uint32_t> output(arr.size());for (int exp = 1; ; exp *= radix) {std::vector<int> count(radix, 0);bool max_reached = true;// 统计频率for (uint32_t num : arr) {int digit = (num / exp) % radix;count[digit]++;if (num / exp >= radix) max_reached = false;}if (max_reached && exp > 1) break;// 计算累积计数for (int i = 1; i < radix; i++) {count[i] += count[i - 1];}// 反向填充（关键稳定性步骤）for (int i = arr.size() - 1; i >= 0; i--) {int digit = (arr[i] / exp) % radix;output[--count[digit]] = arr[i];}arr = output;}
}

特殊场景算法

字符串专用排序（如MSD/LSD Radix）

MSD（最高位优先）基数排序

#include <vector>
#include <string>
#include <algorithm>// MSD基数排序实现
void msd_radix_sort(std::vector<std::string>& arr, int low, int high, int depth = 0) {// 递归终止条件：子数组大小<=1if (high - low <= 1) return;// 1. 创建桶（ASCII范围0-255）const int radix = 256;std::vector<std::vector<std::string>> buckets(radix);// 2. 分配字符串到桶（基于当前深度字符）for (int i = low; i < high; i++) {char c = (depth < arr[i].size()) ? arr[i][depth] : 0;buckets[static_cast<unsigned char>(c)].push_back(arr[i]);}// 3. 收集桶并递归处理int idx = low;for (auto& bucket : buckets) {int bucket_size = bucket.size();if (bucket_size > 0) {// 收集当前桶for (const auto& s : bucket) {arr[idx++] = s;}// 递归处理下一层msd_radix_sort(arr, idx - bucket_size, idx, depth + 1);}}
}// 封装函数
void msd_sort(std::vector<std::string>& arr) {msd_radix_sort(arr, 0, arr.size());
}

LSD（最低位优先）基数排序

#include <vector>
#include <string>
#include <algorithm>// LSD基数排序实现
void lsd_radix_sort(std::vector<std::string>& arr) {if (arr.empty()) return;// 1. 找到最大字符串长度size_t max_len = 0;for (const auto& s : arr) {if (s.size() > max_len) max_len = s.size();}// 2. 从最低位（最右侧字符）开始排序for (int pos = static_cast<int>(max_len) - 1; pos >= 0; pos--) {const int radix = 256; // ASCII范围std::vector<std::string> output(arr.size());std::vector<int> count(radix, 0);// 3. 统计频率for (const auto& s : arr) {char c = (pos < s.size()) ? s[pos] : 0;count[static_cast<unsigned char>(c)]++;}// 4. 计算累积计数for (int i = 1; i < radix; i++) {count[i] += count[i - 1];}// 5. 反向填充（保持稳定性）for (int i = static_cast<int>(arr.size()) - 1; i >= 0; i--) {char c = (pos < arr[i].size()) ? arr[i][pos] : 0;output[--count[static_cast<unsigned char>(c)]] = arr[i];}// 6. 更新数组arr = output;}
}

性能优化：多基数处理

// 使用16位基数（2字节）加速排序
void fast_lsd_sort(std::vector<std::string>& arr) {if (arr.empty()) return;// 1. 找到最大字符串长度size_t max_len = 0;for (const auto& s : arr) {if (s.size() > max_len) max_len = s.size();}// 2. 每轮处理2个字符（16位）for (int pos = static_cast<int>(max_len) - 2; pos >= -1; pos -= 2) {const int radix = 65536; // 16位基数std::vector<std::string> output(arr.size());std::vector<int> count(radix, 0);// 3. 统计频率（组合两个字符）for (const auto& s : arr) {unsigned key = 0;if (pos >= 0) {key |= (static_cast<unsigned char>(s[pos]) << 8);if (pos + 1 < s.size()) {key |= static_cast<unsigned char>(s[pos + 1]);}} else if (pos == -1 && s.size() > 0) {key = static_cast<unsigned char>(s[0]);}count[key]++;}// 4. 计算累积计数for (int i = 1; i < radix; i++) {count[i] += count[i - 1];}// 5. 反向填充for (int i = static_cast<int>(arr.size()) - 1; i >= 0; i--) {unsigned key = 0;const auto& s = arr[i];if (pos >= 0) {key |= (static_cast<unsigned char>(s[pos]) << 8);if (pos + 1 < s.size()) {key |= static_cast<unsigned char>(s[pos + 1]);}} else if (pos == -1 && s.size() > 0) {key = static_cast<unsigned char>(s[0]);}output[--count[key]] = s;}// 6. 更新数组arr = output;}
}

惰性排序（Lazy Sorting）**

策略：延迟排序操作，仅在需要时执行，不再提供代码。

总结与分类

类别	代表性算法
稳定排序	冒泡、插入、归并、计数、桶、基数、原地归并
不稳定排序	选择、快速、堆、希尔、三数取中快排、双路快排
线性时间排序	计数、桶、基数
分治法排序	归并、快速、希尔（间接分治）
原地排序	冒泡、选择、插入、堆、原地归并