【C++学习】十大经典排序算法全解析：原理、代码与性能对比

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、冒泡排序（Bubble Sort）
• • 1.算法描述
  • 2.核心思想
  • 3.动图演示
  • 4.C++实现：
  • 5.算法优化
  • 6. 算法分析
• 二、选择排序（Selection Sort）
• • 1.算法描述
  • 2.核心思想
  • 3.动图演示
  • 4.C++实现：
  • 5. 算法优化
  • 6. 算法分析
• 三、插入排序（Insertion Sort）
• • 1.算法描述
  • 2.核心思想
  • 3.动图演示
  • 4.C++实现：
  • 5. 算法分析
• 四、希尔排序（Shell Sort）
• • 1.算法描述
  • 2.核心思想
  • 3.动图演示
  • 4.C++实现：
  • 5. 算法优化
  • 6. 算法分析
• 五、归并排序（Merge Sort）
• • 1.算法描述
  • 2.核心思想
  • 3.动图演示
  • 4.C++实现：
  • 5.算法优化
  • 6. 算法分析
• 六、快速排序（Quick Sort）
• • 1.算法描述
  • 2.核心思想
  • 3.动图演示
  • 4.C++实现：
  • 5.算法优化
  • 6. 算法分析
• 七、堆排序（Heap Sort）
• • 1.算法描述
  • 2.核心思想
  • 3.动图演示
  • 4.C++实现：
  • 5. 算法分析
• 八、计数排序（Counting Sort）
• • 1.算法描述
  • 2.核心思想
  • 3.动图演示
  • 4.C++实现：
  • 5. 算法分析
• 九、基数排序（Radix Sort）
• • 1.算法描述
  • 2.核心思想
  • 3.动图演示
  • 4.C++实现：
  • 5. 算法分析
• 十、桶排序（Bucket Sort）
• • 1.算法描述
  • 2.核心思想
  • 3.动图演示
  • 4.C++实现：
  • 5. 算法分析
• 通用准备工作
• 测试所有排序算法
• 总结

前言

排序算法是编程入门的核心知识点，也是面试、笔试中的高频考点。本文将系统讲解十种经典排序算法的核心原理，提供可直接运行的 C++ 实现代码，并分析每种算法的时间 / 空间复杂度、稳定性，帮助你彻底掌握排序算法。

一、冒泡排序（Bubble Sort）

1.算法描述

冒泡排序是一种简单的交换类比较排序算法，也是入门级的排序算法。它的核心过程如同气泡从水底逐步上浮到水面，每一轮遍历都会将当前未排序部分的最大元素 “浮” 到末尾，因此得名 “冒泡” 排序。

2.核心思想

• 将待排序数组划分为 “未排序区间” 和 “已排序区间”（初始时已排序区间为空，未排序区间为整个数组）；
• 重复遍历未排序区间，依次比较相邻的两个元素：
  • 若升序排序：如果前一个元素 > 后一个元素，交换两者位置；
  • 若降序排序：如果前一个元素 < 后一个元素，交换两者位置；
• 每完成一轮遍历，未排序区间的最大（升序）/ 最小（降序） 元素会被 “冒泡” 到未排序区间的末尾，成为已排序区间的新起点；
• 当某一轮遍历中没有发生任何交换时，说明数组已完全有序，可提前终止算法（优化点）。

3.动图演示

4.C++实现：

