问题：利用快排思想查找一个数组中第K大的数。
思路：快排中递归调用一个返回第一个数字把数组分成两部分之后的一个下标，这个下标就表示了这第一个数字在排序后的位置，我们通过将它与K对比，可以每次只选择选两部分之一进行递归查询。
此处利用快排的分治思想查找第K大的数的时候没有去重，
比如
1、2、3、3、5
第2大和第3大的都是3，第4大的才是2.
Java 代码：
Java
/** * Created with IntelliJ IDEA.
User: hqtc
Date: 16-3-22
Time: 下午9:52
-
To change this template use File | Settings | File Templates.
*/
public class QuickSort{private int getSeparatorIndex(int[] nums, int low, int high) {
int k = nums[low];
while (low < high) {
while (k < nums[high] && low < high) {
high--;
}
if (low < high)
nums[low++] = nums[high];
while (k > nums[low] && low < high) {
low++;
}
if (low < high)
nums[high--] = nums[low];
}
nums[low] = k;
return low;
}public void sort(int num[], int low, int high) {
if (low < high) {
int sepIndex = getSeparatorIndex(num, low, high);
sort(num, low, sepIndex - 1);
sort(num, sepIndex + 1, high);
}
}public int findKthMax(int arr[], int k, int left, int right) {
int sepIndex = getSeparatorIndex(arr, left, right);
if (k == arr.length - sepIndex) {
return arr[sepIndex];
} else {
if (k > arr.length - sepIndex) {
return findKthMax(arr, k, left, sepIndex - 1);
} else {
return findKthMax(arr, k, sepIndex + 1, right);
}
}
}
}
