C++实现双向冒泡排序算法

前言双向冒泡排序cocktail shaker sort也叫鸡尾酒排序、摇晃排序、双向气泡排序是冒泡排序的一个小改进每一轮先从左往右把最大的元素送到右端再从右往左把最小的元素送到左端扫描区间逐轮向中间收缩。它最典型的应用场景是「大部分元素已有序只有少数元素位于错误的一端」——比如序列2 3 4 5 6 7 8 9 1普通冒泡要把那个 1 一路向左换八次而双向冒泡一轮就能把它带到最左。围绕它的误解主要有两个。第一是把它当成「更快的冒泡排序」实际上两者的最坏复杂度和平均复杂度都是 O(n²)双向扫描只是把常数因子和某些特定输入下的轮数降下来不改变渐进阶。第二是以为它和冒泡排序一样只在「已经有序」时提前退出实际上双向版本还能利用「某一方向本轮没有发生交换」来判断该方向已经有序从而把边界收得更紧。本文从冒泡排序的瓶颈讲起推导双向扫描的边界更新规则给出完整实现并逐轮手工推演最后讨论它的稳定性、复杂度以及什么时候根本不该用它。代码以 C17 为基准。一、冒泡排序的瓶颈普通冒泡排序每一轮从下标 0 扫描到n - 1 - round比较相邻元素逆序就交换。一轮结束后未排序区间里最大的元素一定被推到了区间末尾所以下一轮的右边界可以收缩一位。问题在于「小元素向左移动」的速度。冒泡排序每轮只让一个元素向左移动一位准确说是每轮把一个元素送到它该去的位置如果最小的元素恰好在最右端它需要经过 n-1 轮才能到位。而最大的元素在同样一轮里可以被连续交换一路推到右端两个方向的移动速度并不对称。双向冒泡的思路就是补上这个不对称正向扫描结束后右端已经就位紧接着做一次反向扫描把最小的元素一路推到左端然后左边界收缩。这样每一轮能同时确定两个位置最坏情况下轮数大约减半。二、边界收缩与提前退出设未排序区间为[lo, hi)初始lo 0hi n。正向扫描从lo到hi - 2比较a[i]与a[i1]逆序则交换。扫描结束后a[hi-1]是区间最大值于是--hi。反向扫描从hi - 1到lo 1比较a[i-1]与a[i]逆序则交换。扫描结束后a[lo]是区间最小值于是lo。这里有两个边界细节必须盯住。第一反向扫描的下标是递减的std::size_t。如果写成for (std::size_t i hi - 1; i lo; --i)当i减到 0 之后再执行--i会回绕成SIZE_MAX循环永远不会结束而且会越界访问。正确写法是让循环在i lo时继续循环体内访问a[i-1]与a[i]这样最小的下标是lo 1不会碰到 0 回绕的问题。第二空数组和单元素数组要能被正确处理。hi - lo在hi lo 0时等于 0如果代码里写while (hi - lo 1)是安全的但如果写成while (hi lo 1)而lo是无符号数也没有问题。真正危险的是先做hi - 1再判断hi为 0 时会回绕。因此循环条件应当在使用下标之前判断。提前退出用两个来源一是本轮任何方向都没有发生交换说明整个区间已经有序二是正向扫描没有交换说明右半部分有序但仍需反向扫描确认左侧。实现上用一个swapped标志在每轮开始时清零任一方向发生交换就置位整轮结束后若仍为假则退出。三、完整实现// 适用于 C17#include cstddef#include iostream#include utility#include vectorvoid cocktail_sort(std::vectorint a) {std::size_t lo 0;std::size_t hi a.size();bool swapped true;while (swapped hi - lo 1) {swapped false;// 正向把当前区间最大值送到 hi-1for (std::size_t i lo; i 1 hi; i) {if (a[i] a[i 1]) {std::swap(a[i], a[i 1]);swapped true;}}--hi;// 反向把当前区间最小值送到 lofor (std::size_t i hi; i lo; --i) {if (a[i - 1] a[i]) {std::swap(a[i - 1], a[i]);swapped true;}}lo;}}void print(const std::vectorint a) {for (int v : a) {std::cout v ;}std::cout \n;}int main() {std::vectorint data{5, 1, 4, 2, 8, 0, 2};cocktail_sort(data);print(data);return 0;}for (std::size_t i lo; i 1 hi; i)这个条件比i hi - 1更稳妥当hi为 0 时hi - 1会回绕成巨大值而i 1 hi在hi 0时直接为假循环一次都不执行。这类「用加法代替减法避免无符号下溢」的技巧在边界处理中很常见值得养成习惯。用输入5 1 4 2 8 0 2手工推演一轮正向扫描比较5,1交换得1 5 4 2 8 0 25,4交换得1 4 5 2 8 0 25,2交换得1 4 2 5 8 0 25,8不换8,0交换得1 4 2 5 0 8 28,2交换得1 4 2 5 0 2 8。此时hi从 7 减到 6。反向扫描从i 6开始比较a[5]2与a[6]8不换i 5a[4]0与a[5]2不换i 4a[3]5与a[4]0交换得1 4 2 0 5 2 8i 3a[2]2与a[3]0交换得1 4 0 2 5 2 8i 2a[1]4与a[2]0交换得1 0 4 2 5 2 8i 1a[0]1与a[1]0交换得0 1 4 2 5 2 8。循环条件i lo在i减到 0 之前就结束了lo变为 1。第二轮继续最终得到0 1 2 2 4 5 8。手工推演的价值在于验证边界如果反向循环的终止条件写成i lo最后一步会访问a[SIZE_MAX]如果正向循环用i hi而不检查i 1最后一次比较会越界。这两处是这类算法最常见的崩溃点。四、复杂度、稳定性与替代方案比较次数方面双向冒泡每轮做两次扫描总轮数在最坏情况下约为 n/2比较次数与普通冒泡同阶仍是 O(n²)交换次数的期望也更低因为每一轮把两个元素送到位。空间复杂度 O(1)只用了几个下标和标志。稳定性方面算法只在严格逆序a[i] a[i1]时交换相等元素不会互换位置因此是稳定排序。这一点在需要保持相等元素原始次序时很重要比如先按姓名排序、再按年龄排序第二次排序必须稳定才能保留第一次的结果。std::sort不保证稳定需要稳定时用std::stable_sort。算法最好平均最坏空间稳定冒泡排序O(n)O(n²)O(n²)O(1)是双向冒泡O(n)O(n²)O(n²)O(1)是插入排序O(n)O(n²)O(n²)O(1)是归并排序O(n log n)O(n log n)O(n log n)O(n)是std::sort内省排序O(n log n)O(n log n)O(n log n)O(log n)否实际工程里几乎不会用双向冒泡排序给真实数据排序std::sort在任何规模下都更合适。它的价值主要在教学用最小的代码量展示「边界收缩」「提前退出」「无符号下标回绕」这三个通用技巧。如果题目明确要求「冒泡排序的变体」或者考察对循环边界的把控它才是合适的选择。常见坑点坑点一反向循环的无符号下标回绕。❌for (std::size_t i hi - 1; i lo; --i)i为 0 时再减一会变成SIZE_MAX循环失控并越界。✅for (std::size_t i hi; i lo; --i)循环体内访问a[i-1]与a[i]最小下标是lo 1。坑点二空数组时先算hi - 1。❌std::size_t last a.size() - 1;空数组时回绕成SIZE_MAX。✅ 先判断a.size() 2直接返回或用i 1 hi这样的上界写法。坑点三正向扫描的上界写成i hi。❌ 循环体访问a[i1]最后一次迭代越界std::vector::operator[]越界是未定义行为。✅ 条件写i 1 hi保证i1始终合法。坑点四忘记在每轮开始时重置 swapped。❌ 把swapped false;写在循环外第一轮之后它永远是 true提前退出失效。✅ 每轮进入循环体第一件事就是清零两个方向共用同一个标志。坑点五以为双向冒泡是 O(n log n)。❌ 在需要处理十万级数据的场景选它理由是「双向所以快一倍」。✅ 它的渐进复杂度仍是 O(n²)大数据用std::sort或std::stable_sort。坑点六自定义比较时用。❌if (!(a[i] a[i1])) swap(...)相等元素也会交换稳定性被破坏。✅ 用严格大于判断逆序if (a[i] a[i1])相等时保持原序。坑点七反向扫描的起点写成hi - 1而不是hi。❌ 先--hi再让i hi - 1等于跳过了刚就位的那个元素的前一个位置边界错位。✅ 明确不变式hi是开区间上界反向扫描从i hi开始比较a[i-1]与a[i]。坑点八在排序过程中修改容器大小。❌ 循环里对a调用push_back或erasesize()变化导致边界失效迭代器/下标全部作废。✅ 排序前确定容器大小排序期间只做元素交换。总结要点结论核心思想正向送最大值到右端反向送最小值到左端边界表示未排序区间为[lo, hi)正向条件i 1 hi避免越界与下溢反向条件i lo循环体访问i-1提前退出整轮无交换即有序时间复杂度最好 O(n)平均与最坏 O(n²)空间复杂度O(1)稳定性稳定严格大于才交换双向冒泡排序不是一个「更优的算法」而是一个「更对称的冒泡」。它的全部技巧都集中在循环边界上区间怎么表示、下标怎么递减、什么时候可以提前收手。把这三件事写对代码只有二十行写错任何一处得到的不是慢一点的结果而是越界访问这种未定义行为。