// 冒泡排序
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
// 外层循环：控制排序轮数
for (int i = 0; i < n – 1; ++i) {
// 内层循环：每轮比较相邻元素，已排序的末尾无需再比较
for (int j = 0; j < n – 1 – i; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}

5.算法优化

默认的冒泡排序会固定遍历 n-1 轮（n 为数组长度），但可以通过一个 “交换标记” 优化：

• 每轮遍历前初始化标记 swapped = false；
• 若本轮发生元素交换，将标记置为 true；
• 遍历结束后检查标记：若 swapped= false，说明数组已完全有序，直接终止算法，避免后续无效遍历。

// 冒泡排序优化
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
// 外层循环：控制排序轮数
for (int i = 0; i < n – 1; ++i) {
bool swapped = false; // 优化：标记是否发生交换，提前终止
// 内层循环：每轮比较相邻元素，已排序的末尾无需再比较
for (int j = 0; j < n – 1 – i; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 没有交换，说明数组已排序完成
}
}

6. 算法分析

• 时间复杂度：最好 O(n)（已排序）、最坏 O(n*n)、平均 O(n*n)
• 空间复杂度：O(1)
• 稳定性：稳定（相等元素不交换）

二、选择排序（Selection Sort）

1.算法描述

选择排序是一种简单的选择类比较排序算法，核心是 “选择”—— 每一轮从未排序区间中精准选出最小（升序）或最大（降序）的元素，将其放到已排序区间的末尾，通过逐轮 “选择 + 交换” 完成整体排序，是入门级排序算法的重要代表。

2.核心思想

• 将待排序数组明确划分为 “已排序区间”（初始为空）和 “未排序区间”（初始为整个数组）；
• 重复遍历未排序区间，从中找出最小（升序）或最大（降序）的元素，记录该元素的索引（而非直接交换）；
• 将找到的最小 / 最大元素与未排序区间的第一个元素交换位置，此时该元素正式归入已排序区间；
• 缩小未排序区间的范围（起始位置后移一位），重复上述步骤，直到未排序区间为空。

3.动图演示

4.C++实现：

// 选择排序
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
// 外层循环：确定已排序区的末尾位置
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;
}
}
// 交换最小元素到已排序区末尾
std::swap(arr[i], arr[minIndex]);
}
}

5. 算法优化

选择排序的基础版本逻辑简单，优化空间有限，常见实用优化方向：

• 双极值选择：每一轮遍历未排序区间时，同时找出最小值和最大值，分别放到已排序区间的末尾和开头，将遍历轮数从 n − 1减少到 ⌈n/2⌉，提升大规模数据的排序效率；

6. 算法分析

• 时间复杂度：最好 / 最坏 / 平均 O(n*n)（无论是否有序，都要遍历找极值）
• 空间复杂度：O(1)
• 稳定性：不稳定（交换操作会破坏相等元素的相对位置，例如数组 [2, 2, 1]，第一次交换会破坏相等元素的相对位置）

三、插入排序（Insertion Sort）

1.算法描述

插入排序是一种简单的插入类比较排序算法，其核心逻辑模仿日常整理扑克牌的行为 —— 将未排序的元素逐个 “插入” 到已排序区间的合适位置，是入门级排序算法中对 “几乎有序数据集” 性能最优的算法。

2.核心思想

• 将待排序数组明确划分为 “已排序区间”（初始时仅包含第一个元素）和 “未排序区间”（剩余所有元素）；
• 依次取出未排序区间的第一个元素作为 “待插入元素”，暂存该元素避免被覆盖；
• 从已排序区间的末尾向前遍历，将比待插入元素大（升序排序）的元素向后移动一位，为待插入元素腾出空间；
• 当找到小于 / 等于待插入元素的位置（或遍历到已排序区间开头），将待插入元素放入腾出的空位，完成一次插入；
• 扩大已排序区间的范围，重复上述步骤，直到未排序区间为空。

3.动图演示

4.C++实现：

// 插入排序
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
// 从第二个元素开始（第一个元素默认已排序）
for (int i = 1; i < n; ++i) {
int key = arr[i]; // 待插入的元素
int j = i – 1; // 已排序区的最后一个元素索引

// 把比key大的元素后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j—;
}
// 插入key到正确位置
arr[j + 1] = key;
}
}

5. 算法分析

• 时间复杂度：最好 O(n)（已排序）、最坏 O(n*n)、平均 O(n*n)
• 空间复杂度：O(1)
• 稳定性：稳定

