id="_4">前言

排序算法是编程入门的核心知识点，也是面试、笔试中的高频考点。

本文将系统讲解十种经典排序算法的核心原理，提供可直接运行的

C++

id="1_7">1.算法描述

冒泡排序是一种简单的交换类比较排序算法，也是入门级的排序算法。

它的核心过程如同气泡从水底逐步上浮到水面，每一轮遍历都会将当前未排序部分的最大元素

“浮”

id="2_9">2.核心思想

• 将待排序数组划分为

  “未排序区间”

  “已排序区间”（初始时已排序区间为空，未排序区间为整个数组）；

• 重复遍历未排序区间，依次比较相邻的两个元素：

  >

  后一个元素，交换两者位置；

• 若降序排序：如果前一个元素

  <

  后一个元素，交换两者位置；

3.动图演示

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/86dc3e8193194058aa73a0aa403e7165.gif#pic_center">

function">bubbleSort

class="token

punctuation">::vector

class="token

内层循环：每轮比较相邻元素，已排序的末尾无需再比较

class="token

punctuation">}

id="5_34">5.算法优化

默认的冒泡排序会固定遍历

n-1

false，说明数组已完全有序，直接终止算法，避免后续无效遍历。

function">bubbleSort

class="token

punctuation">::vector

class="token

内层循环：每轮比较相邻元素，已排序的末尾无需再比较

class="token

punctuation">}

6.

O(n*n)

空间复杂度：O(1)

稳定性：稳定（相等元素不交换）

id="Selection_Sort_61">二、选择排序（Selection

Sort）

id="1_62">1.算法描述

选择排序是一种简单的选择类比较排序算法，核心是

“选择”——

每一轮从未排序区间中精准选出最小（升序）或最大（降序）的元素，将其放到已排序区间的末尾，通过逐轮

“选择

2.核心思想

• 将待排序数组明确划分为

  “已排序区间”（初始为空）和

  “未排序区间”（初始为整个数组）；

• 重复遍历未排序区间，从中找出最小（升序）或最大（降序）的元素，记录该元素的索引（而非直接交换）；
• 将找到的最小

  最大元素与未排序区间的第一个元素交换位置，此时该元素正式归入已排序区间；

• 缩小未排序区间的范围（起始位置后移一位），重复上述步骤，直到未排序区间为空。

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/aca4083df137479896bc67a6efa2482f.gif#pic_center">

function">selectionSort

class="token

punctuation">::vector

class="token

punctuation">[minIndex

class="token

punctuation">[minIndex

class="token

punctuation">}

算法优化

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

• 双极值选择：每一轮遍历未排序区间时，同时找出最小值和最大值，分别放到已排序区间的末尾和开头，将遍历轮数从

  1减少到

  ⌈n/2⌉，提升大规模数据的排序效率；

6.

O(n*n)（无论是否有序，都要遍历找极值）

空间复杂度：O(1)

稳定性：不稳定（交换操作会破坏相等元素的相对位置，例如数组

[2,

1]，第一次交换会破坏相等元素的相对位置）

id="Insertion_Sort_97">三、插入排序（Insertion

Sort）

id="1_98">1.算法描述

插入排序是一种简单的插入类比较排序算法，其核心逻辑模仿日常整理扑克牌的行为

“插入”

• 将待排序数组明确划分为

  “未排序区间”（剩余所有元素）；

• 依次取出未排序区间的第一个元素作为

  “待插入元素”，暂存该元素避免被覆盖；

• 从已排序区间的末尾向前遍历，将比待插入元素大（升序排序）的元素向后移动一位，为待插入元素腾出空间；
• 当找到小于

  等于待插入元素的位置（或遍历到已排序区间开头），将待插入元素放入腾出的空位，完成一次插入；

• 扩大已排序区间的范围，重复上述步骤，直到未排序区间为空。

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/76d6bce657ef464b9672e253168d229a.gif#pic_center">

function">insertionSort

class="token

punctuation">::vector

class="token

从第二个元素开始（第一个元素默认已排序）

class="token

punctuation">}

