快速排序（3）的应用：选择--用于选出第K小的元素

排序算法

本文描述了一个快速排序的应用，用快速排序快速的选出数据中第k小的文件（元素）。

一个与排序有关但又不需要完全排序的应用是找出一组数的中间数的操作。寻找中间元素时选择操作的一个特例，即选择一组数中的第$k$个最小元素。一种方法是对数据进行排序，但我们可以使用快速排序的划分过程做的更好。

算法过程（寻找第k小的元素）

• 快速排序的划分，重排数组a[l],……,a[r]，返回一个整数 i ，使得a[l],……,a[i-1]都小于或等于a[i]； a[i+1],……,a[r]都大于或等于a[i];
• 如果k == i,划分完成，此时a[i]中的元素即为第k小的元素；
• 如果k < i,继续对左子文件进行处理
• 如果k > i,继续对右子文件进行处理

程序实现

递归实现选择算法

/*=============选择函数--选出第k小的元素=============*/
void select(Item a[], int l, int r, int k) //递归实现
{
    if(r <= l)
        return;
    int i = partation(a, l, r);
    if(k < i)
        select(a, l, i-1, k);
    else if(k > i)
        select(a, i+1, r, k);
}

非递归实现

void select_2(Item a[], int l, int r, int k) // 非递归实现
{
    while(r > l)
    {
        int i = partation(a, l, r);
        if(k < i)
            r = i-1;
        if(k > i)
            l = i+1;
    }
}

由于上述划分过程是将原数组中的数据进行交换，因此用上述选择算法操作数组后，a[k]中的元素就是第k小的元素。