四、希尔排序（Shell Sort）

1.算法描述

希尔排序（也称为 “缩小增量排序”）是插入排序的高效改进版本，核心思路是通过 “分组预排序” 减少数组的逆序度，解决普通插入排序对逆序元素移动次数多、效率低的问题。它通过逐步缩小的 “步长” 将数组分组，对每组执行插入排序，最终当步长为 1 时，数组已基本有序，再用一次普通插入排序完成最终排序。

2.核心思想

• 选择一个递减的步长序列（如初始步长 gap = n/2，后续逐步缩小为 gap/2，直到 gap = 1）；
• 对于当前步长 gap，将数组划分为 gap 个独立的子数组（索引相差 gap 的元素归为一组，例如 gap=3 时，索引 0/3/6、1/4/7、2/5/8 分别为一组）；
• 对每个子数组单独执行插入排序（分组预排序），使每组内元素有序，整体降低数组的逆序度；
• 逐步缩小步长（如 gap = gap/2），重复 “分组 + 插入排序” 的过程，数组会越来越接近有序；
• 当步长 gap = 1 时，数组已基本有序，此时执行一次普通插入排序（此时插入排序的时间复杂度接近 O(n)），完成最终排序。

3.动图演示

4.C++实现：

// 希尔排序
void shellSort(std::vector<int>& arr) {
int n = arr.size();
// 逐步缩小步长
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个步长组进行插入排序
for (int i = gap; i < n; ++i) {
int key = arr[i];
int j = i;
// 组内插入排序
while (j >= gap && arr[j – gap] > key) {
arr[j] = arr[j – gap];
j -= gap;
}
arr[j] = key;
}
}
}

5. 算法优化

希尔排序的性能核心取决于步长序列的选择，基础的 “n/2 递减” 步长并非最优，常见的优化步长序列如下：

• Knuth 序列：步长公式为 gap=gap∗3+1初始 gap=1，反向推导得到排序用的步长序列，如 1,4,13,40…），能显著降低时间复杂度，是最常用的优化步长；
• Sedgewick 序列：步长由 9 ∗ 4^i − 9 ∗ 2^i + 1 和 4^i − 3 ∗ 2^i + 1组合生成（如 1,5,19,41,109…）;
• Hibbard 序列：步长为 2^k−1（如 1,3,7,15…），避免了基础步长中 “偶数步长与前序步长倍数重叠” 的问题。

6. 算法分析

• 时间复杂度：最好 O(n)（已排序）、最坏 O(n*n)、平均 O(n^1.3)
• 空间复杂度：O(1)
• 稳定性：不稳定

五、归并排序（Merge Sort）

1.算法描述

归并排序是一种基于分治思想的比较排序算法，也是首个时间复杂度达到 O(n*logn)的经典排序算法。其核心逻辑是 “先分后合”：将待排序数组递归拆分为更小的子数组，直到子数组长度为 1（天然有序）；再将两个有序子数组逐步 “合并” 为一个有序数组，最终通过层层合并得到完整的有序数组。

2.核心思想

• 分（Divide）：采用递归策略，将当前数组从中间拆分为左右两个子数组，重复拆分过程，直到每个子数组仅包含 1 个元素（单个元素本身就是有序的）；
• 治（Conquer）：递归处理每个子数组，本质是完成子数组的拆分与底层有序子数组的初始化；
• 合（Merge）：这是算法的核心步骤 —— 将两个相邻的有序子数组合并为一个新的有序数组。合并时通过双指针遍历两个子数组，依次选取较小（升序）的元素放入结果数组，最终将合并后的有序数组覆盖原数组对应区间。

3.动图演示

4.C++实现：

// 合并两个有序子数组
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid – left + 1;
int n2 = right – mid;

// 临时数组存储两个子数组
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];

// 合并临时数组到原数组
int 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++];
}
}