5.

O(n*n)

空间复杂度：O(1)

稳定性：稳定

id="Shell_Sort_132">四、希尔排序（Shell

Sort）

id="1_133">1.算法描述

希尔排序（也称为

“缩小增量排序”）是插入排序的高效改进版本，核心思路是通过

“分组预排序”

减少数组的逆序度，解决普通插入排序对逆序元素移动次数多、效率低的问题。

它通过逐步缩小的

“步长”

• 选择一个递减的步长序列（如初始步长

  gap

  分别为一组）；

• 对每个子数组单独执行插入排序（分组预排序），使每组内元素有序，整体降低数组的逆序度；
• 逐步缩小步长（如

  gap

  时，数组已基本有序，此时执行一次普通插入排序（此时插入排序的时间复杂度接近

  alt="在这里插入图片描述"

  src="https://i-blog.csdnimg.cn/direct/092ed47b43444aa4a8ce7eda8e0cdc24.gif#pic_center">

  function">shellSort

  class="token

  punctuation">::vector

  class="token

  punctuation">}

  算法优化

  希尔排序的性能核心取决于步长序列的选择，基础的

  “n/2

  1,4,13,40…），能显著降低时间复杂度，是最常用的优化步长；

• Sedgewick

  序列：步长由

  1,5,19,41,109…）;

• Hibbard

  序列：步长为

  O(n^1.3)

• 空间复杂度：O(1)
• 稳定性：不稳定

id="Merge_Sort_173">五、归并排序（Merge

Sort）

id="1_174">1.算法描述

归并排序是一种基于分治思想的比较排序算法，也是首个时间复杂度达到

“先分后合”：将待排序数组递归拆分为更小的子数组，直到子数组长度为

1（天然有序）；再将两个有序子数组逐步

• 分（Divide）：采用递归策略，将当前数组从中间拆分为左右两个子数组，重复拆分过程，直到每个子数组仅包含

  个元素（单个元素本身就是有序的）；

• 治（Conquer）：递归处理每个子数组，本质是完成子数组的拆分与底层有序子数组的初始化；
• 合（Merge）：这是算法的核心步骤

  将两个相邻的有序子数组合并为一个新的有序数组。

  合并时通过双指针遍历两个子数组，依次选取较小（升序）的元素放入结果数组，最终将合并后的有序数组覆盖原数组对应区间。

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/aedc8241a6d24cb192418cf6445a6170.gif#pic_center">

⚠️

踩坑记录：

我在实际项目中遇到过一个问题，这个配置在开发环境正常，但生产环境会报错。

后来发现是因为生产环境的版本不一致导致的。

建议大家在部署前一定要检查版本兼容性。

punctuation">::vector

class="token

punctuation">::vector

class="token

function">mergeSort

class="token

punctuation">::vector

class="token

function">mergeSort

class="token

function">mergeSort

class="token

function">mergeSort

class="token

punctuation">::vector

class="token

function">mergeSort

class="token

punctuation">}

5.算法优化

• 提前终止合并：合并前判断左子数组的最后一个元素

  右子数组的第一个元素，若成立则两个子数组已天然有序，无需执行合并操作；

id="6__230">6.

n）

空间复杂度：O(n)（需要临时数组存储子数组）

稳定性：稳定

六、快速排序（Quick

Sort）

id="1_235">1.算法描述

快速排序是一种基于分治思想的原地比较排序算法，也是实际工程中应用最广泛的高效排序算法（被冠以

“快速”

将数组划分为左右两部分（左部分≤基准值、右部分≥基准值），递归处理左右子数组，最终通过分区的收敛性实现整体有序（无需归并排序的

“合并”

• 选基准（Pivot）：从待排序数组中选择一个元素作为基准值，基准值的选择直接决定算法的性能（核心优化点）；
• 分区（Partition）：遍历数组，将小于等于基准值的元素移到基准值左侧，大于等于基准值的元素移到右侧，最终基准值会被放到

  “排序后的正确位置”；

• 递归处理：对基准值左侧和右侧的子数组重复执行

  “选基准

  操作，直到子数组长度≤1（单个元素天然有序，递归终止）；

