搞了一晚上寻找第k小元素，终于弄出来了，下面的代码，我测试的是没有问题的。这思想完美体现了快速排序的思想，分治，又有点像二分，每次partition完了如果没找到只在某一半继续寻找，丢弃另一半。注意，i < k - 1的时候下一次的递归不需要变成k - i - 1，毕竟start的下标没变，仍然按照原始数组下标来执行的。
private int findKth(int k, int[] nums, int start, int end) {
int i = start, j = end;
int pivot = nums[start];
while (i < j) {
while (i < j && nums[j] >= pivot)
j--;
if (i < j)
nums[i] = nums[j];
while (i < j && nums[i] <= pivot)
i++;
if (i < j)
nums[j] = nums[i];
}
nums[i] = pivot;
if (i == k - 1)
return nums[i];
else if (i > k - 1)
return findKth(k, nums, start, i - 1);
else
return findKth(k, nums, i + 1, end);
}
下面是快速排序，快速排序有很多种实现，这里就只选取nums[0]当做pivot了，我感觉这样做没什么不好（当然最好是用三数取中之类的方法取pivot），除非nums[0]每次都恰好是最大或最小。注意在进行nums比较的时候我都加上了>=或者<=，结果是没问题的，我感觉这样可以减少一些递归次数。还有，有的人把代码写成: nums[i--] = nums[j];这样，这么做唯一的好处就是，省去了下一次while里的比对，效果是一样的。还有，注意这么写的时候要从尾部往前搞(先j--)，不能从头往后搞。
private static void quickSort(int[] a, int low, int high) {
//递归的出口
if (low > high) {
return;
}
int i = low;
int j = high;
int pivot = a[low];
//完成一趟排序
while (i < j) {
//[从右往左]找到第一个小于pivot的数
while (i < j && a[j] > pivot) {
j--;
}
//从左往右找到第一个大于pivot的数
while (i < j && a[i] <= pivot) {
i++;
}
//a[i]和a[j]交换
if (i < j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
//a[i]和a[low]交换
int temp = a[i];
a[i] = a[low];
a[low] = temp;
quickSort(a, low, i - 1);
quickSort(a, i + 1, high);
}
--
ref:
http://wangleide414.iteye.com/blog/1672424
http://www.jianshu.com/p/2cc8fc1c878
