搞了一晚上尋找第k小元素逻族，終于弄出來了，下面的代碼束昵，我測試的是沒有問題的拔稳。這思想完美體現(xiàn)了快速排序的思想，分治锹雏，又有點像二分巴比，每次partition完了如果沒找到只在某一半繼續(xù)尋找，丟棄另一半礁遵。注意匿辩，i < k - 1的時候下一次的遞歸不需要變成k - i - 1，畢竟start的下標沒變榛丢，仍然按照原始數組下標來執(zhí)行的铲球。
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);
}
下面是快速排序，快速排序有很多種實現(xiàn)晰赞，這里就只選取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.reibang.com/p/2cc8fc1c878
