快速选择思想
快速选择思想源于快速排序，但我们只进行部分快速排序，只要找到我们要的位置上的元素，排序就不再进行下去。快速选择的方法跟快速排序基本一致，差别在于我们有给定要找的元素位置，在排序基准值时，把基准值的位置和我们要找的位置进行比较。如果我们要找小于基准值位置的元素，便缩小至左子区间继续查找；如果我们要找大于基准值位置的元素，便缩小至右子区间继续查找。
一个例子让你掌握快速选择
我们给定一个数组，假设要找排完序后数组的第3个位置上元素的值。我们定义临时变量temp存放基准值，定义左标志位定位至数组第一个元素，定义右标志位定位至数组最后一个元素。我们假定左标志位为基准值。首先我们把左标志位的元素值5放入临时变量temp中。
然后比较基准值5与右标志位元素值8。右标志位的值大于基准值，满足排序条件，左移右标志位，继续与基准值比较。
右标志位元素4小于基准值5，把右标志位的值4赋予左标志位。
接下来右移左标志位，左标志位的值7与基准值5进行比较，左标志位的值7大于基准值5。把左标志位的值7赋值给右标志位。
继续更改右标志位，左移右标志位，基准值5与右标志位1进行比较，右标志位的值1小于基准值5，把右标志位的值赋值给左标志位。
左标志位右移一位，基准值5与左标志位的值9进行比较，左标志位的值9大于基准值5。把左标志位的值9赋值给右标志位。
右标志位左移一位，右标志位的值3与基准值5进行比较。右标志位的值3小于基准值5，把右标志位的值赋值给左标志位。
左标志位右移一位，左标志位的值2与基准值5进行比较，左标志位的值2比基准值5小，符合排序条件，左标志位右移一位。
左标志位的值6继续与基准值5进行比较，左标志位的值6大于基准值5，把左标志位的值6赋值给右标志位。
右标志位左移一位，恰好左右标志位重合。直接把基准值5赋值给左标志位。
此时左标志位与右标志位位置均为4，元素5的位置已经确定下来，但位置值大于我们要找的位置3，我们缩小区间至左子区间，继续查找。
我们更新右边界为上一步的基准值所在位置的前一位，假定左标志位为基准值，把左标志位的元素值4放入临时变量temp中。
然后比较基准值4与右标志位元素值2。右标志位的值小于基准值，把右标志位的值赋值给左标志位。
右移左标志位一位，比较基准值4与左标志位元素值1，符合排序条件，左标志位继续右移一位。
比较基准值4与左标志位元素值3，符合排序条件，左标志位继续右移一位。
左右标志位位置刚好重合，把基准值4放入此位置。
当前标志位位置在3上，刚好与我们要的位置相匹配，基准值就是我们要找的答案。
快速选择算法一(此方法仅对无重复元素的数组有效！)：
// 针对不含重复元素的数组有效
public int quickSelection(int[] array, int k) {
// 定义左右边界
int left = 0, right = array.length - 1;
// 当左边界没有超过右边界值时执行循环
while (left < right) {
// 定义左右标志位
int i = left, j = right;
// 取左标志位的值为基准值
int target = array[left];
// 当左标志位小于右标志位时
while (i < j) {
// 如果i没有越界 并且 右标志位的元素值大于等于基准值
while (i < j && target <= array[j])
// 说明右标志位的元素符合排序要求，左移右标志位
j--;
// 把右标志位的元素值覆盖左标志位的元素值
array[i] = array[j];
// 如果i没有越界 并且 左标志位的元素值小于等于基准值
while (i < j && array[i] <= target)
// 说明左标志位的元素符合排序要求，右移左标志位
i++;
// 把左标志位的元素值覆盖右标志位的元素值
array[j] = array[i];
}
// 当左右标志位重回时，把基准值放入序列
array[i] = target;
// 当坐标k的值小于等于左标志位i，说明要找的值在左子区间，缩小区间范围至左子区间
if (k <= i)
// 更新右边界至左标志位前一个位置
right = i - 1;
// 当坐标k的值大于等于右标志位j，说明要找的值在右子区间，缩小区间范围至右子区间
if (i <= k)
// 更新左边界至右标志位后一个位置
left = i + 1;
}
// 返回标志位上的元素值
return left;
}
快速选择算法二(此方法对所有情况数组有效！)：
// 快速选择查找位置k上的元素值，默认k位置有效
public int quickSelectionK(int[] nums, int k) {
// 定义左右边界
int left = 0, right = nums.length - 1;
// 当左边界小于右边界执行循环
while (left < right) {
// 调用快速选择函数获取区间轴节点位置
int mid = quickSelection(nums, left, right);
// 如果轴节点位置刚好是目标元素位置
if (mid == k)
// 返回此位置上的元素值
return nums[mid];
// 如果轴节点位置在目标位置前方
if (mid < k) {
// 缩小区间至右子区间，左边界更新为轴节点下一个位置
left = mid + 1;
} else {
// 否则轴节点位置在目标位置后方
// 缩小区间至左子区间，右边界更新为轴节点前一个位置
right = mid - 1;
}
}
// 返回边界位置上的值
return nums[left];
}
// 快速选择
public int quickSelection(int[] nums, int left, int right) {
// 定义左标志位为左边界下一个位置，右标志位为右边界，默认基准值为左边界上的元素值
int i = left + 1, j = right;
// 循环
while (true) {
// 如果i没有越界 并且 左标志位的元素值小于等于基准值
while (i < right && nums[i] <= nums[left])
// 左标志位右移一位
++i;
// 如果j没有越界 并且 右标志位的元素值大于等于基准值
while (left < j && nums[j] >= nums[left])
// 右标志位左移一位
--j;
// 如果i和j位置重合或i>j，跳出循环
if (i >= j)
break;
// 交换左右标志位上的元素
swap(nums, i, j);
}
// 交换基准值和右标志位上的元素
swap(nums, left, j);
// 返回右标志位位置
return j;
}
// 交换数组元素
public void swap(int[] nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}