// 归并排序（递归）
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left >= right) return; // 递归终止条件
int mid = left + (right – left) / 2; // 避免溢出
mergeSort(arr, left, mid); // 左半部分排序
mergeSort(arr, mid + 1, right); // 右半部分排序
merge(arr, left, mid, right); // 合并
}

// 对外接口（简化调用）
void mergeSort(std::vector<int>& arr) {
mergeSort(arr, 0, arr.size() – 1);
}

5.算法优化

• 提前终止合并：合并前判断左子数组的最后一个元素 ≤ 右子数组的第一个元素，若成立则两个子数组已天然有序，无需执行合并操作；

6. 算法分析

• 时间复杂度：最好 / 最坏 / 平均 O(n*logn)（递归拆分是 logn层，每层合并是 n）
• 空间复杂度：O(n)（需要临时数组存储子数组）
• 稳定性：稳定

六、快速排序（Quick Sort）

1.算法描述

快速排序是一种基于分治思想的原地比较排序算法，也是实际工程中应用最广泛的高效排序算法（被冠以 “快速” 之名，正是因为其平均情况下的执行效率远超同级别 O(n*logn)算法）。其核心逻辑是 “分而不治、就地分区”：通过选择一个 “基准值（pivot）” 将数组划分为左右两部分（左部分≤基准值、右部分≥基准值），递归处理左右子数组，最终通过分区的收敛性实现整体有序（无需归并排序的 “合并” 步骤）。

2.核心思想

• 选基准（Pivot）：从待排序数组中选择一个元素作为基准值，基准值的选择直接决定算法的性能（核心优化点）；
• 分区（Partition）：遍历数组，将小于等于基准值的元素移到基准值左侧，大于等于基准值的元素移到右侧，最终基准值会被放到 “排序后的正确位置”；
• 递归处理：对基准值左侧和右侧的子数组重复执行 “选基准 + 分区” 操作，直到子数组长度≤1（单个元素天然有序，递归终止）；
• 整个过程无需额外的合并步骤，分区完成后子数组的有序性会自然收敛到整个数组有序。

3.动图演示

4.C++实现：

// 划分函数：返回基准值的最终位置
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 选最后一个元素作为基准
int i = low – 1; // 小于基准区的最后一个元素索引

for (int j = low; j < high; ++j) {
if (arr[j] <= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
// 把基准值放到正确位置
std::swap(arr[i + 1], arr[high]);
return i + 1;
}

// 快速排序（递归）
void quickSort(std::vector<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); // 右半部分排序
}
}

// 对外接口
void quickSort(std::vector<int>& arr) {
quickSort(arr, 0, arr.size() – 1);
}

5.算法优化

• 基准值优化（核心）：
  • 三数取中法：选择数组左、中、右三个位置的中位数作为基准值，避免已排序 / 逆序数组导致的最坏情况；
  • 随机选基准：随机选取数组中的元素作为基准值，将最坏情况的概率降至极低；
  • 大数组用三数取中，小数组用固定基准，兼顾性能与效率。
• 三路快排优化：将数组分为 “≤pivot、=pivot、≥pivot” 三部分，解决大量重复元素时普通快排退化为 O(n*n)的问题；

6. 算法分析

• 时间复杂度：最好 / 平均 O(n*logn)、最坏 O(n*n)（已排序数组，基准选最后一个）
• 空间复杂度：O(logn)（递归栈空间）
• 稳定性：不稳定

七、堆排序（Heap Sort）

1.算法描述

堆排序是一种基于堆数据结构的选择类比较排序算法，也是少数能同时实现 “原地排序 + 稳定 O (n*logn) 时间复杂度” 的经典算法。其核心逻辑是利用 “大顶堆（升序）/ 小顶堆（降序）” 的特性（堆顶元素为极值），通过 “构建初始堆→提取极值→调整堆” 的循环，将极值逐个 “提取” 到数组末尾，最终实现整体有序。

2.核心思想

