老程序员回炉补基础一排序算法——从冒泡到快排的回归之旅写在前面当年43岁非科班出身做了多年架构师。框架、中间件、分布式系统这些上层的东西玩得很熟。2023年夏天我决定从零开始把大学里欠的课一门一门补回来。这是我5个月学习过程的真实记录。为什么老程序员要补算法做架构久了容易产生一种错觉我懂设计模式、懂微服务、懂高并发算法那东西早就忘光了也无所谓。但真相是——不懂排序你无法理解数据库索引为什么用B树而不是二叉查找树不懂递归你无法理解分库分表策略的本质不懂动态规划你无法做出最优的资源调度决策算法不是面试的敲门砖它是架构师思维的地基。我的排序练习框架我设计了一个统一的接口所有排序算法都实现它publicinterfacesortbase{publicvoidsort(int[]array);}测试类通过接口引用随时切换排序实现sortbase objnewbubbleSort();// 换一行代码就能切换算法obj.sort(arr);作为架构师即使写练习代码抽象的习惯也改不掉。一、冒泡排序Bubble Sort学习时间2023年10月25日这是大多数人学的第一个排序算法也是我重学的起点。publicclassbubbleSortimplementssortbase{publicvoidsort(int[]array){for(inti0;iarray.length;i){booleanflagfalse;for(intj0;jarray.length-i-1;j){if(array[j]array[j1]){inttmparray[j];array[j]array[j1];array[j1]tmp;flagtrue;}}if(!flag)break;// 没有交换提前退出}}}我的理解冒泡排序的核心就是相邻元素两两比较大的往后冒。有两个优化点flag标志位如果某一轮没有发生任何交换说明数组已经有序直接退出。最好情况从 O(n²) 降到 O(n)。内层循环边界array.length - i - 1每轮结束后最大的元素已经冒到最后了下一轮不需要再比较。复杂度情况时间复杂度空间复杂度稳定性最好O(n)O(1)稳定最坏O(n²)O(1)稳定二、选择排序Selection Sort学习时间2023年9月25日publicclassSelectSortimplementssortbase{publicvoidsort(int[]array){intindex0;for(inti0;iarray.length;i){indexi;for(intji1;jarray.length;j){if(array[index]array[j]){indexj;}}inttemparray[i];array[i]array[index];array[index]temp;}}}我的理解选择排序的思路很直觉每轮从未排序区间中找出最大或最小的放到已排序区间的末尾。我这里写的是降序排列找最大的放前面。说实话重写的时候发现array[index] array[j]这个比较方向我一开始写反了——这也说明有些细节只有手写一遍才能真正记住。复杂度情况时间复杂度空间复杂度稳定性任何O(n²)O(1)不稳定选择排序是不稳定的比如[5, 5, 3]第一轮交换后第一个5和第二个5的相对顺序就变了。三、插入排序Insertion Sort学习时间2023年9月25日publicclassinsertSortimplementssortbase{Overridepublicvoidsort(int[]array){if(array.length1)return;for(inti1;iarray.length;i){inttmparray[i];intji-1;for(;j0;--j){if(array[j]tmp)array[j1]array[j];// 元素后移elsebreak;}array[j1]tmp;// 插入到正确位置}}}我的理解插入排序就像打扑克牌拿到一张新牌从右往左找到合适的位置插进去。关键点在于元素后移而不是交换。很多人写插入排序时习惯用 swap但真正的插入应该是先保存待插入元素把比它大的都往后挪一位最后一次性插入。这样减少了赋值次数。对于近乎有序的数组插入排序非常快接近 O(n)。这也是为什么很多高级排序如 TimSort在小区间或近乎有序时会退化为插入排序。复杂度情况时间复杂度空间复杂度稳定性最好O(n)O(1)稳定最坏O(n²)O(1)稳定四、希尔排序Shell Sort学习时间2023年10月16日publicclassshellSortimplementssortbase{Overridepublicvoidsort(int[]array){intgeparray.length;do{gepgep/2;shell(array,gep);}while(gep1);}privatevoidshell(int[]arr,intd){intlenarr.length;for(intid;ilen;i){intji-d;inttemparr[i];if(arr[j]arr[jd]){for(;j0temparr[j];j-d){arr[jd]arr[j];}arr[jd]temp;}}}}我的理解希尔排序是插入排序的升级版。思路是先让数组宏观上有序再逐渐缩小步长最后步长为1时就是标准的插入排序。为什么比纯插入排序快因为插入排序对无序数组的效率很低但如果数组基本有序插入排序近乎 O(n)。希尔排序通过大步长的预排序让数组在最后做插入排序时已经基本有序了。我用了最简单的步长序列gep / 2。更优的步长序列如 Hibbard、Sedgewick可以进一步提升性能。复杂度步长序列时间复杂度空间复杂度稳定性n/2O(n²)O(1)不稳定五、归并排序Merge Sort学习时间2023年9月25日我写了两个版本mergeSort和myMerge这里展示更清晰的myMerge版本publicclassmyMergeimplementssortbase{Overridepublicvoidsort(int[]array){int[]tempnewint[array.length];mergeSort(array,temp,0,array.length-1);}publicvoidmergeSort(int[]array,int[]temp,intbegin,intend){if(beginend)return;intmid(endbegin)/2;mergeSort(array,temp,begin,mid);mergeSort(array,temp,mid1,end);mergeArray(array,temp,begin,mid1,end);}publicvoidmergeArray(int[]array,int[]temp,intbegin,intmid,intend){intminAbegin;intminBmid;for(intibegin;iend;i){if(minAmid){temp[i]array[minB];minB;}elseif(minBend){temp[i]array[minA];minA;}else{if(array[minA]array[minB]){temp[i]array[minA];minA;}else{temp[i]array[minB];minB;}}}System.arraycopy(temp,begin,array,begin,end-begin1);}}我的理解归并排序是分治思想的经典体现把数组一分为二分别排序然后合并两个有序数组。合并merge是核心。两个指针分别指向两个子数组每次取较小的那个放入临时数组。有一个细节temp数组在递归外部只创建一次避免在每层递归中反复创建数组造成性能损耗。复杂度情况时间复杂度空间复杂度稳定性任何O(n log n)O(n)稳定归并排序是唯一一个在最坏情况下也能保证 O(n log n) 的稳定排序Java 中对对象排序用的TimSort就是归并排序的变种。六、快速排序Quick Sort学习时间2024年1月8日这是我这批练习的最后一篇代码publicclassquickSortimplementssortbase{publicvoidsort(intarray[]){quick(array,0,array.length-1);}publicvoidchange(intarray[],inti,intj){inttemparray[i];array[i]array[j];array[j]temp;}publicvoidquick(intarray[],intbegin,intend){if(beginend){intstartdataarray[begin];intibegin;intjend1;while(true){while(iendarray[i]startdata){}while(jbeginarray[--j]startdata){}if(ij){change(array,i,j);}else{break;}}change(array,begin,j);quick(array,begin,j-1);quick(array,j1,end);}}}我的理解快排是最常被面试官问到的排序算法也是我之前最怕被问到的。核心是partition分区选一个基准值pivot把比它小的放左边比它大的放右边。我的实现用了经典的左右指针法取第一个元素作为 pivoti从左往右找比 pivot 大的j从右往左找比 pivot 小的交换i和j的元素当i和j相遇时把 pivot 放到j的位置注意i初始化为beginj初始化为end 1配合i和--j的前缀自增/自减先移动再比较。复杂度情况时间复杂度空间复杂度稳定性最好O(n log n)O(log n)不稳定最坏O(n²)O(n)不稳定快排最坏情况出现在数组已经有序时每次 pivot 都选到最大或最小值。工程上通常用三数取中来优化 pivot 的选择。七、堆排序Heap Sort学习时间2023年11月20日publicclassmyHeapSortimplementssortbase{Overridepublicvoidsort(int[]array){intendarray.length-1;// 建大顶堆for(inti(end-1)/2;i0;i--){buildHeap(array,i,end);}// 每次把堆顶最大值换到末尾再调整堆inttmp;for(inti0;iend;i){tmparray[0];array[0]array[end-i];array[end-i]tmp;buildHeap(array,0,end-i-1);}}publicvoidbuildHeap(int[]array,intbegin,intend){inttmparray[begin];for(intibegin*21;iend;i2*i1){if(iendarray[i]array[i1]){i;// i 指向左右孩子中较大的那个}if(array[i]tmp){array[begin]array[i];begini;}else{break;}}array[begin]tmp;}}我的理解堆排序是最让我有成就感的算法。它利用了完全二叉堆的性质建堆从最后一个非叶子节点(end-1)/2开始从下往上逐个下沉调整。这是一个 O(n) 的过程很多人直觉以为是 O(n log n)但实际上从底向上构建是线性的。排序把堆顶最大值和最后一个元素交换堆的大小减1再对堆顶做一次下沉调整。重复 n-1 次就排好了。buildHeap中的技巧在于先保存后放置先把待调整节点的值存到tmp然后沿着较大的孩子一路往上覆盖最后把tmp放到最终位置。这比每次 swap 减少了赋值次数。复杂度情况时间复杂度空间复杂度稳定性任何O(n log n)O(1)不稳定堆排序最大的优势是原地排序且最坏也是 O(n log n)但实际应用中由于缓存不友好跳跃式访问数组性能通常不如快排。七大排序对比总结排序算法平均时间最好时间最坏时间空间稳定特点冒泡排序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^1.3)O(n)O(n²)O(1)不稳定插入排序的优化版归并排序O(n log n)O(n log n)O(n log n)O(n)稳定唯一稳定且O(n log n)快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定实践中最快堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定原地且最坏O(n log n)一个43岁架构师的反思写完这7个排序算法我花了大约2个月2023年9月~11月。最大的感悟是算法不是背出来的是写出来的。看懂和写出来之间隔着一道鸿沟。选择排序的稳定性问题看了无数遍书都记不住手写一遍就永远忘不掉了。作为架构师理解这些基础算法让你在做技术选型时有底气。比如为什么 Java 用 TimSort归并插入而不是单纯的快排因为它需要稳定性。下一篇预告《老程序员回炉补基础二手写链表、栈、队列——不依赖任何集合框架》