选择问题（求第k个最小元素）

喜欢ヅ旅行 2022-05-24 12:44 175阅读 0赞

*  什么是选择问题
 *  划分的思路
 *  Lomuto 划分
 *  利用划分求第k小元素
 *  C语言实现
 *  改进
 *  参考资料

# 什么是选择问题 #

选择问题（selection problem）是求一个`n`个数列表的第`k`个最小元素的问题。这个数字被称为第`k`个顺序统计量（order statistic）。当然，对于`k=1`或者`k=n`的情况，我们可以扫描整个列表，找出最小或者最大的元素。对于其他情况，我们可以对列表进行排序，然后返回第`k`个元素。

可是，对于整个列表进行排序是不是小题大做？因为该问题仅仅是要找出第`k`小的元素，而不是要求把列表从小到大排列。

# 划分的思路 #

我们可以将给定的列表根据某个值`p`（例如列表的第一个元素）进行划分。一般来说，这是对列表元素的重新整理，使左边部分包含所有小于等于p的元素，紧接着是中轴（pivot）`p`本身，再接着是所有大于等于p的元素。如下图所示  
![这里写图片描述][70]

有两种主要的划分方法，本文讨论 Lomuto 划分，以后会介绍更有名的 Hoare 划分。

# Lomuto 划分 #

Lomuto（洛穆托）划分的伪代码如下：

// 算法：Lomuto_Partition(A[l..r])
    // 用第一个元素作为中轴对子数组进行划分
    // 输入：数组A[0..n-1]的一个子数组A[l..r]，它由左右两边的索引l和r(l<=r)定义
    // 输出：A[l..r]的划分和中轴的新位置
    
    p = A[l]
    s = l
    for i=l+1 to r do
        if A[i] < p
            s = s+1;
            swap(A[s], A[i])
    swap(A[l], A[s])
    return s

# 利用划分求第`k`小元素 #

我们如何利用划分列表来寻找其第`k`小元素呢？

假设列表是以数组实现的，其元素索引从`0`开始，那么第`k`小的元素就是把此列表从小到大排序后，索引在`k-1`位置上的元素。

假设首次划分此列表，s是分割位置，也就是划分后中轴元素的索引。我们分3种情况进行讨论：

\[1\]. 当`s=k-1` ,那么中轴`p`本身显然就是第`k`小的元素；  
![这里写图片描述][70 1]

\[2\]. 如果`s>k-1`，那么整个列表的第`k`小元素就是左边部分的第`k`小元素；

![这里写图片描述][70 2]

\[3\]. 如果`s<k-1`，那么问题就转换为求右边部分的第`(k-s-1)`小元素；推导过程是这样的：本来是求第`k`小，通过划分，筛除了最前面的`(s+1)`个元素，所以只用求右边部分（蓝色）的第 `k-(s+1)`小。

![这里写图片描述][70 3]

可以看出，第2种情况和第3种情况虽然没有彻底解决问题，但是使问题的实例变小了。对于这个较小的实例可以用同样的方法来解决，即递归求解。这个算法被称为“快速选择”，在算法思想中属于减可变规模算法（减治法的一种）。

# C语言实现 #

// 交换*a和*b
    void swap(int* a, int* b) 
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    // a是数组首地址，l和r分别是两端的索引,要求l<=r
    int Lomuto_partition(int a[], int l, int r) 
    {
        int pivot = a[l];
        int j = l;
    
        for(int i = l + 1; i <= r; ++i)
        {
            if( a[i] < pivot )
            {
                swap( &a[++j], &a[i]);
            }
        }
    
        swap(&a[l], &a[j]);
        return j;   // j是下标
    }
    
    
    // 返回第k小的元素值。
    // 注意：k不是下标，表示第k个
    int __quick_select(int a[], int l, int r, int k) 
    {
        // s是分裂点，中轴的下标
        int s = Lomuto_partition(a, l, r);
    
        if(s == l+k-1)
            return a[s];
        else if( s > (l+k-1) )// 处理左边的部分
            return __quick_select(a, l, s-1, k);
        else // 处理右边的部分
            return __quick_select(a, s+1, r, k-(s-l+1)); 
    }
    
    // 快速选择主函数
    int quick_select_min(int a[], int len, int k) 
    {
        return __quick_select(a, 0, len-1, k);
    }

测试代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    int main(int argc,char *argv[])
    {
    
        int k = atoi(argv[1]); //把命令行输入的字符串转为整数
        printf("k = %d \n",k);
    
        int array[] = {
       9,9,8,7,6,5,4,3,3,3,2,2,2,1,1,0,}; 
        int len = sizeof array/sizeof array[0];
    
        printf("%dth min = %d\n", k, quick_select_min(array,len,k) );
    
        return 0;
    }

运行截图：  
![这里写图片描述][70 4]

# 改进 #

该算法也可以不用递归实现。在非递归版本中，甚至不需要调整`k`的值，只要一直调用`Lomuto_partition`，直到`s=k-1`为止。

代码如下：

int quick_select_min_2(int a[], int len, int k)
    {
        int left = 0;
        int right = len - 1;
        int s;
        // 直到返回的下标是 k-1 为止
        while( (s = Lomuto_partition(a, left, right)) != (k-1) )
        {
            if(s < k-1)
                left = s+1; //处理右边的部分
            else
                right = s-1; // 处理左边的部分
        }
        return a[s];
    }

# 参考资料 #

《算法设计与分析基础（第3版）》（清华大学出版社）

[70]: /images/20220524/3206c21cf986460891547b40a3ca17ed.png
[70 1]: /images/20220524/3c6b95fb7ecc43fdbb3677d0159ac6f6.png
[70 2]: /images/20220524/11282c72fc9942b4b174c533df1b6a12.png
[70 3]: /images/20220524/9bf59c3b743d4564a5d67186a4465e94.png
[70 4]: /images/20220524/69463cb1a3304c1d9bf685022fd30717.png