• 整个过程无需额外的合并步骤，分区完成后子数组的有序性会自然收敛到整个数组有序。

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/74bf6237c9f14432adbb567df8b13d90.gif#pic_center">

function">partition

class="token

punctuation">::vector

class="token

function">quickSort

class="token

punctuation">::vector

class="token

function">partition

class="token

function">quickSort

class="token

function">quickSort

class="token

function">quickSort

class="token

punctuation">::vector

class="token

function">quickSort

class="token

punctuation">}

id="5_276">5.算法优化

• 基准值优化（核心）：
  • 三数取中法：选择数组左、中、右三个位置的中位数作为基准值，避免已排序

    逆序数组导致的最坏情况；

  • 随机选基准：随机选取数组中的元素作为基准值，将最坏情况的概率降至极低；
  • 大数组用三数取中，小数组用固定基准，兼顾性能与效率。

• 三路快排优化：将数组分为

  O(n*logn)、最坏

  O(n*n)（已排序数组，基准选最后一个）

• 空间复杂度：O(logn)（递归栈空间）
• 稳定性：不稳定

Sort）

id="1_287">1.算法描述

堆排序是一种基于堆数据结构的选择类比较排序算法，也是少数能同时实现

“原地排序

在正式排序前，需先明确堆的基础概念：堆是完全二叉树结构，满足

“大顶堆”（每个父节点≥子节点）或

“小顶堆”（每个父节点≤子节点）的性质；数组可直接映射为完全二叉树（索引

1，右子节点

src="https://i-blog.csdnimg.cn/direct/a6d2d84850df48d0862b73d126033497.jpeg#pic_center">

堆排序（升序）的核心步骤：

• 构建初始大顶堆：从最后一个非叶子节点开始，向前遍历并调整每个节点的位置，使整个数组满足大顶堆性质（堆顶为最大值）；
• 提取堆顶极值：交换堆顶元素（最大值）和当前堆的最后一个元素，此时最大值被

  “固定”

  到数组末尾（已排序区间）；

• 调整剩余堆：将交换后的剩余元素（未排序区间）重新调整为大顶堆（仅需调整堆顶节点，因为其余节点仍满足堆性质）；
• 重复

  “提取极值

  src="https://i-blog.csdnimg.cn/direct/6ea50fe12b244c398ff9a3af692b9fe5.gif#pic_center">

  punctuation">::vector

  class="token

  punctuation">[largest

  class="token

  punctuation">[right

  class="token

  punctuation">[largest

  class="token

  punctuation">[largest

  class="token

  punctuation">::vector

  class="token

  构建大顶堆（从最后一个非叶子节点开始）

  class="token

  punctuation">}

  5.

  (n*logn)）；

• 空间复杂度：迭代版：O(1)

  递归版：O(logn)（递归栈空间）；

• 稳定性：不稳定

id="Counting_Sort_338">八、计数排序（Counting

Sort）

id="1_339">1.算法描述

计数排序是一种非比较类的线性时间排序算法，也是入门级的

“基于统计”

的排序算法。

其核心逻辑并非通过元素间的比较实现排序，而是通过统计数组中每个元素的出现次数，再根据元素值的大小顺序重新填充数组

完全避开比较操作，因此能突破比较类排序

id="2_341">2.核心思想

计数排序的前提是：待排序元素为整数，且元素值的范围（记为

k）远小于数组长度

• 确定值域范围：遍历数组找到最小值

  minVal

  1（用于确定计数数组的长度）；

• 统计元素频次：创建长度为

  range

  minVal，避免负数索引）；

• 计算前缀和：对计数数组做前缀和处理，此时

  count[i]

  的元素总数”，该值可直接确定对应元素在有序数组中的最终位置；

• 反向填充结果：从原数组的末尾向前遍历（保证排序稳定性），根据前缀和数组找到当前元素的目标位置，放入结果数组后更新前缀和（避免重复元素位置冲突）；
• 拷贝结果：将有序的结果数组拷贝回原数组，完成排序。

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/3258c2919e8b497f9de8c8a2a0496fe2.gif#pic_center">

