|
快速选择思想 快速选择思想源于快速排序，但我们只进行部分快速排序，只要找到我们要的位置上的元素，排序就不再进行下去。快速选择的方法跟快速排序基本一致，差别在于我们有给定要找的元素位置，在排序基准值时，把基准值的位置和我们要找的位置进行比较。如果我们要找小于基准值位置的元素，便缩小至左子区间继续查找；如果我们要找大于基准值位置的元素，便缩小至右子区间继续查找。 一个例子让你掌握快速选择 我们给定一个数组，假设要找排完序后数组的第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;}
|