在正式排序前，需先明确堆的基础概念：堆是完全二叉树结构，满足 “大顶堆”（每个父节点≥子节点）或 “小顶堆”（每个父节点≤子节点）的性质；数组可直接映射为完全二叉树（索引 i 的左子节点 = 2i + 1，右子节点 = 2i + 2，父节点 =(i – 1) / 2）。 堆排序（升序）的核心步骤：

• 构建初始大顶堆：从最后一个非叶子节点开始，向前遍历并调整每个节点的位置，使整个数组满足大顶堆性质（堆顶为最大值）；
• 提取堆顶极值：交换堆顶元素（最大值）和当前堆的最后一个元素，此时最大值被 “固定” 到数组末尾（已排序区间）；
• 调整剩余堆：将交换后的剩余元素（未排序区间）重新调整为大顶堆（仅需调整堆顶节点，因为其余节点仍满足堆性质）；
• 重复 “提取极值 + 调整堆” 的过程，直到堆的大小缩减为 1（所有元素已排序）。

3.动图演示

4.C++实现：

// 调整堆（大顶堆）
void heapify(std::vector<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) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}

// 堆排序
void heapSort(std::vector<int>& arr) {
int n = arr.size();

// 构建大顶堆（从最后一个非叶子节点开始）
for (int i = n / 2 – 1; i >= 0; —i) {
heapify(arr, n, i);
}

// 逐个取出堆顶元素
for (int i = n – 1; i > 0; —i) {
std::swap(arr[0], arr[i]); // 交换根节点和最后一个元素
heapify(arr, i, 0); // 调整剩余元素为大顶堆
}
}

5. 算法分析

• 时间复杂度：最好 / 最坏 / 平均 O(nlogn)（构建堆 O(n)，n-1 次调整堆每次 O(logn)，总复杂度为 O(n + nlogn) = O (n*logn)）；
• 空间复杂度：迭代版：O(1) 递归版：O(logn)（递归栈空间）；
• 稳定性：不稳定

八、计数排序（Counting Sort）

1.算法描述

计数排序是一种非比较类的线性时间排序算法，也是入门级的 “基于统计” 的排序算法。其核心逻辑并非通过元素间的比较实现排序，而是通过统计数组中每个元素的出现次数，再根据元素值的大小顺序重新填充数组 —— 完全避开比较操作，因此能突破比较类排序 O(n*logn)的时间复杂度下限，达到线性时间复杂度。

2.核心思想

计数排序的前提是：待排序元素为整数，且元素值的范围（记为 k）远小于数组长度 n（否则空间开销过大）。升序排序的核心步骤：

• 确定值域范围：遍历数组找到最小值 minVal 和最大值 maxVal，计算值域范围 range = maxVal – minVal + 1（用于确定计数数组的长度）；
• 统计元素频次：创建长度为 range 的计数数组 count，遍历原数组，统计每个元素出现的次数（元素 num 对应计数数组的索引为 num – minVal，避免负数索引）；
• 计算前缀和：对计数数组做前缀和处理，此时 count[i] 表示 “小于等于 minVal + i 的元素总数”，该值可直接确定对应元素在有序数组中的最终位置；
• 反向填充结果：从原数组的末尾向前遍历（保证排序稳定性），根据前缀和数组找到当前元素的目标位置，放入结果数组后更新前缀和（避免重复元素位置冲突）；
• 拷贝结果：将有序的结果数组拷贝回原数组，完成排序。

3.动图演示

4.C++实现：

// 计数排序
void countingSort(std::vector<int>& arr) {
if (arr.empty()) return;

// 找数组的最大值和最小值
int maxVal = *max_element(arr.begin(), arr.end());
int minVal = *min_element(arr.begin(), arr.end());
int range = maxVal – minVal + 1;

// 计数数组和结果数组
std::vector<int> count(range, 0), output(arr.size());

// 统计每个元素出现次数
for (int num : arr) {
count[num – minVal]++;
}

// 计算前缀和（确定元素的最终位置）
for (int i = 1; i < range; ++i) {
count[i] += count[i – 1];
}

// 构建输出数组（从后往前，保证稳定性）
for (int i = arr.size() – 1; i >= 0; —i) {
output[count[arr[i] – minVal] – 1] = arr[i];
count[arr[i] – minVal]—;
}

// 复制回原数组
arr = output;
}

