[算法详解][快速选择] Quick Select
通常用来在未排序的数组中寻找第k小/第k大的元素。
【基本思想】
选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。
【步骤】
- 选择一个元素作为基准来对元素进行分区
- 将小于和大于基准的元素分在基准左边和右边的两个区域。
- 递归进入一边的元素中继续寻找
【实例分析】
nums = [1, 5, 1, 1, 6, 4]， k=2
left = 0, right = 5, pivot = nums[2] = 1, cur = 0
- loop1: nums = [1, 5, 1, 1, 6, 4]
nums[cur] = 1 == pivot, cur++. cur = 1, left = 0, right = 5 - loop2: nums= [1, 4, 1, 1, 6, 5]
nums[cur] = 5 > pivot, swap nums[right] and pivot, , right=4, left = 0, cur = 1 - loop3: nums = [1, 6, 1, 1, 4, 5]
nums[cur] = 4 > pivot, swap nums[right] and pivot, , right=3, left = 0, cur = 1 - loop4: nums = [1, 1, 1, 6, 4, 5]
nums[cur] = 6 > pivot, swap nums[right] and pivot, , right=2, left = 0, cur = 1 - loop5: nums = [1, 1, 1, 6, 4, 5]
nums[cur] = 1 == pivot. cur = 2, left = 0, right = 2 - loop6:
cur == right break while loop.
left 表示小于pivot的个数，cur表示小于等于pivot的个数，k为前k个最小元素
如果left >= k，遍历左半部分，即select(nums, start, left, k)
如果cur<=k,遍历右半部分 select(nums, cur, end, k)
该实例需要遍历右半部分，select(nums, 2, 5, 2)
left = 2, right = 5, pivot = nums[3] = 6, cur = 2
nums = [1, 1, 1, 6, 4, 5]
loop1: nums = [1, 1, 6, 1, 4, 5]
nums[cur] = 1 < pivot，swap nums[left] and pivot, right=5, left = 3, cur = 3
loop2: nums = [1, 1, 1, 6, 4, 5]
nums[cur] = 6 == pivot. right=5, left = 3, cur = 4
loop2: nums = [1, 1, 1, 4, 6, 5]
nums[cur] = 4 < pivot，swap nums[left] and pivot, right=5, left = 4, cur = 5
loop3:
cur == right break while loop.
遍历左半部分，select(nums, 2, 4, 2)
left = 2, right = 4 pivot = nums[3] = 4, cur = 2
nums = [1, 1, 1, 4, 6, 5]
loop1: nums = [1, 1, 1, 4, 6, 5]
nums[cur] = 1 < pivot，swap nums[left] and pivot, right=4, left = 3, cur = 3
loop2: nums = [1, 1, 1, 6, 4, 5]
nums[cur] = 4 == pivot 。right=4, left = 3, cur = 4
loop3:
cur == right break while loop.
遍历左半部分，select(nums, 2, 3, 2)
left = 2, right = 3 pivot = nums[2] = 1, cur = 2
nums = [1, 1, 1, 6, 4, 5]
loop1: nums = [1, 1, 1, 4, 6, 5]
nums[cur] = 1 == pivot，right=3, left = 2, cur = 3
遍历左半部分，select(nums, 2, 2, 2)
return
此时nums[k]为median
【伪代码】
function select(list, left, right, k)
if left = right
return
pivot = list[mid]
index: cur, left_cur, right_cur
loop
if list[cur] > pivot
swap(list[cur] , list[right_cur]);
right--
else if list[cur] < pivot
swap(list[cur] , list[left_cur]);
left++; cur++
else
cur++
if(k <= left) select(list, left, left_cur, k)
if(k > cur) select(list, cur, right, k)
【JAVA代码实现】
public void median(int[] nums, int start, int end, int k) {
int left = start, right = end;
if(left == right) return;
int cur = left;
int pivot = nums[(left + right) / 2];
while(cur < right){
if(nums[cur] < pivot) {
int tmp = nums[cur];
nums[cur] = nums[left];
nums[left] = tmp;
cur++;
left++;
}else if(nums[cur] > pivot) {
int tmp = nums[cur];
nums[cur] = nums[right];
nums[right] = tmp;
right--;
}else{
cur++;
}
}
if(left >= k) median(nums, start, left, k);
if(cur <= k) median(nums, cur, end, k);
return;
}
【性能分析】
1. 最优
时间复杂度为O(n)
在最好情况下，若输入已排序，插入排序的时间复杂度在O(n)，即线性时间上完成排序。
2. 最坏
时间复杂度为O(n^2)
3. 平均
O(n)
因为Quick select只考虑所寻找的目标所在的那一部分子数组
设算法时间复杂度为T(n)。在第一层循环中，我们将pivot与n个元素进行了比较，这个时间为cn 。
所以第一步时间为：T(n) = cnc + T(n/2)。其中T(n/2)为接下来递归搜索其中一半的子数组所需要的时间。
在递归过程中，我们可以得到如下公式：
T(n/2) = c(n/2) + T(n/4)
T(n/4) = c(n/4) + T(n/8)
...
T(2) = 2c + T(1)
T(1) = 1c
将以上公式循环相加消除T项可以得到：
T(n) = c(n + n/2 + n/4 + n/8 + ... + 2 + 1) = 2n = O(n)
4. 空间复杂度
O(1)
算法没有使用额外空间，swap操作是inplace操作，所以算法的空间复杂度为O(1)。
5. 稳定性
【应用：常见面试题目】
Leetcode 324. Wiggle Sort II
参考：Quick Sort
