自己写的代码，记录一下。分别记录了两种partition的方法。
public class QuickSort {
public static void quickSort(int[] nums, int start, int end) {
if(start >= end) {
return;
}
int pivot = partition2(nums, start, end);
quickSort(nums, start, pivot - 1);
quickSort(nums, pivot + 1, end);
}
public static int partition(int[] nums, int start, int end) {
int pivot = start;
for(int i = start + 1; i <= end; i++) {
if(nums[i] <= nums[start]) {
pivot++;
int temp = nums[pivot];
nums[pivot] = nums[i];
nums[i] = temp;
}
}
int temp = nums[pivot];
nums[pivot] = nums[start];
nums[start] = temp;
return pivot;
}
// better partition method
public static int partition2(int[] nums, int start, int end) {
int pivot = start, i = start + 1, j = end;
while(i <= j) {
while(i <= end && nums[i] <= nums[pivot]) {
i++;
}
while(nums[j] >nums[pivot]) {
j--;
}
if(i >= j) {
break;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
i--;
int temp = nums[i];
nums[i] = nums[pivot];
nums[pivot] = temp;
return i;
}
public static void main(String[] args) {
int[] nums = new int[]{13, 6, 9, 1, 19, -21, 5};
quickSort(nums, 0, nums.length - 1);
System.out.println(nums);
}
}
//20181015
重写了partition2，上面的方法太冗余。
1. i完全可以从start开始，而不是start+1，因为nums[start]在下面也会因为和pivot相等而跳过。这样做可以避免一个错误，就是不会因为下面while的判断i<j，而跳过下面的处理。这样的话，如果数组是{1,2}，也会直接从37行开始交换{2,1}，这是显然错误的。
2. 这样的思路比较清晰，两个<的地方不用<=，显然是因为如果i和j是同一个元素，就不需要比较了，因为下面的操作是交换。
3.37行是交换j，因为j最后来到的地方必然是最后一个小于等于pivot的地方。这里用i-1也可以，但是j更清晰。
class Solution {
public int findKthLargest(int[] nums, int k) {
return find(nums, k, 0, nums.length - 1);
}
public int find(int[] nums, int k, int start, int end) {
int pivot = partition(nums, start, end);
if (k == end - pivot + 1) {
return nums[pivot];
} else if (k < end - pivot + 1) {
return find(nums, k, pivot + 1, end);
} else {
return find(nums, k - (end- pivot) - 1, start, pivot - 1);
}
}
public int partition(int[] nums, int start, int end) {
if (start >= end) {
return start;
}
int pivot = nums[start], i = start, j = end;
while (i < j) {
while (i <= end && nums[i] <= pivot) {
i++;
}
while (nums[j] > pivot) {
j--;
}
if (i > j) {
break;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// j不可能<start，因为nums[start] == pivot
int temp = nums[start];
nums[start] = nums[j];
nums[j] = temp;
return j;
}
}