再也不用担心快排写错了
普通介绍快排的资料，在进行partition的时候，经常是使用两个“指针”i和j：
- 从前往后扫描，遇到比比较值大的就停下；
- j从后往前扫描，遇到比比较值小的就停下；
- 然后交换i，j两个对应的值
- 若i >= j，则结束，否则进入1
这样理解也不是很难，关键就在于写的时候很容易出错，反正我基本很难一次就写对。
上面的partition的思想是：首先假设比较值为V，数组是arr，下标从start开始，end结束（即end下标是合法的），那么在下标为[start, i)（左闭右开区间，后面也需注意）中的数都是小于比较值的（比较值可选下标为start或end的），下标为(j, end]的数都是大于比较值的然后找到arr[i] > V，arr[j] < V，然后交换这两个值，以维护前面说得那两个区间的性质。
不容易写错的快排
前面不用看也没关系，因为下面要介绍的才是重点。
下面要介绍的方法，稍微有点不同，但是基本思路还是相似的。先看代码：
import java.util.Random;
public class Qsort {
private static Random random = new Random();
private static void swap(int[] arr; int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
private static partition(int[] arr, int start, int end) {
int lc = start - 1;
// 此处的swap，是为了随机选取中间的值作为比较值，这样要比直接选取arr[start]或arr[end]性能要好。
swap(arr, end, random.nextInt(end + 1 - start) + start);
for (int i = 0; i < end; i++) {
if (arr[i] < arr[end]) {
lc ++;
if (i != lc) { // 这个判定可以不要，i和lc相等时，交换和不交换没区别，只不过稍微耗点时间，最好还是加上
swap(arr, i, lc);
}
}
}
lc ++;
swap(arr, lc, end);
return lc;
}
public static void sort(int[] arr, int start, int end) {
if (start >= end) return; // 递归结束条件，这个应该很好理解
int mid = partition(arr, start, end);
// mid的值就是上一次partition后比较值的位置
// 小于arr[mid]的数全部都在mid前面，大于等于arr[mid]的数全在mid的后面
sort(arr, start, mid - 1);
sort(arr, mid + 1, end);
}
}
快排的递归还是很好理解和书写的，关键就在与partition函数的书写。
首先明确partition的功能：
返回一个下标mid，使得小于arr[mid]的数的下标都小于mid，大于arr[mid]的数的下标都大于mid。对于等于arr[mid]的数的下标是小于还是大于mid，取决于具体的实现，我们会在代码中进行说明。
那么对于前面实现的partition函数，我们先将代码单独拿出来：
private static partition(int[] arr, int start, int end) {
int lc = start - 1;
// 此处的swap，是为了随机选取中间的值作为比较值，这样要比直接选取arr[start]或arr[end]性能要好。
swap(arr, end, random.nextInt(end + 1 - start) + start);
for (int i = 0; i < end; i++) {
if (arr[i] < arr[end]) { // 这样的实现，等于比较值的数的下标就比mid要大，若判定条件加个等号，则等于比较值的数的下标就比mid要小
lc ++;
if (i != lc) { // 这个判定可以不要，i和lc相等时，交换和不交换没区别，只不过稍微耗点时间，最好还是加上
swap(arr, i, lc);
}
}
}
lc ++;
swap(arr, lc, end);
return lc;
}
需要知道的变量有start， end，lc和i。
前面两个很容易理解，就是要对arr数组中[start, end]进行操作。lc和i需要在循环过程中来讲解：
我们可以看到，lc在arr[i] < arr[end]的时候，会自加一次，这样，当这个条件第一次成立的时候，lc就变成了start，若此时lc和i不相等，则会进行一次交换，这样交换之后，一定就有arr[lc] < arr[end]，我们可以观察到，每一次lc自加，然后经过swap，一定有arr[lc] < arr[end]，所以我们可以得出结论：
- 区间[start, lc]中的数（若存在的话），一定是小于arr[end]的。
那么剩下的区间呢？
剩下的区间，可以分为[lc + 1, i]，[i + 1, end - 1]。
对于[i + 1, end - 1]，很明显，都是还未进行比较的数，他们和arr[end]的值大小关系还没有确定。
对于[lc + 1, i]，这些数已经和arr[end]比较过了，小于arr[end]的数，已经在[start, lc]中了，因此，下标为[lc + 1, i]区间中的数，是大于等于arr[end]的数。这样，当for循环完成时，有：
- 下标为[start, lc]中的数都是小于arr[end]的
- 小标为[lc + 1, end - 1]的数都是大于等于arr[end]的
最后将位置lc + 1和end处的数相交换，然后返回lc + 1就行了。
维护下标为[start, lc]的数是小于等于arr[end]的关键就在于lc自加后进行一次swap。
需要注意的是，return前的lc自加和swap是为了找到arr[end]真正的位置，并交换过去，然后将位置返回，而不是维护下标为[start, lc]的数小于arr[end]的性质。
