【数据结构与算法】死磕排序算法：面试官最爱问的那些排序（下篇）

前言：欢迎来到排序算法的进阶篇！在上篇中，我们掌握了四大基础排序。但是在面试字节、阿里、腾讯等大厂时，面试官往往会甩给你一句：“写个快排吧”或者“手撕一个归并/堆排序”。本篇我们将攻克这三座大山，并附带最全的复杂度对比表，看完这篇，你的排序算法面试再无盲区！

5. 快速排序 (Quick Sort) ⭐️大厂必问⭐️

💡 通俗理解：
快排运用了分治思想 (Divide and Conquer)。你是一个班长，要给全班按身高排队。你随便抓一个同学（通常是第一个）作为“标杆”（Pivot）。然后对剩下的人喊口令：“比标杆矮的去左边，比标杆高的去右边！”。之后你对左右两堆人再让副班长重复这个操作，直到每堆只有1个人，整个队伍就排好了。

⏱ 面试必背核心点：

• 时间复杂度：平均O(Nlog⁡N)O(N \log N)O(NlogN)，最坏情况退化为O(N2)O(N^2)O(N2)（当数组已经有序，且你总是选第一个当标杆时）。
• 空间复杂度：最好O(log⁡N)O(\log N)O(logN)（递归栈），最坏O(N)O(N)O(N)。
• 稳定性：不稳定。

💻 Java 核心实现：

publicvoidquickSort(int[]arr,intleft,intright){if(left>=right)return;// 1. 找一个基准值，划分区域intpivotIndex=partition(arr,left,right);// 2. 递归对左半边排序quickSort(arr,left,pivotIndex-1);// 3. 递归对右半边排序quickSort(arr,pivotIndex+1,right);}// 核心划分逻辑：双指针法privateintpartition(int[]arr,intleft,intright){intpivot=arr[left];// 选第一个元素作为基准inti=left,j=right;while(i<j){// 先从右边找比 pivot 小的while(i<j&&arr[j]>=pivot)j--;// 再从左边找比 pivot 大的while(i<j&&arr[i]<=pivot)i++;// 交换这两个元素if(i<j){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}// 最后把基准值放到它该在的地方（i的位置）arr[left]=arr[i];arr[i]=pivot;returni;}

6. 归并排序 (Merge Sort)

💡 通俗理解：
同样是分治法，但归并排序思路更具结构感。你可以把它想象成“打淘汰赛然后再合并”。把一个长数组从中间劈成两半，两半再劈，一直劈到长度为 1。接下来开始“合并”：把两个已经排好序的短数组，合并成一个长的有序数组。合并时，只需要两个指针在两个数组开头比大小，谁小就先把谁揪出来。

⏱ 面试必背核心点：

• 时间复杂度：非常稳定，不管怎样都是O(Nlog⁡N)O(N \log N)O(NlogN)。
• 空间复杂度：O(N)O(N)O(N)（因为合并的时候需要借助一个额外的临时数组）。
• 稳定性：稳定（也是性能极高的高级算法中极少数稳定的！）。

💻 Java 核心实现：

publicvoidmergeSort(int[]arr,intleft,intright){if(left>=right)return;intmid=left+(right-left)/2;// 防溢出// 分：将左边拍好，右边排好mergeSort(arr,left,mid);mergeSort(arr,mid+1,right);// 治：合并两个有序数组merge(arr,left,mid,right);}privatevoidmerge(int[]arr,intleft,intmid,intright){int[]temp=newint[right-left+1];// 临时数组inti=left,j=mid+1,k=0;// 比较合并while(i<=mid&&j<=right){temp[k++]=arr[i]<=arr[j]?arr[i++]:arr[j++];}// 把左/右半边剩下的清空while(i<=mid)temp[k++]=arr[i++];while(j<=right)temp[k++]=arr[j++];// 拷贝回原数组for(intp=0;p<temp.length;p++){arr[left+p]=temp[p];}}

7. 堆排序 (Heap Sort)

💡 通俗理解：
堆排序其实是利用了“完全二叉树”的数据结构（大根堆中，父亲永远大于等于孩子）。
首先，我们把数组整理成一个大根堆（此时最大的元素就在堆顶，即数组的第0个位置）。
然后我们把堆顶（最大的数）和数组最后一个元素交换，这个时候最大的数就沉底了。把最后一个元素排除在外，对剩下的树再进行一次调整，让它变为新的大根堆。重复这个动作，直到所有元素排好。

⏱ 面试必背核心点：

• 时间复杂度：总是O(Nlog⁡N)O(N \log N)O(NlogN)（因为建堆是O(N)O(N)O(N)，每次调整是O(log⁡N)O(\log N)O(logN)）。
• 空间复杂度：O(1)O(1)O(1)（原地排序，无需额外数组）。
• 稳定性：不稳定。

💻 Java 核心实现：

publicvoidheapSort(int[]arr){if(arr==null||arr.length<2)return;// 1. 构建大顶堆 (从最后一个非叶子节点开始向下调整)for(inti=arr.length/2-1;i>=0;i--){heapify(arr,arr.length,i);}// 2. 排序过程：把最大的放在后面，重新调整剩余部分for(inti=arr.length-1;i>0;i--){// 交换堆顶（最大值）和当前最后一位inttemp=arr[0];arr[0]=arr[i];arr[i]=temp;// 把剩余的部分 i 再次调整为大顶堆heapify(arr,i,0);}}// 调整为大顶堆的函数 (下沉操作)privatevoidheapify(int[]arr,intn,inti){intlargest=i;// 初始化最大值为根intleft=2*i+1;// 左孩子intright=2*i+2;// 右孩子if(left<n&&arr[left]>arr[largest])largest=left;if(right<n&&arr[right]>arr[largest])largest=right;if(largest!=i){inttemp=arr[i];arr[i]=arr[largest];arr[largest]=temp;// 递归向子树去调整heapify(arr,n,largest);}}

🎯 终极归纳：面试常备武功秘籍

为了方便大家强记，请直接把下表截个图，刻在脑子里：

面试秒答话术：
“在所有的高阶排序算法中，如果对稳定性有要求，我会选择归并排序，但它会占用额外的O(N)O(N)O(N)空间；如果对时间和空间的综合考量较高，快速排序在平均情况下效率极高，因此应用最广；如果是在海量数据中求 Top K 问题，堆排序则是当仁不让的最优解。”

祝大家顺利撕穿手撕代码，拿到心仪的 Offer！