function">countingSort

class="token

punctuation">::vector

class="token

function">max_element

class="token

function">min_element

class="token

punctuation">::vector

class="token

punctuation">(range

class="token

punctuation">{count

class="token

punctuation">{count

class="token

punctuation">{output

class="token

punctuation">[count

class="token

punctuation">;count

class="token

punctuation">}

5.

k)

稳定性：稳定（反向填充结果数组时，相等元素的相对顺序与原数组一致）；

id="Radix_Sort_388">九、基数排序（Radix

Sort）

id="1_389">1.算法描述

基数排序是一种非比较类的线性时间排序算法，也是桶排序的高效变种。

其核心逻辑并非直接比较元素大小，而是将元素按

“位”

拆分（如十进制数的个位、十位、百位），对每一位依次执行稳定排序（通常用计数排序

桶排序）——

从最低位到最高位（或反之）完成所有位的排序后，数组会自然整体有序。

该算法完全避开比较操作，突破了比较类排序

O(n*logn)

id="2_391">2.核心思想

基数排序的前提是：待排序元素可按

“位”

2）。

主流的低位优先（LSD）

升序排序核心步骤：

• 确定排序参数：遍历数组找到最大值，计算其位数（即需要排序的总轮数

  maxDigit）；确定基数

  计数：从最低位（个位）到最高位依次遍历每一位：

  1. 对当前位执行稳定排序（常用计数排序，也可用桶排序）：
     • 统计当前位上每个数字（0~radix-1）的出现频次；
     • 计算前缀和确定每个数字在结果数组中的位置；
     • 反向遍历原数组，按当前位数字将元素放入结果数组（保证稳定性）；
  2. 将结果数组拷贝回原数组，完成当前位的排序；
• 所有位排序完成后，数组整体有序。

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/4b2be07c4b5748a5ad1daed4d29b4759.gif#pic_center">

function">radixSort

class="token

punctuation">::vector

class="token

function">max_element

class="token

punctuation">;maxDigit

class="token

punctuation">::vector

class="token

punctuation">::vector

class="token

punctuation">;buckets

class="token

punctuation">[digit

class="token

function">push_back

class="token

punctuation">}bucket

class="token

punctuation">}

5.

算法分析

• 时间复杂度：O(d*(n+k))（d是位数，k是基数，十进制

  k)

• 稳定性：稳定

id="Bucket_Sort_449">十、桶排序（Bucket

Sort）

id="1_450">1.算法描述

桶排序是一种基于分治和值域映射的非比较类线性时间排序算法，也是计数排序、基数排序的通用扩展形式。

其核心逻辑是将待排序元素按预设的

“值域区间”

中，对每个桶内的元素执行稳定排序（通常用插入排序），最后按桶的顺序合并所有桶内的元素

“分桶降维”

id="2_452">2.核心思想

桶排序的前提是：待排序元素均匀分布在某个连续值域范围内（如

0~100

• 确定桶的参数：遍历数组找到最小值

  minVal

  bucketCount（通常取数组长度的平方根或固定值），计算每个桶的区间大小

  interval

  bucketCount；

