import java.util.*;
import java.lang.*;
public class Demo {
// 非递归 using stack
public static void quickSortStack(int[] nums, int left, int right) {
if (left >= right) return;
Stack<Range> stack = new Stack<Range>();
stack.push( new Range(left, right) );
while( !stack.empty() ) {
Range curRange = stack.pop();
if (curRange.left < curRange.right) {
int pivotIdx = partition(nums, curRange.left, curRange.right);
stack.push( new Range(curRange.left, pivotIdx - 1) );
stack.push( new Range(pivotIdx + 1, curRange.right) );
}
}
}
// recursion quickSort
public static void quickSort(int[] nums, int left, int right) {
if (left < right) {
int pIdx = partition(nums, left, right);
quickSort(nums, left, pIdx - 1);
quickSort(nums, pIdx + 1, right);
}
}
public static int partition(int[] nums, int left, int right) {
// nums[left]~nums[retIdx - 1] <= nums[retIdx] <= nums[retIdx ~ right]
if (left == right) return left;
int pivot = nums[left]; // mark the leftmost value as the pivot. and store it.
int lp = left, rp = right;
while(lp < rp) {
while(lp < rp && nums[rp] >= pivot)
rp--;
nums[lp] = nums[rp]; //move the smaller value to left Range.
while(lp < rp && nums[lp] <= pivot)
lp++;
nums[rp] = nums[lp]; // move the bigger value to right Range.
}
nums[lp] = pivot;
return lp;
}
public static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
public static int partitionV2(int[] nums, int left, int right) {
int l = left;
int r = right + 1;
int pivot = nums[left];
while(true) {
while( l < right && nums[++l] < pivot )
if ( l == right ) break;
while( r > left && nums[--r] >= pivot )
if ( r == left ) break;
if (l >= r)
break;
swap(nums, l, r);
}
swap(nums, left, r);
return r;
}
//TopK问题
public static int findKthLargest(int[] nums, int k) {
return quickSelect(nums, k, 0, nums.length - 1);
}
//快速选择算法
public static int quickSelect(int[] nums, int k, int left, int right) {
if (left == right) return nums[left];
int index = partition(nums, left, right);
if ( index - left + 1 == k) {
return nums[index];
}
else if ( index - left + 1 > k ) {
return quickSelect(nums, k, left, index - 1);
}
else {
return quickSelect(nums, k - index + left - 1, index + 1, right);
}
}
public static void showArrays(int[] nums, String str) {
System.out.println("===" + str + "===");
showArrays(nums);
}
public static void showArrays(int[] nums) {
for (int i = 0; i < nums.length; i++)
System.out.printf(nums[i] + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = new int[] {1,3,2,3,4,2,7,5};
// int[] nums = new int[]{3,2,3};
showArrays(nums, "origin");
//print i-th min nubmer.
for (int i = 1; i <= nums.length; i++) {
System.out.println( i + " " + findKthLargest(nums, i) );
}
quickSortStack(nums, 0, nums.length - 1);
showArrays(nums, "quickSortStack");
}
}
class Range {
public int left;
public int right;
public Range(int left, int right) {
this.left = left;
this.right = right;
}
}