我是少侠露飞。学习塑造人生，技术扭转世界。
开场白
疾速排序号称最优雅的算法之一，在开发中可能用得不算多，然而在一些场景下还是很杰出的。最要害的是，各大厂面试官都爱问啊，你说要不要好好把握吧。
而后就是网上很多快排的代码和解说，少侠发现很多人本人压根都没搞清楚，代码的边界不清，扔进去一执行就报数组越界异样；要么就是一些人模仿的快排过程都是错的，这让真心想学习的人不免心累。所以少侠决定写一篇记录之，解说未必是最好的，但代码肯定是正确的。
原理及排序过程
原理
合成：快排的外围就是首先选定一个主元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); } }小结
本篇参考书籍《算法导论》。下期还会写篇对于堆排序的博客，敬请期待，也欢送点赞、关注。咱们下期再见。