快速排序

划分

定义：选择一个元素a将一个数组分成2部分，比a小的元素都在a的前面，不比a小的都在a之后，同时返回划分完成a的下标

排序过程中，这种划分的好处是划分后的前后两部分元素之间就不需要再比较了，后半部分一定比前半部分大，减少了比较的次数。

划分的实现有很多种，移数组[6, 3, 4, 7, 2, 10]按6进行划分为例

区间法

将数组分成<6跟>6两个区间，前半区间一开始是空的，下标是-1

注意一开始我们将6跟10做了交换，将6放到了最后一个元素，这是为了方便最后得到6最终的位置。

   static int partition(int a[], int l, int r) {
        int keyValue = a[r];
        int smallIndex = l - 1;
        for(int i = l; i < r; i++) {
            if(a[i] < keyValue) {
                smallIndex++;
                int t = a[smallIndex];
                a[smallIndex] = a[i];
                a[i] = t;
            }
        }
        int t = a[++smallIndex];
        a[smallIndex] = keyValue;
        a[r] = t;
        return smallIndex;
    }

双指针挖坑法

int partition(int a[], int l, int r) {
   int p = a[l];
   int hole = l;
   while(l < r) {
      while(l < r && a[r] >= p) r--;
      a[hole] = a[r];
      hole = r;
      while(l < r && a[l] <= p) l++;
      a[hole] = a[l];
      hole = l;
   }
  a[hole] = p;
  return hole;
}

颜色分类

https://leetcode.cn/problems/sort-colors/
这题其实就是将数组分成 >x、=x、<x三个区

    public void sortColors(int[] nums) {
        if(nums == null) return;
        int x = 1;
        int less = -1, more = nums.length, cur = 0;
        while(less < more && cur < more) {
            // < x
            if(nums[cur] < x) {
                swap(nums, ++less, cur++);
            }
            // =x
            else if(nums[cur] == x) {
                cur++;
            }
            // > x
            else {
                // cur不动，交换过来还需要比较
                swap(nums, cur, --more);
            }
        }
    }

    void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

第K大数

https://leetcode.cn/problems/kth-largest-element-in-an-array/
随便选一个数x一次划分后都能分成>x跟<x两部分序列已经x最终在数组的下标idx，那么只需要比较idx跟k的关系就能确定后续划分的序列是哪一部分，每次都能减少1/2的数据量所以时间复杂度为O(n)

  int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length < k) {
            return -1;
        }
        int n = nums.length;
        k = n - k;
        int idx = -1, l = 0, r = n - 1;
        while(idx != k) {
            idx = partition(nums, l, r);
            if(idx < k) {
                l = idx + 1;
            } else {
                r = idx - 1;    
            }
        }
        return nums[k];
    }

快速排序

void quicksort(int a[], int l, int r) {
    if(l >= r) return;
    int m = partition(a, l, r);
    quicksort(a, l, m - 1);
    quicksort(a, m + 1, r)
}