快速选择(Quickselect)算法是利用快速排序(Quick Sort)算法,在排序串行的同时,选择出串行中第 K 小或是第 K 大的元素。若我们只想要从串行中找出一个第 K 小或是第 K 大元素,使用快速选择法会比使用快速排序法来得快很多,因为前者不需要把串行的排序完整做完,平均只需线性时间即可找到结果。
使用快速选择法寻找串行中第 K 小的元素,在完成快速排序法中「把比支点元素小的元素移到支点左边和把比支点元素大的元素移到支点右边」的动作后,快速选择法并不需再对支点两端的子串行都进行排序,取而代之的是,利用此时已经固定下来的支点,可以知道支点元素是串行中第 P 小的元素,来判断 K 是否等于 P,如果 K 等于 P,我们就找到第 K 小的元素了;如果 K 不等于 P,那就只要继续用相同方式排序支点右端或是支点左端的子串行,持续下去直到找出 K 即可。
/// 快速选择法(从最小开始),使用循环来迭代。
pub fn quickselect(array: &mut [i32], index: usize) -> usize {
let mut start = 0;
let mut end = array.len() - 1;
loop {
if start == end {
return start;
}
let pivot = array[start];
let mut l = start + 1;
let mut r = end;
loop {
while r > start && array[r] >= pivot {
r -= 1;
}
while l <= r && array[l] <= pivot {
l += 1;
}
if l < r {
array.swap(l, r);
} else {
if r > start {
array.swap(start, r);
}
break;
}
}
match index.cmp(&r) {
Ordering::Equal => {
return index;
}
Ordering::Greater => {
start = r + 1;
}
Ordering::Less => {
end = r - 1;
}
}
}
}
/// 快速选择法(从最大开始),使用循环来迭代。
pub fn quickselect_desc(array: &mut [i32], index: usize) -> usize {
let mut start = 0;
let mut end = array.len() - 1;
loop {
if start == end {
return start;
}
let pivot = array[end];
let mut l = start;
let mut r = end - 1;
loop {
while l < end && array[l] >= pivot {
l += 1;
}
while r >= l && array[r] <= pivot {
if r == 0 {
break;
}
r -= 1;
}
if l < r {
array.swap(l, r);
} else {
if l < end {
array.swap(l, end);
}
break;
}
}
match index.cmp(&l) {
Ordering::Equal => {
return index;
}
Ordering::Greater => {
start = l + 1;
}
Ordering::Less => {
end = l - 1;
}
}
}
}
/**
* 快速选择法(从最小开始),使用循环来迭代。
*/
public static int quickselect(final int[] array, final int index) {
int start = 0;
int end = array.length - 1;
while (true) {
if (start == end) {
return start;
}
final int pivot = array[start];
int l = start + 1;
int r = end;
while (true) {
while (r > start && array[r] >= pivot) {
--r;
}
while (l <= r && array[l] <= pivot) {
++l;
}
if (l < r) {
int temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (r > start) {
int temp = array[start];
array[start] = array[r];
array[r] = temp;
}
break;
}
}
if (index == r) {
return index;
} else if (index > r) {
start = r + 1;
} else {
end = r - 1;
}
}
}
/**
* 快速选择法(从最大开始),使用循环来迭代。
*/
public static int quickselectDesc(final int[] array, final int index) {
int start = 0;
int end = array.length - 1;
while (true) {
if (start == end) {
return start;
}
final int pivot = array[end];
int l = start;
int r = end - 1;
while (true) {
while (l < end && array[l] >= pivot) {
++l;
}
while (r >= l && array[r] <= pivot) {
--r;
}
if (l < r) {
int temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (l < end) {
int temp = array[l];
array[l] = array[end];
array[end] = temp;
}
break;
}
}
if (index == l) {
return index;
} else if (index > l) {
start = l + 1;
} else {
end = l - 1;
}
}
}
/**
* 快速选择法(从最小开始),使用循环来迭代。
*/
function quickselect(array: number[], index: number) {
let start = 0;
let end = array.length - 1;
for (; ;) {
if (end === start) {
return start;
}
const pivot = array[start];
let l = start + 1;
let r = end;
for (; ;) {
while (r > start && array[r] >= pivot) {
r -= 1;
}
while (l <= r && array[l] <= pivot) {
l += 1;
}
if (l < r) {
const temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (r > start) {
const temp = array[start];
array[start] = array[r];
array[r] = temp;
}
break;
}
}
if (index === r) {
return index;
} else if (index > r) {
start = r + 1;
} else {
end = r - 1;
}
}
}
/**
* 快速选择法(从最大开始),使用循环来迭代。
*/
function quickselectDesc(array: number[], index: number) {
let start = 0;
let end = array.length - 1;
for (; ;) {
if (end === start) {
return start;
}
const pivot = array[end];
let l = start;
let r = end - 1;
for (; ;) {
while (l < end && array[l] >= pivot) {
l += 1;
}
while (r >= l && array[r] <= pivot) {
r -= 1;
}
if (l < r) {
const temp = array[l];
array[l] = array[r];
array[r] = temp;
} else {
if (l < end) {
const temp = array[l];
array[l] = array[end];
array[end] = temp;
}
break;
}
}
if (index === l) {
return index;
} else if (index > l) {
start = l + 1;
} else {
end = l - 1;
}
}
}
// 快速选择法(从最小开始),使用循环来迭代。
func Quickselect(array []int, index int) int {
start := 0
end := len(array) - 1
for {
if start == end {
return start
}
pivot := array[start]
l := start + 1
r := end
for {
for r > start && array[r] >= pivot {
r -= 1
}
for l <= r && array[l] <= pivot {
l += 1
}
if l < r {
array[l], array[r] = array[r], array[l]
} else {
if r > start {
array[start], array[r] = array[r], array[start]
}
break
}
}
if index == r {
return index
} else if index > r {
start = r + 1
} else {
end = r - 1
}
}
}
// 快速选择法(从最大开始),使用循环来迭代。
func QuickselectDesc(array []int, index int) int {
start := 0
end := len(array) - 1
for {
if start == end {
return start
}
pivot := array[end]
l := start
r := end - 1
for {
for l < end && array[l] >= pivot {
l += 1
}
for r >= l && array[r] <= pivot {
r -= 1
}
if l < r {
array[l], array[r] = array[r], array[l]
} else {
if l < end {
array[l], array[end] = array[end], array[l]
}
break
}
}
if index == l {
return index
} else if index > l {
start = l + 1
} else {
end = l - 1
}
}
}