• 元素分桶：创建

  bucketCount

  个空桶，遍历原数组，将每个元素根据值域映射到对应的桶中（映射公式：桶索引

  (num

  interval）；

• 桶内排序：对每个非空桶内的元素执行稳定排序（小规模数据优先选插入排序，大规模可选快速排序）；
• 合并桶：按桶的索引顺序，将所有桶内的元素依次拷贝回原数组，完成整体排序。

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/4d980f4bde9a476ca57718511db39b29.gif#pic_center">

function">bucketSort

class="token

punctuation">::vector

class="token

function">max_element

class="token

function">min_element

class="token

punctuation">::vector

class="token

punctuation">::vector

class="token

punctuation">(bucketCount

class="token

punctuation">;buckets

class="token

punctuation">[index

class="token

function">push_back

class="token

function">insertionSort

class="token

punctuation">(bucket

class="token

punctuation">}

5.

O(n*n)所有元素进一个桶）

空间复杂度：O(n

k)

稳定性：稳定（取决于桶内排序算法）

---

id="_498">通用准备工作

为了方便测试和展示排序效果，我们先定义两个通用函数：打印数组、生成随机数组。

所有排序算法都会基于这两个函数进行测试。

string"><iostream>

class="token

string"><vector>

class="token

string"><cstdlib>

class="token

string"><ctime>

class="token

string"><cmath>

class="token

string"><algorithm>

class="token

function">printArray

class="token

punctuation">::vector

class="token

punctuation">::endl

class="token

punctuation">::vector

class="token

function">generateRandomArray

class="token

punctuation">::vector

class="token

punctuation">}

punctuation">::vector

class="token

function">generateRandomArray

class="token

function">printArray

class="token

测试每种排序算法（每次测试前复制原始数组）std

class="token

punctuation">::vector

class="token

function">bubbleSort

class="token

punctuation">(arrCopy

class="token

function">printArray

class="token

punctuation">(arrCopy

class="token

function">selectionSort

class="token

punctuation">(arrCopy

class="token

function">printArray

class="token

punctuation">(arrCopy

class="token

function">insertionSort

class="token

punctuation">(arrCopy

class="token

function">printArray

class="token

punctuation">(arrCopy

class="token

function">shellSort

class="token

punctuation">(arrCopy

class="token

function">printArray

class="token

punctuation">(arrCopy

class="token

function">mergeSort

class="token

punctuation">(arrCopy

class="token

function">printArray

class="token

punctuation">(arrCopy

class="token

function">quickSort

class="token

punctuation">(arrCopy

class="token

function">printArray

class="token

punctuation">(arrCopy

class="token

punctuation">(arrCopy

class="token

function">printArray

class="token

punctuation">(arrCopy

class="token

function">countingSort

class="token

punctuation">(arrCopy

class="token

function">printArray

class="token

punctuation">(arrCopy

class="token

function">radixSort

class="token

punctuation">(arrCopy

class="token

function">printArray

class="token

punctuation">(arrCopy

class="token

function">bucketSort

class="token

punctuation">(arrCopy

class="token

function">printArray

class="token

punctuation">(arrCopy

class="token

punctuation">}

id="_592">总结

排序算法	最好情况	最坏情况	平均时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	O(n)	O(n*n)	O(n*n)	O(1)	稳定	小规模数据、几乎有序的数据
选择排序	O(n*n)	O(n*n)	O(n*n)	O(1)	不稳定	小规模数据
插入排序	O(n)	O(n*n)	O(n*n)	O(1)	稳定	小规模数据、几乎有序的数据
希尔排序	O(n)	O(n*n)	O(n^1.3)	O(1)	不稳定	中等规模数据
归并排序	O(n*logn)	O(n*logn)	O(n*logn)	O(n)	稳定	大规模数据、需要稳定排序
快速排序	O(n*logn)	O(n*n)	O(n*logn)	O(logn)	不稳定	大规模数据（实际应用最优）
堆排序	O(n*logn)	O(n*logn)	O(n*logn)	O(1)	不稳定	大规模数据、内存受限场景
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定	整数、值范围小的数据集
基数排序	O(d(n+k))	O(d(n+k))	O(d(n+k))	O(n+k)	稳定	整数、字符串、位数固定的元素
桶排序	O(n+k)	O(n*n)	O(n+k)	O(n+k)	稳定	元素均匀分布的数据集

1. 比较类排序（冒泡

   堆）：基于元素比较实现，时间复杂度最低为

   桶）：不依赖比较，时间复杂度更低，但有适用场景限制。

2. 稳定性：稳定排序（冒泡

   桶）适合需要保留相等元素相对位置的场景（如电商订单按价格排序后保留下单时间）。

3. 实际选型：小规模数据用插入

   冒泡；大规模数据优先用快速排序（实际性能最优）；需要稳定排序选归并；整数且范围小选计数排序；元素均匀分布选桶排序。