关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
快速选择是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。同样地，它在实际应用是一种高效的算法，具有很好的平均时间复杂度，然而最坏时间复杂度则不理想。
快速选择及其变种是实际应用中最常使用的高效选择算法。
快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度，从O(n log n)至O(n)，不过最坏情况仍然是O(n2)。
示例：
从数组中找出第 k 小的元素：
// find the kth **smallest** element in an unsorted array
public int quickSelect(int[] nums, int k) {
int i = 0;
int j = nums.length - 1;
while(i <= j) {
int partitionIdx = partition(nums, i, j);
if((k - 1) == partitionIdx) {
return nums[partitionIdx];
}
else if((k - 1) < partitionIdx) {
j = partitionIdx - 1;
}
else {
i = partitionIdx + 1;
}
}
return 0;
}
// same as qucik sort
public int partition(int[] nums, int start, int end) {
if(start == end) {
return start;
}
int pivot = nums[start];
while(start < end) {
// find first smaller element from right
while(start < end && nums[end] >= pivot) {
end--;
}
nums[start] = nums[end];
// find first larger element from left
while(start < end && nums[start] <= pivot) {
start++;
}
nums[end] = nums[start];
}
nums[start] = pivot;
return start;
}
引用：
