划分
定义：选择一个元素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)
}
