引言：“哪个算法最能体现你的代码功底？”
十有八九的面试官会问你排序。而十有八九，他希望听到的不是冒泡，而是快速排序！它不仅效率高，更是“分而治之”思想的完美体现。今天，我们就来彻底征服它，让你在面试和工作中都能游刃有余。
一、 动图秒懂：快速排序在做什么？
想象一下你是一个高效的仓库管理员，要对一堆乱序的箱子排序。快排的做法是：
挑个基准：从数组中随意挑一个元素，称为“基准”（pivot）。
分区操作：重新排列数组，所有比基准小的都放到它左边，比基准大的都放到它右边（等于的放哪边都行）。操作结束后，基准就处于了它最终的正确位置！
递归治之：递归地将小于基准的子序列和大于基准的子序列进行快速排序。
（此处插入一张经典的快速排序分区动图，展示元素如何围绕基准值移动）
看，递归到最后，整个数组就自然有序了！这就是“分治”的魅力。
二、 核心揭秘：关键的“分区”过程
分区是整个快排的灵魂，这里介绍两种最主流、最易懂的方法，让你彻底搞懂。
方法一：挖坑填数法（Hoare版，易于理解）
这种方法超级直观，就像在地上挖坑填坑。
def quick_sort(arr, low, high):
if low < high:
# 分区操作，返回基准值的正确位置
pi = partition(arr, low, high)
# 递归排序左右两部分
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
def partition(arr, low, high):
# 选取第一个元素作为基准
pivot = arr[low]
while low < high:
# 从右向左找第一个小于pivot的数
while low < high and arr[high] >= pivot:
high -= 1
# 找到后，把它填到左边的“坑”里
arr[low] = arr[high]
# 从左向右找第一个大于等于pivot的数
while low < high and arr[low] < pivot:
low += 1
# 找到后，把它填到右边的“坑”里
arr[high] = arr[low]
# 循环结束，low==high，这就是pivot的正确位置
arr[low] = pivot
return low过程解析：
先把基准数pivot挖走（arr[low]成了第一个坑）。
从右开始，找一个比pivot小的数，挖出来，填到左边的坑里。
再从左开始，找一个比pivot大的数，挖出来，填到右边的坑里。
重复直到左右指针相遇，把pivot填回最后的坑中。
方法二：指针交换法（Lomuto版，代码简洁）
这是另一种常见写法，逻辑更紧凑。
def partition_lomuto(arr, low, high):
pivot = arr[high] # 选择最后一个元素作为基准
i = low - 1 # i指向小于pivot区域的最后一个元素
for j in range(low, high):
# 如果当前元素小于等于基准
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i] # 把它交换到小于区域
# 最后，将基准值放到正确位置
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1过程解析：
它维护了两个指针，i 和 j。
i 始终指向小于基准区域的边界。
j 不断向右扫描，遇到小的就把它扔到 i 的右边，然后 i 向右扩一步。
最后把基准值放到 i+1 的位置。
两种方法对比：
挖坑法：交换次数一般更少，理解起来需要一点空间想象。
指针法：代码超级清晰，是教科书上的常客。
三、 为什么它是“快速”排序？
快排的平均时间复杂度是 O(n log n)，最坏情况（如数组已有序）是 O(n²)。但为什么它在实践中如此之快？
缓存友善：它的操作是原地进行的，主要是在连续数组上进行比较和交换，能很好地利用CPU缓存。
常数因子小：虽然和归并排序都是O(n log n)，但快排内部的常数操作更少，所以在数据量巨大时，优势明显。
如何避免最坏的 O(n²)？
随机化：不总选第一个或最后一个元素作为基准，而是随机选择一个。这能将最坏情况的发生概率降到极低。
三数取中法：选取头、中、尾三个元素的中位数作为基准，能有效避免在已排序数组上的性能退化。
四、 面试与工作实战要点
面试官考什么？
手写代码能力：务必掌握其中一种分区方法。
理解深度：能说清分区的过程、时间复杂度和优化策略。
思想延伸：“分治”思想还能解决哪些问题？（如：归并排序、二叉树遍历等）
工作中的应用：
绝大多数编程语言的标准库排序函数都借鉴了快排的思想（如C++的std::sort，Java的Arrays.sort）。理解它，你就能理解为什么这些内置排序如此高效。
结语：
快速排序，以其名字中的“快速”二字，数十年来一直是效率与智慧的代名词。掌握它，不仅是掌握一个算法，更是掌握一种“分而治之，逐个击破”的高效问题解决思维。
互动话题：
你在面试中被问过快排吗？是让你手写代码还是讲解思路？在评论区分享你的经历吧！
彩蛋：
1.原理
快速排序采用”分而治之递归排序”的思想，对于一组数据，选择一个基准元素（base），列如选择第一个、中间位置元素或最后一个元素，通过第一轮扫描，比base小的元素都在base左边，比base大的元素都在base右边，然后再用同样的方法递归排序数组的左右两个子部分，直到序列中所有数据均有序为止。
2.代码
以下使用Java代码作为示例：
//测试快速排序的函数
public void testQuickSort(){
//进行排序的数组样例
int[] data = new int[]{80, 2, 67, 32, 57, 13, 48, 1, 60, 100};
quickSort(data,0,data.length-1);
}
/**
快速排序主函数
arr：要排序的数组
left：排序数组左边界索引
right：排序数组右边界索引
*/
public void quickSort(int arr[], int left, int right) {
if (left < right) {
//算出基准元素索引值index
int index = partition(arr, left, right);
//对低于index索引的数组递归排序
quickSort(arr, left, index - 1);
//对高于index索引的数组递归排序
quickSort(arr, index + 1, right);
}
}
//算出基准元素索引值，此索引值左侧值都小于基准元素值，此索引值右侧值都大于基准元素值
public int partition(int[] num, int left, int right) {
if (num == null || num.length <= 0 || left < 0 || right >= num.length) {
return0;
}
//获取数组基准元素的下标
int prio = num[left + (right - left) / 2];
//从两端交替向中间扫描
while (left <= right) {
while (num[left] < prio)
left++;
while (num[right] > prio)
right--;
if (left <= right) {
//将不符合条件的元素值交换位置并继续扫描
swap(num, left, right);
left++;
right--;
}
}
returnleft;
}
//交换元素
public void swap(int[] num, int left, int right) {
int temp = num[left];
num[left] = num[right];
num[right] = temp;
}
暂无评论内容