引言：
快速排序和归并排序是面试当中常常被问到的两种排序算法，在研究过数据结构所有的排序算法后，个人认为最复杂的当属快速排序。从代码量上来看，快速排序并不多，我之所以认为快排难以掌握是因为快排是一种递归算法，同时终止条件较多。如果你刚刚把快排的思路整理过一遍可能觉得不难，然而一个月之后呢？
面试要求的是临场发挥，如果不是烂熟于心，基本就卡壳了。在面试官眼里，你和那些完全不懂快速排序算法的菜逼是一样的，也许实际上你可能私底下已经理解很多遍了，然而并没卵。所以当下问题就是，如何将快排烂熟于心？我觉得记忆一个算法应当在理解的基础上，当你心里面把所有终止和判断条件都一清二楚之后，手写快排就不是件难事了。
源代码：
public static void main(String[] args) { int[] nums = new int[] { 2, 1, 3, 5, 0 }; QuickSort(nums, 0, nums.length - 1); for (int i : nums) { System.out.println(i); } } static void QuickSort(int[] nums, int start, int end) { if (start >= end) { return; } int i = start; int j = end; int key = nums[i]; while (i < j) { while (i < j && nums[j] >= key) { j--; } nums[i] = nums[j]; while (i < j && nums[i] <= key) { i++; } nums[j] = nums[i]; } nums[i] = key; QuickSort(nums, start, i - 1); QuickSort(nums, i + 1, end); }
思路整理：
我想，对于大多数学过数据结构的人来说，上面代码的大体思路应该是没有什么问题的，如果有问题那你是不是要好好考虑下重学一遍数据结构了。
这里我从几个判定条件入手来捋一捋算法思路：
判定条件1 while (i < j && nums[j] >= key) 中的 i < j
来看这个例子，假设我们要对 4 2 1 6 进行排序，即待排序数组 nums= {4,2,1,6}； 快速排序的步骤大体是这样的：
4 2 1 6 | 4 ----> 4 2 1 6 | 4 ----> 1 2 1 6 | 4 ----> 1 21 6 | 4 ----> 1 2 1 6 | 4 ----> 1 2 4 6 | 4（跳出循环，nums[i] = temp; ）
在这里，我们用蓝色代表i指向的元素，红色代表j指向的元素，橙色红色代码low和high相遇了，即 i == j，而|号后边的数字4代码选取的基准元素（默认是数组第一个数字）。
所以，在移动low和high的过程中，终止条件就是low==high，即他们相遇了，如果我们使用i <= j 的话，我们的i指针将会指向6的位置，然后变成4，造成数据的错乱。
判定条件2 while(i < j ){}
条件1中说了，i 和 j 不能相遇。但是为什么外面还要设置一层循环呢？咱们再看一个例子：
4 2 5 7 2 3 1 6 | 4 ----> 4 2 5 7 2 3 1 6 | 4 ----> 1 2 5 7 2 3 1 6 | 4 ----> 1 2 5 7 2 3 1 6 | 4 ----> 1 2 5 7 2 3 1 6 | 4 ----> 1 2 5 7 2 3 5 6 | 4
到这里，读者可以考虑一下如果没有外面这层while循环，下一步干嘛？没错，会这样执行1 2 4 7 2 3 5 6 | 4，但是这个数组还没有遍历完啊! 并且说好的4左边的全部比4小，4右边的全部比4大的呢？
因此，如果low和high没有相遇，就应该让它们一直遍历下去！
判定条件3 while (i < j && nums[j] >= key) 中的 nums[j] >= key
有没有想过为什么是 >= 呢？ 如果换成 > 会是什么结果？ 我可以明确的告诉你，把等号去掉就会死循环了！是不是倒吸一口凉气？我想，任何一个程序员应该都不敢轻视任意一个边界条件，所以即便是一个等号也要认真考半天，为什么要等号，可以不可以去掉？我们继续上个例子：
1 2 1 1 3 -5 0 | 1 ----> 0 2 1 1 3 -5 0 | 1 ----> 0 2 1 1 3 -5 2 | 1 ----> 0 2 1 1 3 -5 2 | 1 ----> 0 -5 1 1 3 -5 2 | 1 ----> 0 -5 1 1 3 -5 2 | 1 ----> 0 -5 1 1 3 1 2 | 1，好了，到了这里读者再往后推算几步，看看有什么发现？是不是一直在做反复赋值的死循环？
因为从 i < j一直满足， 而 nus[j] > key 和 nums[i] < key 一直都不满足，所以i 和 j 一直都不会移动了，所以自然就死循环了！
这个时候，只有把>和<修改成>=和<=，low和high才会继续移动下去！左边的数应当是小于或等于基准元素，右边的数应当是大于等于基准元素的值才对！！！！
好了，整个快排梳理就到这儿了，通过反复梳理记忆，快排一定会烂熟于心！
