目录一、冒泡排序1.1 算法思想1.2 代码实现1.3 运行推演1.4 复杂度分析二、快速排序2.1 算法思想2.2 代码实现2.3 运行推演2.4 复杂度分析前言 交换排序的本质是通过“比较相邻元素、逆序则交换”逐步消除逆序对。冒泡排序作为最朴素的交换排序以稳定的相邻交换保证稳定性快速排序则凭借分治策略与高效的划分操作成为实际应用中最快的通用排序算法。本文将从冒泡排序的迭代优化讲起直至快速排序的递归分治与复杂度陷阱结合代码与状态日志逐帧剖析。一、冒泡排序1.1 算法思想冒泡排序重复地遍历待排序序列每次比较相邻的两个元素如果它们的顺序错误前大于后就交换。每一趟遍历完成后当前未排序部分中的最大元素会像气泡一样“浮”到末尾。经过n-1趟遍历后整个序列有序。1.2 代码实现voidBubbleSort(DataType a[],intn){inti,j;for(i0;in-1;i){intflag0;// 优化标志位记录本趟是否发生过交换for(j0;jn-1-i;j){if(a[j]a[j1]){DataType tempa[j];a[j]a[j1];a[j1]temp;flag1;}}if(flag0){break;// 整趟无交换已经有序}}}代码解析外层循环i控制趟数每完成一趟末尾就多一个排好序的元素因此内层循环的终点为n - 1 - i。flag标志位是冒泡排序的重要优化如果某一趟完整遍历后没有发生任何交换说明数组已经完全有序可以直接结束排序。这将最好情况的时间复杂度从O ( n 2 ) O(n^2)O(n2)降至O ( n ) O(n)O(n)。1.3 运行推演初始数据4 6 3 2 8 0 1 10 5 4状态日志每一趟结束后的数组4 3 2 6 0 1 8 5 4 10 3 2 4 0 1 6 5 4 8 10 2 3 0 1 4 5 4 6 8 10 2 0 1 3 4 4 5 6 8 10 0 1 2 3 4 4 5 6 8 10步骤解析 第一趟排序中从索引0开始逐对比较。46?不交换63?交换得4,3,6,...62?交换……最大值 10 逐渐被推至末端。每趟过后数组尾部的有序序列逐步加长。到第五趟时发现未发生任何交换算法提前终止。可以看到冒泡排序的“有序尾部”是从后向前逐渐构建的。1.4 复杂度分析时间复杂度最好情况序列已有序且启用flag优化一趟扫描即可退出O ( n ) O(n)O(n)。最坏情况完全逆序需n − 1 n-1n−1趟完整遍历O ( n 2 ) O(n^2)O(n2)。平均O ( n 2 ) O(n^2)O(n2)。空间复杂度O ( 1 ) O(1)O(1)。稳定性 稳定。相邻元素若相等不发生交换相对顺序不变。二、快速排序2.1 算法思想快速排序采用分治策略从序列中选取一个元素作为“基准”pivot通过一趟划分Partition将序列分成左右两部分使得左边所有元素不大于基准右边所有元素不小于基准此时基准就落在了它的最终正确位置上。然后递归地对左右两部分进行同样的操作直到每个子区间只剩一个元素或为空。2.2 代码实现intPartition(DataType a[],intlow,inthigh){DataType pivota[low];//将第一个元素作为基准while(lowhigh){while(lowhigha[high]pivot)--high;a[low]a[high];while(lowhigha[low]pivot)low;a[high]a[low];}a[low]pivot;returnlow;}voidQuickSort(DataType a[],intlow,inthigh){if(lowhigh){intpivotposPartition(a,low,high);QuickSort(a,low,pivotpos-1);QuickSort(a,pivotpos1,high);}}///////// 调用 ///////////QuickSort(a,0,n-1);////////////////////////代码解析Partition函数采用经典的“左右指针填坑法”。选取a[low]作为基准并保存low位置即成为一个“坑”。右指针high向左移动找到第一个小于 pivot 的元素填入左坑此时high位置变成新坑左指针low向右移动找到第一个大于 pivot 的元素填入右坑。如此交替直至low high将 pivot 填入最后的坑位返回划分点。递归主函数QuickSort接收low和high若区间长度大于 1 则划分并递归处理左右子区间。注意while循环中的和保证了相等的元素不会陷入无限交换但也因此可能使相等元素分布不均不过这并不影响正确性。2.3 运行推演初始数据4 6 3 2 8 0 1 10 5 4状态日志每次划分后的数组状态以 4 为基准划分后: 1 0 3 2 4 8 6 10 5 4 以 1 为基准划分后: 0 1 3 2 4 8 6 10 5 4 以 3 为基准划分后: 0 1 2 3 4 8 6 10 5 4 以 8 为基准划分后: 0 1 2 3 4 4 6 5 8 10 以 4 为基准划分后: 0 1 2 3 4 4 6 5 8 10 以 6 为基准划分后: 0 1 2 3 4 4 5 6 8 10 0 1 2 3 4 4 5 6 8 10步骤解析 第一轮以首个元素4为基准。右指针从尾端向左找到4索引9处4停止但继续向左找到1不大于4将1填到左坑索引0左指针向右找到64填入右坑……最后基准4归位到索引4左侧全部 4右侧全部 4。后面递归直至全数组有序。日志清晰展现了分治的过程和基准逐步归位的工作方式。2.4 复杂度分析时间复杂度最好/平均每次划分将序列均分递归深度为log n \log nlogn每层操作总和O ( n ) O(n)O(n)总时间O ( n log n ) O(n \log n)O(nlogn)。最坏每次划分极不平衡如原序列已有序且始终取首元素为基准递归深度退化为n nn复杂度O ( n 2 ) O(n^2)O(n2)。空间复杂度 主要由递归调用栈深度决定。最好/平均O ( log n ) O(\log n)O(logn)最坏O ( n ) O(n)O(n)。稳定性 不稳定。划分过程中的远距离填坑交换会改变相同元素的相对顺序。下一篇我们将进入选择排序的世界剖析简单选择排序与堆排序敬请期待。
