思想：
使左右整体有序 找到pivot 左边小于等于pivot 右边大于等于pivot 然后左右再继续调用
有四个注意点:
- 始终是left<=right 原因在于 要不取等号的话再向下调用会有重复 quicksort(start, right) quicksort(left, end)left元素左右都被排序 导致会有stackoverflow 例子(1, 2); 所以取等号使左右彻底错开
- 从左到右找第一个大于等于pivot元素；从右向左找第一个小于等于pivot元素。之所以取等 是要尽可能使等于的元素左右分布均匀 如果不取等(1,1,1,1,1)集中在左边 不能尽可能平均下次左右元素的数量
- 最后left和right错开一位相邻，也有可能错开两位中间隔一个数 这点在quickselect最后一步讨论时比较关键
- 做题时注意是求升序还是降序
题目
- lt464 Sort O(nlogn) quick sort/merge sort
- 找第k大 215 Kth Largest Element in an Array
- heap 用最小堆 n(logk)
- quickselect O(n)
- 找前k大 544 Top k Largest Numbers 这个题有三种思路
- heap 用最小堆 n(logk)
- quickselect 找到第k大的数x 然后把大于等于x的都挑出来(具体要讨论 因为有可能有大于等于x的数) quickselect O(n) + sort O(klog(k)
- quicksort 比较巧 给原版quicksort加一个条件 start>k就不排 相当于最后只有前k个数是有序的 O(n) 到 O(nlog(n))之间
lt464. Sort O(nlogn) quick sort/merge sort
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers2(int[] nums) {
// write your code here
if(nums==null)
return;
int[] temp = new int[nums.length];
// mergesort(nums, temp, 0, nums.length-1);
quickSort(nums, 0, nums.length-1);
}
private void mergesort(int[] nums, int[] temp, int start, int end){
if(start>=end)
return;
int mid = start+(end-start)/2;
mergesort(nums, temp, start, mid);
mergesort(nums, temp, mid+1, end);
int left = start;
int right = mid+1;
int index = start;
while(left<=mid && right<=end){
if(nums[left]<nums[right]){
temp[index] = nums[left];
left++;
}else{
temp[index] = nums[right];
right++;
}
index++;
}
while(left<=mid ){
temp[index] = nums[left];
left++;
index++;
}
while(right<=end ){
temp[index] = nums[right];
right++;
index++;
}
for(int i=start; i<=end; i++){
nums[i] = temp[i];
}
}
private void quickSort(int[] nums, int start, int end){
if(start>=end)
return;
int left = start;
int right = end;
int pivot = nums[left+(right-left)/2];
while(left<=right){
while(left<=right && nums[left]<pivot)
left++;
while(left<=right && nums[right]>pivot)
right--;
if(left<=right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
quickSort(nums, start, right);
quickSort(nums, left, end);
}
}
215. Kth Largest Element in an Array
quickselect O(n)
heap O(nlogK)
class Solution {
public int findKthLargest(int[] nums, int k) {
// return heap(nums, k);
return partition(nums, k);
}
public int heap(int[] nums, int k) {
if(nums==null || k<=0 || nums.length<k)
return -1;
PriorityQueue<Integer> heap = new PriorityQueue<>(k);
for(int i=0; i<nums.length; i++){
if(heap.size()<k)
heap.offer(nums[i]);
else{
heap.offer(Math.max(nums[i], heap.poll()));
}
}
return heap.peek();
}
public int partition(int[] nums, int k) {
if(nums==null || k<=0 || nums.length<k)
return -1;
return helper(nums, k, 0, nums.length-1);
}
private int helper(int[] nums, int k, int start, int end){
if(start>=end)
return nums[start];
int left = start;
int right = end;
int mid = left+(right-left)/2;
int pivot = nums[mid];
while(left<=right){
while(left<=right && nums[left]>pivot){
left++;
}
while(left<=right && nums[right]<pivot){
right--;
}
if(left<=right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if(k<=right-start+1){
return helper(nums, k, start, right);
}
if(k>=left-start+1)
return helper(nums, k-(left-start), left, end);
return nums[right+1];
}
}
544. Top k Largest Numbers
public class Solution {
/**
* @param nums: an integer array
* @param k: An integer
* @return: the top k largest numbers in array
*/
public int[] topk(int[] nums, int k) {
// write your code here
int kth = findKthLargest(nums, k, 0, nums.length-1);
int[] result = new int[k];
int left=0;
int right = k-1;
System.out.println(kth);
for(int i=0; i<nums.length; i++){
if(nums[i]>kth){
result[left] = nums[i];
left++;
}
if(nums[i]==kth&&right>=left){
result[right] = nums[i];
right--;
}
}
Arrays.sort(result);
int start = 0;
int end = k-1;
while(start<end){
int temp = result[start];
result[start] = result[end];
result[end] = temp;
start++;
end--;
}
return result;
}
private int findKthLargest(int[] nums, int k, int start, int end){
if(start>=end)
return nums[start];
int mid = start + (end-start)/2;
int pivot = nums[mid];
int left = start;
int right = end;
while(left<=right){
while(left<=right && nums[left]>pivot){
left++;
}
while(left<=right && nums[right]<pivot){
right--;
}
if(left<=right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if(start+k-1<=right)
return findKthLargest(nums, k, start, right);
if(start+k-1>=left)
return findKthLargest(nums, k-(left-start), left, end);
return nums[right+1];
}
}
// base on heap
class Solution {
/*
* @param nums an integer array
* @param k an integer
* @return the top k largest numbers in array
*/
public int[] topk(int[] nums, int k) {
PriorityQueue<Integer> minheap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
for (int i : nums) {
minheap.add(i);
if (minheap.size() > k) {
minheap.poll();
}
}
int[] result = new int[k];
for (int i = 0; i < result.length; i++) {
result[k - i - 1] = minheap.poll();
}
return result;
}
};
// base on quicksort
import java.util.Random;
class Solution {
/*
* @param nums an integer array
* @param k an integer
* @return the top k largest numbers in array
*/
public int[] topk(int[] nums, int k) {
// Write your code here
quickSort(nums, 0, nums.length - 1, k);
int[] topk = new int[k];
for (int i = 0; i < k; ++i)
topk[i] = nums[i];
return topk;
}
private void quickSort(int[] A, int start, int end, int k) {
if (start >= k)
return;
if (start >= end) {
return;
}
int left = start, right = end;
// key point 1: pivot is the value, not the index
Random rand =new Random(end - start + 1);
int index = rand.nextInt(end - start + 1) + start;
int pivot = A[index];
// key point 2: every time you compare left & right, it should be
// left <= right not left < right
while (left <= right) {
// key point 3: A[left] < pivot not A[left] <= pivot
while (left <= right && A[left] > pivot) {
left++;
}
// key point 3: A[right] > pivot not A[right] >= pivot
while (left <= right && A[right] < pivot) {
right--;
}
if (left <= right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
left++;
right--;
}
}
quickSort(A, start, right, k);
quickSort(A, left, end, k);
}
};
