快速選擇(Quickselect)演算法，快速尋找第K小或是第K大的元素

快速選擇(Quickselect)演算法是利用快速排序(Quick Sort)演算法，在排序序列的同時，選擇出序列中第K小或是第K大的元素。若我們只想要從序列中找出一個第K小或是第K大元素，使用快速選擇法會比使用快速排序法來得快很多，因為前者不需要把序列的排序完整做完，平均只需線性時間即可找到結果。

快速選擇法(Quickselect)

快速選擇法的概念

快速選擇法是基於快速排序法的演算法，如果您還不了解快速排序法的話，請先參考這篇文章：

https://magiclen.org/quick-sort/

使用快速選擇法尋找序列中第K小的元素，在完成快速排序法中「把比支點元素小的元素移到支點左邊和把比支點元素大的元素移到支點右邊」的動作後，快速選擇法並不需在再對支點兩端的子序列都進行排序，取而代之的是，利用此時已經固定下來的支點，可以知道支點元素是序列中第P小的元素，來判斷K是否等於P，如果K等於P，我們就找到第K小的元素了；如果K不等於P，那就只要繼續用相同方式排序支點右端或是支點左端的子序列，持續下去直到找出K即可。

快速選擇法的過程

假設現在有個陣列資料，內容如下：

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何找到第5小的元素呢？

一開始當然要先選擇一個支點。在此就選擇陣列最前端的位置為支點好了，如下表所示：

       ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

接著從最尾端開始，往前尋找比支點元素還要小的元素。可以找到索引8的元素32，比支點元素69還要小。如下表所示：

       ●                              ＜
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

接著從除了支點的最左端開始，尋找比支點元素還要更大的元素。可以找到索引1的元素81，比支點元素69還要大。如下表所示：

       ●  ＞                          ＜
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

若此時比支點元素更大的元素位置小於比支點元素更小的元素位置(換句話說就是，比支點元素更大的元素在比支點元素更小的元素左邊)，則交換兩個元素的位置，如下表所示：

       ●  ＞                          ＜
索引    0   1   2   3   4   5   6   7   8   9
數值   69  32  30  38   9   2  47  61  81  79
           └─────────────┘

接著從原先比支點元素更小的元素位置繼續向左尋找比支點元素更小的元素。可以找到索引7的元素61，比支點元素69還要小。如下表所示：

       ●  ＞                      ＜
索引    0   1   2   3   4   5   6   7   8   9
數值   69  32  30  38   9   2  47  61  81  79

因為索引7還在原先比支點元素更大的元素位置之右邊，因此再繼續從原先比支點元素更大的元素位置，向右尋找比支點元素更大的元素。可以找到索引8的元素81，比支點元素69還要大。如下表所示：

       ●                          ＜  ＞
索引    0   1   2   3   4   5   6   7   8   9
數值   69  32  30  38   9   2  47  61  81  79

此時比支點元素更大的元素位置大於比支點元素更小的元素位置(換句話說就是，比支點元素更大的元素在比支點元素更小的元素右邊)，則將比支點元素更小的元素與支點元素交換，如下表所示：

       ●                          ＜  ＞
索引    0   1   2   3   4   5   6   7   8   9
數值   61  32  30  38   9   2  47  69  81  79
       └─────────────┘

                                   ○
索引    0   1   2   3   4   5   6   7   8   9
數值   61  32  30  38   9   2  47  69  81  79

支點元素被交換了之後，可以發現支點元素被換到的位置，也就是索引7，其左邊的元素正好都小於支點元素，而右邊的元素正好都大於支點元素。此時索引7就是第6小的元素。由於我們要找的是第5小的元素，因此還要繼續排序支點左邊的子陣列。

同樣選擇陣列最前端的位置為支點好了，如下表所示：

       ●                         | ◎  ◎  ◎
索引    0   1   2   3   4   5   6 |  7   8   9
數值   61  32  30  38   9   2  47 | 69  81  79

接著從尾端開始，往前尋找比支點元素還要小的元素。可以找到索引6的元素47，比支點元素61還要小。如下表所示：

       ●                      ＜ | ◎  ◎  ◎
索引    0   1   2   3   4   5   6 |  7   8   9
數值   61  32  30  38   9   2  47 | 69  81  79

接著從除了支點的左端開始，尋找比支點元素還要更大的元素，會發現都找不到。如下表所示：

       ●                      ＜  ＞ | ◎  ◎  ◎
索引    0   1   2   3   4   5   6     |  7   8   9
數值   61  32  30  38   9   2  47     | 69  81  79

此時將比支點元素更小的元素與支點元素交換，如下表所示：

       ●                      ＜  ＞ | ◎  ◎  ◎
索引    0   1   2   3   4   5   6     |  7   8   9
數值   47  32  30  38   9   2  61     | 69  81  79
       └───────────┘

支點元素被交換了之後，可以發現到支點元素被換到的位置，就是索引6，也就是我們要找的第5小的位置。

                               ○ | ◎  ◎  ◎
索引    0   1   2   3   4   5   6 |  7   8   9
數值   47  32  30  38   9   2  61 | 69  81  79

至此我們就找出陣列中第5小的元素是61了！

快速選擇法的程式實作

/// 快速選擇法(從最小開始)，使用迴圈來迭代。
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
		}

		middle := (start + end) / 2

		if start != middle {
			array[start], array[middle] = array[middle], array[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
		}
	}
}

與快速排序法一樣，快速選擇法也可以隨機選擇支點，而不是每次都用最左邊的索引位置，避免遭遇固定的最差案例。

快速選擇法的複雜度

以#{{n}}#來表示要搜尋或是要排序的資料筆數。

項目	值	備註
最差時間複雜度	#{{O(n^2)}}#	並非要取得最大值或最小值，但選擇到的支點元素剛好都是最大或最小值。
最佳時間複雜度	#{{O(n)}}#	第一次選擇到的支點元素就是要找的第K小或是第K大元素。
平均時間複雜度	#{{O(n)}}#
最差空間複雜度	#{{O(1)}}#
是否穩定	否