【数据结构与算法】腾讯面试官让我模拟快排的执行过程，背好的代码竟无用武之地

我是少侠露飞。学习塑造人生，技术改变世界。

开场白

快速排序号称最优雅的算法之一，在开发中可能用得不算多，但是在一些场景下还是很出色的。最关键的是，各大厂面试官都爱问啊，你说要不要好好掌握吧。 然后就是网上很多快排的代码和讲解，少侠发现很多人自己压根都没搞清楚，代码的边界不清，扔进去一执行就报数组越界异常；要么就是一些人模拟的快排过程都是错的，这让真心想学习的人难免心累。所以少侠决定写一篇记录之，讲解未必是最好的，但代码一定是正确的。

原理及排序过程

原理

分解：快排的核心就是首先选定一个主元pivot，然后将原数组分解成两个子数组A和B，保证A中的结果小于等于pivot，B中的结果都大于等于pivot。 解决：然后针对两个子数组A和B再递归的调用，按照上步分解的逻辑进行。 合并：我们知道，归并排序最后是需要合并子数组的。但在这里，好消息是快排是原址排序，不需要合并。

排序过程

原理不难理解，但是初学者对这个过程可能还是比较模糊。这里少侠就选择一个数组，按照快排的过程一步一步展示给大家。 这里我们选择初始化数组[6,2,3,9,5,8]。 首先选择主元，怎么选呢，可以选择某一索引位置的值，也可以选择多个索引，然后取中位数的值作为主元。这里我们固定选择第一个元素为主元。

第一次分解的时候pivot=6，分解的目标就是把所有大于等于6的元素移动右边，小于等于6的元素移到左边。然后左指针i从起始位置开始，右指针j从结尾开始，循环的边界就是i<j。初始位置如下图：

每次从右边的指针判定。当右指针的值大于pivot时，右指针左移一位，直到遇到小于等于pivot的值。如下图：

当右指针的值小于pivot时，将当前值赋值给指针i对应的位置，同时i向右移动一位，如下图：

当发生上步的情况（即右指针因小于pivot而发生值的覆盖时候），需要进入该逻辑：就是开始判断左指针的元素值，如果小于pivot，就向右移动一位，直到遇到大于等于pivot的元素。

此时i移动到元素值为9的位置，也就是大于pivot，此时需要将此位置的值赋值给j位置并使得指针j左移一位，即：

注意看，此时i=j，左右指针重合，已经不满足循环边界条件(i<j)了，退出循环。但是此时i位置的值才是pivot应该在的位置，所以执行赋值操作将pivot赋值给nums[i]=pivot;得到本次分解的最终结果：

最后再对主元pivot两侧的数组{5,2,3}和{9,8}递归的调用上述过程，得到最终排序结果。

完整实现代码（Java）

public void quickSort(int[] nums) { if (nums == null || nums.length <= 1) { return; } quickSort(nums, 0, nums.length - 1); } private void quickSort(int[] nums, int left, int right) { // 左右指针没有相遇前比较各数据与主元的大小 if (left < right) { // 选择主元值 int pivot = nums[left]; // 标记左右指针 int i = left, j = right; // 一趟排序，找到比主元大的数据放在主元右侧，比主元小的值放在基元左侧 while (i < j) { // 从右往左扫描，当前值大于主元时跳过，右指针左移一位 while (i < j && nums[j] > pivot) { j--; } // 当走到这里时，意味着当前值左指针和右指针相遇，说明本趟排序结束 // 也可能是当前数据小于等于主元，此时需要将当前数据赋值给左指针对应的值，并将左指针右移一位 if (i < j) { nums[i++] = nums[j]; } // 从左往右扫描，当前值小于主元时跳过，左指针右移一位 while (i < j && nums[i] < pivot) { i++; } // 当走到这里时，意味着当前值左指针和右指针相遇，说明本趟排序结束 // 也可能是当前数据大于等于主元，此时需要将当前数据赋值给右指针对应的值，并将右指针左移一位 if (i < j) { nums[j--] = nums[i]; } } // 此时索引i的位置应该就是主元值 nums[i] = pivot; // 左侧按照相同思路递归 quickSort(nums, left, i - 1); // 右侧按照相同思路递归 quickSort(nums, i + 1, right); } }

小结

本篇参考书籍《算法导论》。下期还会写篇关于堆排序的博客，敬请期待，也欢迎点赞、关注。咱们下期再见。