快速选择算法

快速选择是一种从无序列表中找到第小元素的选择算法，其原理与快速排序相关。

算法思路：选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准点左边和右边。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。在快速选择中，虽然大部分元素是乱序的，但基准元素已经在最终排好序的位置上。

算法伪代码：

// 分区,即将列表分成两部分，粉笔是是小于基准pivot和大于基准pivot的元素
function partition(list, left, right, pivotIndex)
    pivotValue := list[pivotIndex]
    // 将基准pivot移动到最末端
    swap list[pivotIndex] and list[right]
    storeIndex := left
    for i from left to right-1
        if list[i] < pivotValue
            swap list[storeIndex] and list[i]
            increment storeIndex
    // 将基准移动到其最终排序好的位置上
    swap list[right] and list[storeIndex]  // Move pivot to its final place
    return storeIndex

function select(list, left, right, k)
   if left = right        // 若list只包含一个元素,直接返回当前元素
       return list[left]
   // 在left和right之间选择pivotIndex
   pivotIndex  := left + floor(rand() % (right - left + 1))
   pivotIndex  := partition(list, left, right, pivotIndex)
   // The pivot is in its final sorted position
   // pivotIndex对应的元素已经在最终排序好的位置上。
   if k = pivotIndex
       return list[k]
   else if k < pivotIndex
       return select(list, left, pivotIndex - 1, k)
   else
       return select(list, pivotIndex + 1, right, k)

算法对应的C++实现：

#include <iostream>
#include <vector>
using namespace std;

/**
 * 分区函数
 * 将大于基准和小于基准的元素划分到基准点的左侧和右侧并返回基准在数组中的位置索引
 */
int partition(vector<int> &arr, int left, int right, int privot_idx)
{
    int privot_val = arr[privot_idx];
    // 将基准元素移动到最右端
    swap(arr[right], arr[privot_idx]);
    int store_idx = left;
    for (int i = left; i < right; i++)
    {
        if (arr[i] < privot_val)
        {
            swap(arr[i], arr[store_idx]);
            store_idx++;
        }
    }
    swap(arr[store_idx], arr[right]);
    return store_idx;
}

/**
 * 快速选择（递归版）
 */
int quick_select(vector<int> &arr, int left, int right, int k)
{
    if (left == right)
        return arr[left];
    // 在left和right间选择基准索引
    int privot_idx = left + rand() % (right - left + 1);
    privot_idx = partition(arr, left, right, privot_idx);
    if (privot_idx == k - 1)
        return arr[privot_idx];
    else if (privot_idx > k - 1)
        return quick_select(arr, left, privot_idx - 1, k);
    else
        return quick_select(arr, privot_idx + 1, right, k);
}

int main()
{
    vector<int> arr = {1, 4, 2, 7, 10, 0, 3};
    int k = 5;
    cout << quick_select(arr, 0, arr.size() - 1, k) << endl; // 4
    return 0;
}