5. 算法分析

• 时间复杂度：最好 / 最坏 / 平均 O(n + k)（k 是元素值范围）
• 空间复杂度：O(n + k)
• 稳定性：稳定（反向填充结果数组时，相等元素的相对顺序与原数组一致）；

九、基数排序（Radix Sort）

1.算法描述

基数排序是一种非比较类的线性时间排序算法，也是桶排序的高效变种。其核心逻辑并非直接比较元素大小，而是将元素按 “位” 拆分（如十进制数的个位、十位、百位），对每一位依次执行稳定排序（通常用计数排序 / 桶排序）—— 从最低位到最高位（或反之）完成所有位的排序后，数组会自然整体有序。该算法完全避开比较操作，突破了比较类排序 O(n*logn) 的时间复杂度下限。

2.核心思想

基数排序的前提是：待排序元素可按 “位” 拆分（如整数、固定长度字符串），且每一位的取值范围有限（即 “基数”，十进制基数为 10，二进制为 2）。主流的低位优先（LSD） 升序排序核心步骤：

• 确定排序参数：遍历数组找到最大值，计算其位数（即需要排序的总轮数 maxDigit）；确定基数 radix（如十进制取 10）；
• 按位分桶 / 计数：从最低位（个位）到最高位依次遍历每一位：
• 对当前位执行稳定排序（常用计数排序，也可用桶排序）：
  • 统计当前位上每个数字（0~radix-1）的出现频次；
  • 计算前缀和确定每个数字在结果数组中的位置；
  • 反向遍历原数组，按当前位数字将元素放入结果数组（保证稳定性）；
• 将结果数组拷贝回原数组，完成当前位的排序；
• 所有位排序完成后，数组整体有序。

3.动图演示

4.C++实现：

// 获取数字的指定位数（个位=1，十位=2…）
int getDigit(int num, int digit) {
return (num / (int)pow(10, digit – 1)) % 10;
}

// 基数排序（按十进制位排序）
void radixSort(std::vector<int>& arr) {
if (arr.empty()) return;

// 找最大值，确定需要排序的位数
int maxVal = *max_element(arr.begin(), arr.end());
int maxDigit = 0;
while (maxVal > 0) {
maxVal /= 10;
maxDigit++;
}

// 按每一位排序（从个位到最高位）
for (int d = 1; d <= maxDigit; ++d) {
// 10个桶（0-9）
std::vector<std::vector<int>> buckets(10);

// 按当前位放入桶中
for (int num : arr) {
int digit = getDigit(num, d);
buckets[digit].push_back(num);
}

// 合并桶到原数组
int idx = 0;
for (auto& bucket : buckets) {
for (int num : bucket) {
arr[idx++] = num;
}
bucket.clear();
}
}
}

5. 算法分析

• 时间复杂度：O(d*(n+k))（d是位数，k是基数，十进制 k=10）
• 空间复杂度：O(n + k)
• 稳定性：稳定

十、桶排序（Bucket Sort）

1.算法描述

桶排序是一种基于分治和值域映射的非比较类线性时间排序算法，也是计数排序、基数排序的通用扩展形式。其核心逻辑是将待排序元素按预设的 “值域区间” 映射到多个独立的 “桶” 中，对每个桶内的元素执行稳定排序（通常用插入排序），最后按桶的顺序合并所有桶内的元素 —— 通过 “分桶降维” 将大规模排序拆解为小规模排序，从而实现高效的线性时间排序。

2.核心思想

