C算法
交换排序详解：冒泡优化与快速排序四种实现
交换排序算法主要包含冒泡排序与快速排序。冒泡排序通过相邻元素比较交换实现有序化，可通过标记优化提前终止。快速排序采用分治策略，核心在于基准值选取与分区操作。了快速排序的四种实现：Hoare 版本、前后指针法、挖坑法及非递归版本。同时介绍了三数取中、小区间优化等提升性能的关键技术，并对比了递归与非递归在内存模型上的差异。
交换排序算法主要包含冒泡排序与快速排序。冒泡排序通过相邻元素比较交换实现有序化，可通过标记优化提前终止。快速排序采用分治策略，核心在于基准值选取与分区操作。了快速排序的四种实现：Hoare 版本、前后指针法、挖坑法及非递归版本。同时介绍了三数取中、小区间优化等提升性能的关键技术，并对比了递归与非递归在内存模型上的差异。
交换排序的核心逻辑非常纯粹：通过两个元素之间的比较与位置交换，让有序的序列逐渐浮现。
本篇将深度拆解：冒泡排序及其极致优化，以及快速排序的四种主流实现（Hoare 版本、挖坑法、前后指针法、非递归实现）。
冒泡排序模拟了水中气泡上升的过程。大的数值会通过相邻位置的比较，一层一层地往数组末尾浮动。
核心步骤：
很多教科书给出的冒泡排序是'死'的。如果数组已经有序了，它依然会傻傻地跑完所有循环。
极致优化思路： 设置一个标记。如果在一轮遍历中没有发生任何交换，说明数组已经有序，直接提前终止！
void BubbleSort(int* a, int n) {
// 外层循环：控制排序的轮数
// 每执行完一轮，待排序序列中最大的那个数就会被'冒泡'到数组的最后一位
// n 个元素通常需要比较 n-1 轮
for (int i = 0; i < n; i++) {
// 【优化关键】：设置一个标记变量 flag
// 初始设为 0，假设这一轮遍历中没有发生任何交换（即数组已经有序）
int flag = 0;
// 内层循环：负责在当前待排序区间内进行相邻两数的比较
// 随着 i 的增加，数组末尾已经排好序的元素越来越多
// 因此内层循环的边界是 n - i - 1
for (int j = 0; j < n - i - 1; j++) {
// 如果前一个数比后一个数大，则说明顺序不对，需要交换
if (a[j] > a[j + 1]) {
// 调用交换函数，将大的数往后挪
Swap(&(a[j]), &(a[j + 1]));
// 只要发生了交换，就说明此时数组可能还没完全有序
// 将 flag 置为 1
flag = 1;
}
}
// 一轮比较结束后，检查 flag 的状态
// 如果 flag 依然为 0，说明在这一轮整趟遍历中没有发生任何数据交换
// 这意味着数组已经完全有序了，不需要再进行后续的轮数，直接提前结束循环
if (flag == 0) break;
}
}
快速排序（Quick Sort）是计算机科学领域最伟大的算法之一。它的核心是一种**'分而治之'**的策略：选一个基准值（key），通过一次排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快排的创始人 Tony Hoare 最初设计的逻辑非常简洁：选取一个基准值（key），通过左右指针的'对冲'交换，实现左右分区。
算法逻辑：
key。key 小的值。key 大的值。L 和 R 指向的元素对调。L 与 R 相遇时，将 key 与相遇点的值交换。这里就得问问为什么了，为什么相遇的位置一定是 key 的准确位置呢？为什么必须是 R 先走呢？当 L 和 R 相遇时，只有两种情况，而这两种情况在 R 先走的前提下都是安全的：
情况 A：R 撞上 L
key 本身，要么是刚刚换过来的比 key 小的值。key 小的值，直到撞上 L。此时相遇点的值是 L 停留的值（即 ≤ key 的值），交换是安全的。情况 B：L 撞上 R
key 小的值并停了下来。这个逻辑可以总结为一个对称的原则：
key，右边先走：保证相遇点 ≤ key。key，左边先走：保证相遇点 ≥ key。一句话总结：先走的那一方，实际上是在为最后一次交换'踩点'，确保交换回来的数符合分区的要求。
void QuickSort(int* a, int left, int right) {
// 递归终止条件：区间只有一个元素或区间非法
if (left >= right) return;
int begin = left;
int end = right;
// 选定左边第一个数为基准值，记录其位置
int key_pos = left;
while (begin < end) {
// 关键点 1：必须右边先走！寻找比基准值小的值
while (begin < end && a[end] >= a[key_pos]) end--;
// 关键点 2：左边再走 寻找比基准值大的值
while (begin < end && a[begin] <= a[key_pos]) begin++;
// 找到后，交换左右两个'不听话'的元素 使得小的去左边，大的去右边
Swap(&(a[begin]), &(a[end]));
}
// 此时 begin == end，即指针相遇，将相遇点的值与基准值位置的值交换
// 由于是右边先走，保证了 a[begin] 一定小于等于 a[key_pos]
Swap(&(a[begin]), &(a[key_pos]));
// 更新基准值在数组中的最终正确位置 key_pos = begin;
key_pos = begin;
// 递归处理左子区间 [left, key_pos - 1]
QuickSort(a, left, key_pos - 1);
// 递归处理右子区间 [key_pos + 1, right]
QuickSort(a, key_pos + 1, right);
}
在快速排序中，'三数取中'（Median-of-Three）是一项极其关键的优化技术。它的核心目的只有一个：防止算法在处理'最差情况'时退化，确保排序效率的稳定性。
以下是为什么要采取这一策略的深层原因：
代码比较简单，就判断即可。
为什么要进行小区间优化？
快速排序是一个递归算法。随着递归的深入，子区间的长度会越来越短。当区间长度减小到一定程度（例如 10 左右）时，继续使用快排会带来两个负面影响：
假设此图为快速排序递归树，如果每一次递归都进行到区间只有一个元素为止，那么最后一层将产生最多的函数调用。那就可以将最后几层优化掉，也就是使用别的排序替换掉最后几层的快排。你可以选择任何你喜欢的排序算法，这里我选插入排序。
// 小区间优化：当区间长度小于 10 时，采用插入排序
if ((right - left + 1) < 10) {
// 注意：传入的地址是 a + left，长度是区间个数
InsertSort(a + left, right - left + 1);
return;
}
当子区间的 right - left + 1 小于某个阈值（通常设定为 10~15）时，我们不再进行划分，而是直接调用插入排序（Insertion Sort）。
为什么选择插入排序？
在快速排序的多种单趟排序实现中，前后指针法以其代码极其精简、逻辑高度一致的特点，成为现代工程实践中最受推崇的版本之一。
前后指针法的核心思想可以形象地比喻为 '推土机'或'区域划分'：
key (基准值)：作为参照的标杆，通常选定为区间的第一个元素。prev (后指针)：它是小于 key 区域的边界。它的左边（包括它自己）存放的都是已经发现的比 key 小的值。cur (前指针)：它是侦察兵。它从左向右扫描数组，寻找比 key 小的元素。left 位置。令 prev 指向 left，cur 指向 left + 1。cur 移动)：
a[cur] 大于或等于 key，cur 直接继续向后走。a[cur] 小于 key，说明找到了一个需要被'归位'的小数：
prev 向前移动一步（扩展小于区边界）。a[prev] 和 a[cur]，将这个小数扔进 prev 维护的'安全区'内。cur 遍历完整个区间后，prev 所在的位置就是小于 key 区域的最后一个位置。此时交换 a[prev] 和 a[key_pos]，key 正好落在了大小数的分界点上。int PartSort3(int* a, int left, int right) {
// 1. 三数取中优化：从左、中、右三个位置选出中间值
// 目的：防止在处理有序数组时快排退化为 O(N^2)
int midi = getMidi(a, left, right);
// 将选出的中间值交换到左边界，作为基准值(key)
Swap(&(a[midi]), &(a[left]));
int key_pos = left;
// 记录基准值的位置
int prev = left;
// prev 指向小于 key 区域的最后一个元素
int cur = left + 1;
// cur 作为探路指针，寻找比 key 小的元素
// 2. 探路阶段：cur 遍历整个区间
while (cur <= right) {
// 如果 cur 发现了一个比基准值小的数
if (a[cur] < a[key_pos]) {
// 小于 key 的区域向后扩展一位 prev++
prev++;
// 将 cur 发现的小数交换到 prev 的新位置
// 只有在 prev 和 cur 不相等时才交换，减少无效自换
if (prev != cur) Swap(&(a[cur]), &(a[prev]));
}
// cur 无论是否发现小数，都继续向后探测 cur++
cur++;
}
// 3. 基准值归位
// 此时 prev 及其左边都是小于 key 的数，prev 右边都是大于等于 key 的数
// 将基准值交换到 prev 的位置，使其回到序列正中间
Swap(&(a[prev]), &(a[key_pos]));
// 返回基准值的正确下标，用于后续递归分裂区间
return prev;
}
挖坑法是 Hoare 版本的变体，以其极其直观的逻辑，成为了最容易理解的版本。通过'填坑'的动作，形象地展示了数据如何根据基准值（key）进行左右分流，不需要纠结谁先走。
挖坑法的核心在于利用一个临时变量存出基准值，从而在数组中制造一个'坑位'，随后通过左右指针交替填坑。
left）形成第一个坑。key 小的数，将其填入左边的坑中，随后 right 位置变成新坑。key 大的数，将其填入右边的坑中，随后 left 位置变成新坑。left。将 a[left] 赋值给变量 key，令 hole = left。right 开始向左找比 key 小的数。找到后，将 a[right] 填入 a[hole]，并更新坑位 hole = right。left 开始向右找比 key 大的数。找到后，将 a[left] 填入 a[hole]，并更新坑位 hole = left。left 与 right 相遇。key 填入相遇点的坑位 a[hole]。int PartSort2(int* a, int left, int right) {
// 1. 三数取中优化：在左、中、右三个数中选出数值大小排在中间的那一个
// 这样可以有效防止在面对有序数组时，基准值选到极值导致效率退化为 O(N^2)
int midi = getMidi(a, left, right);
Swap(&(a[midi]), &(a[left]));
// 将选出的中间值交换到左边界，作为基准值
// 2. 形成初始坑位
// 将基准值保存在变量 key 中，此时 a[left] 逻辑上形成了一个'坑'
int hole = left;
int key = a[left];
// 左右指针开始向中间靠拢，直到 left 和 right 相遇
while (left < right) {
// 3. 右边找小，填左坑
// 右指针向左移动，跳过所有大于或等于 key 的元素
while (left < right && a[right] >= key) --right;
// 找到比 key 小的数后，将其填入左边的'坑' a[hole] 中
// 此时 a[right] 位置空了出来，成为新的'坑'
a[hole] = a[right];
hole = right;
// 4. 左边找大，填右坑
// 左指针向右移动，跳过所有小于或等于 key 的元素
while (left < right && a[left] <= key) ++left;
// 找到比 key 大的数后，将其填入右边的'坑' a[hole] 中
// 此时 a[left] 位置空了出来，再次成为新的'坑'
a[hole] = a[left];
hole = left;
}
// 5. 回填基准值
// 当循环结束（left == right），将最初保存的 key 填入最后的坑位
a[hole] = key;
// 返回基准值最终所在的下标，供外层递归划分区间
return hole;
}
在面对海量数据时，深度递归可能会导致栈溢出（Stack Overflow），因为系统栈的空间是有限的。为了提高算法的稳健性，我们可以利用 堆区（Heap） 上开辟的自定义栈（Stack）来手动模拟递归过程。
为什么在处理工业级大数据时，非递归版本更受青睐？这涉及到计算机底层内存的布局差异：
| 内存区域 | 递归（系统栈） | 非递归（自定义栈） |
|---|---|---|
| 所属位置 | 栈区 (Stack) | 堆区 (Heap) |
| 空间大小 | 极小，通常为 1MB ~ 8MB | 极大，取决于物理内存 (GB 级别) |
| 溢出风险 | 高（深度递归易导致 Stack Overflow） | 极低（通过 realloc 动态扩容） |
| 管理方式 | 操作系统自动分配与回收 | 程序员手动初始化与销毁 |
把每次函数递归时不一样的部分画在递归树上可以得到，每次就是待排序数组的边界不一样，也就是区间，那就只需要把区间存起来就好了，然后每次取出需要用的那个区间就好，现在要考虑的就是存取顺序而已，在递归版本的代码，首先是对左部分区间进行递归排序，那就跟递归版本保持一致，也从左区间开始存取，但栈是后进先出，所以怎么压栈就是最大的难题。
先排左，那就代表需要先取出左，那就只能先压右，注意这里区间有左右两个数，这个顺序也很重要，不要取反了。
STInit(ST* pst)：初始化栈。将数组指针置空，容量与栈顶位置归零。STDestroy(ST* pst)：销毁栈。释放动态开辟的内存空间，防止内存泄漏。STPush(ST* pst, STDataType x)：入栈。
top == capacity），利用 realloc 进行扩容。left 和 right 下标压入栈中。STPop(ST* pst)：出栈。
assert）栈不为空，直接将 top 减 1 即可实现逻辑删除。STTop(ST* pst)：获取栈顶元素。
a[top - 1] 位置的值。在快排中，这用于获取当前要处理的区间边isEmpty(ST* pst)：判空。
while 循环的终止条件。只要栈不为空，就说明还有待排序的子区间。这些接口之前都已经实现过了，所以这里只给出接口，代码参考相关栈实现文档。
非递归快排的执行逻辑可以概括为以下步骤：
right 再入 left）。begin 和 end，调用单趟排序函数（如 singleTripSort）确定基准值的位置 key_pos。key_pos 将原区间拆分为左右两个子区间。void QuickSortNonR(int* a, int left, int right) {
// 1. 初始化自定义栈（ST 为动态数组实现的栈结构）
ST st;
STInit(&st);
// 2. 初始区间入栈
// 策略：先进右边界，后进左边界。
// 根据栈'后进先出'的特性，出栈时会先拿到左边界，符合我们的思维习惯。
STPush(&st, right);
STPush(&st, left);
// 3. 循环处理栈中的任务
// 只要栈不为空，说明还有待划分的子区间
while (!isEmpty(&st)) {
// 4. 出栈获取当前待排序的区间下标 [begin, end]
// 先拿出来的 top 是左边界，后拿出来的是右边界
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
// 5. 执行单趟排序（singleTripSort）
// singleTripSort 会选定基准值并完成分区，返回基准值的最终下标位置 key_pos
// 此时 a[key_pos] 已经处于其最终正确位置
int key_pos = singleTripSort(a, begin, end);
// 6. 分裂子区间并入栈（分治思想的体现）
// 原区间 [begin, end] 被 key_pos 分为左右两部分：
// 左区间：[begin, key_pos - 1]
// 右区间：[key_pos + 1, end]
// --- 压入右子区间 ---
// 如果右区间包含至少两个元素（key_pos + 1 < end），则入栈等待处理
if (key_pos + 1 < end) {
STPush(&st, end);
STPush(&st, key_pos + 1);
}
// --- 压入左子区间 ---
// 如果左区间包含至少两个元素（key_pos - 1 > begin），则入栈等待处理
if (key_pos - 1 > begin) {
STPush(&st, key_pos - 1);
STPush(&st, begin);
}
// 注意：由于栈是 LIFO（后进先出），我们后压入左区间，
// 那么下一次循环会优先处理左区间，逻辑上模拟了递归的前序遍历。
}
// 7. 任务完成，销毁栈并释放动态内存
STDestroy(&st);
}
flag 优化，其本质仍未脱离 O(N^2) 的限制，适用于小规模数据或教学入门。三种单趟排序方法，反映了对数据移动的不同理解：
prev 和 cur 像推土机一样线性推进。这种方法逻辑高度一致，代码最为精简，且对 CPU 缓存（Cache）更加友好，是工业级实现的首选。非递归版本的剖析加深了对计算机体系结构的理解：
LIFO 栈结构手动维护待处理的区间，模拟了深度优先搜索（DFS）的遍历路径。这是处理千万级、亿级海量数据时防止程序崩溃的终极保障。| 特性 | 冒泡排序（优化版） | 快速排序（递归 + 优化） | 快速排序（非递归） |
|---|---|---|---|
| 平均时间复杂度 | O(N^2) | O(N log N) | O(N log N) |
| 空间复杂度 | O(1) | O(log N)（栈帧消耗） | O(log N)（堆区开销） |
| 核心风险 | 效率极低 | 深度递归导致栈溢出 | 需要手动管理内存 |
| 最佳应用场景 | 教学、极小规模数据 | 通用高性能排序 | 工业级、海量数据处理 |
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online