再也不用担心快排写错了

普通介绍快排的资料，在进行partition的时候，经常是使用两个“指针”i和j：

1. 从前往后扫描，遇到比比较值大的就停下；
2. j从后往前扫描，遇到比比较值小的就停下；
3. 然后交换i，j两个对应的值
4. 若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]的性质。