桶排序的前提是：待排序元素均匀分布在某个连续值域范围内（如 0~100 的整数、0~1 的浮点数）。升序排序的核心步骤：

• 确定桶的参数：遍历数组找到最小值 minVal 和最大值 maxVal，根据数据分布选择桶的数量 bucketCount（通常取数组长度的平方根或固定值），计算每个桶的区间大小 interval = (maxVal – minVal + 1) / bucketCount；
• 元素分桶：创建 bucketCount 个空桶，遍历原数组，将每个元素根据值域映射到对应的桶中（映射公式：桶索引 = (num – minVal) / interval）；
• 桶内排序：对每个非空桶内的元素执行稳定排序（小规模数据优先选插入排序，大规模可选快速排序）；
• 合并桶：按桶的索引顺序，将所有桶内的元素依次拷贝回原数组，完成整体排序。

3.动图演示

4.C++实现：

// 桶排序
void bucketSort(std::vector<int>& arr) {
if (arr.empty()) return;

// 找最大值和最小值
int maxVal = *max_element(arr.begin(), arr.end());
int minVal = *min_element(arr.begin(), arr.end());

// 桶的数量（可根据实际情况调整）
int bucketCount = 5;
std::vector<std::vector<int>> buckets(bucketCount);

// 计算每个桶的区间大小
double interval = (double)(maxVal – minVal + 1) / bucketCount;

// 将元素分配到桶中
for (int num : arr) {
int index = (num – minVal) / interval;
buckets[index].push_back(num);
}

// 对每个桶排序，然后合并
int idx = 0;
for (auto& bucket : buckets) {
insertionSort(bucket); // 桶内用插入排序
for (int num : bucket) {
arr[idx++] = num;
}
}
}

5. 算法分析

• 时间复杂度：最好 / 平均 O(n+k)、最坏 O(n*n)所有元素进一个桶）
• 空间复杂度：O(n + k)
• 稳定性：稳定（取决于桶内排序算法）

通用准备工作

为了方便测试和展示排序效果，我们先定义两个通用函数：打印数组、生成随机数组。所有排序算法都会基于这两个函数进行测试。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>

// 打印数组
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}

// 生成随机数组
std::vector<int> generateRandomArray(int size, int min = 0, int max = 100) {
std::vector<int> arr(size);
srand(time(0)); // 设置随机种子
for (int i = 0; i < size; ++i) {
arr[i] = rand() % (max – min + 1) + min;
}
return arr;
}

测试所有排序算法

int main() {
// 生成测试数组
std::vector<int> arr = generateRandomArray(10, 0, 100);
std::cout << "原始数组：";
printArray(arr);

// 测试每种排序算法（每次测试前复制原始数组）
std::vector<int> arrCopy;

arrCopy = arr;
bubbleSort(arrCopy);
std::cout << "冒泡排序后：";
printArray(arrCopy);

arrCopy = arr;
selectionSort(arrCopy);
std::cout << "选择排序后：";
printArray(arrCopy);

arrCopy = arr;
insertionSort(arrCopy);
std::cout << "插入排序后：";
printArray(arrCopy);

arrCopy = arr;
shellSort(arrCopy);
std::cout << "希尔排序后：";
printArray(arrCopy);

arrCopy = arr;
mergeSort(arrCopy);
std::cout << "归并排序后：";
printArray(arrCopy);

arrCopy = arr;
quickSort(arrCopy);
std::cout << "快速排序后：";
printArray(arrCopy);

arrCopy = arr;
heapSort(arrCopy);
std::cout << "堆排序后：";
printArray(arrCopy);

arrCopy = arr;
countingSort(arrCopy);
std::cout << "计数排序后：";
printArray(arrCopy);

arrCopy = arr;
radixSort(arrCopy);
std::cout << "基数排序后：";
printArray(arrCopy);

arrCopy = arr;
bucketSort(arrCopy);
std::cout << "桶排序后：";
printArray(arrCopy);

return 0;
}

总结