快速排序

快速排序是一种经典的排序算法，和它的名字一样，它的排序速度非常快！平均时间复杂度可以达到O(nlogn)。

1. 首先选择数组中的一个数字A
2. 遍历数组，将比A小的数移动到A的左边，将比A大的数移动到A的右边，完成后数组被分成左右两个区域，左边全部比A小，右边全部比A大
3. 对元素数量大于1的区域，执行1、2、3三个操作

大致过程如下图：

快速排序的过程，虽然不难理解，但是这里也存在几个问题：

1. 数字A该如何选择？数字A的选择其实是一件非常重的事情，数字A选的好可以使算法的时间复杂度更接近平均时间复杂度O(nlogn)，其中缘由我就不赘述了，实际中我们只需要随机选择一个就可以了，随机选择效果已经足够好了，而且很简单。

2. 选好数字A后，如何将比A小的数移动到A的左边，将比A大的数移动到A的右边？过程如下图：

public class Sort {
    // 排序数组中从索引from（包含）到索引to（不包含）范围内的数字
    public static void quickSort(int[] arr, int from, int to) {
      if (from + 1 >= to) return;
      int less = from - 1;
      int large = to;
      int mid = arr[from + new Random().nextInt(to)];
      int cur = from;
      while (cur < large) {
        if (arr[cur] < mid) {
          swap(arr, cur, less + 1);
          less++;
        }
        if (arr[cur] > mid) {
          swap(arr, cur, large - 1);
          large--;
          continue;
        }
        cur++;
      }
      quickSort(arr, from, less + 1);
      quickSort(arr, large, to);
    }


    private static void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
}