LeetCode 排序算法题型总结
快排
第一次拿起x = nums[left]，从右侧找一个比x小的数放到 lfet位置
这时右侧的right空了，再从左侧找个数放到右侧，
以此来推
直到left>=right，我们可以保证 left左侧都是严格小于x的，这时将x放到left的位置（或者这样理解，因为循环最后是nums[j] = nums[i]， 所以最后跳出循环后一定是左侧left有空位，所以放到left）
class QuickSort {
public void quickSort(int[] nums) {
if (nums == null || nums.length <= 1) return;
sort(nums, 0, nums.length - 1);
}
private void sort(int[] nums, int l, int r) {
if (l >= r) return; // 递归结束条件
int pivotIndex = partition(nums, l, r);
// 对左右两边都进行递归排序
sort(nums, l, pivotIndex - 1);
sort(nums, pivotIndex + 1, r);
}
private int partition(int[] nums, int l, int r) {
int pivot = nums[l]; // 选择最左元素作为pivot
int i = l, j = r;
while (i < j) {
while (i < j && nums[j] >= pivot) j--; // 从右找小于pivot的
nums[i] = nums[j]; // 覆盖到左边
while (i < j && nums[i] <= pivot) i++; // 从左找大于pivot的
nums[j] = nums[i]; // 覆盖到右边
}
nums[i] = pivot; // 将pivot放到最终位置
return i;
}
}
优化-三路划分
- 注意 swap(nums，i++，lt++);
- 因为 交换前 nums[it]=p，nums[i]<p，交换后 nums[i]=p这是已知的，所以i++，同时这也保证了 i>=it
class Solution {
private Random r = new Random();
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
int target = n-1-k+1;
return helper(nums, 0, n-1, target);
}
private int helper(int[] nums, int left, int right ,int target){
int x = left+ r.nextInt(right-left+1);
swap(nums, x, left);
int pivot = nums[left];
// [left,lt-1]<p, [lt,i]=p , [gt+1,right]>p
int lt = left, gt = right , i = left;
while (i<=gt) { // 保证nums[gt+1]>p, 但是gt这个位置还要判断
if (nums[i]<pivot) {
swap(nums, i++, lt++);
}else if (nums[i]>pivot) {
swap(nums, i, gt--);
}else{
i++;
}
}
if (target<=lt-1) {
return helper(nums, left, lt-1, target);
}else if (target>=gt+1) {
return helper(nums, gt+1, right, target);
}else{
return nums[lt];
}
}
private void swap(int[] nums, int a,int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}