分治法——基于快速排序求第k小元素

1.問題描述

給定一個序列，求序列中的第 k 小，k的取值範圍為1~n。

2.問題分析

這個問題我們可以在快速排序的基礎上使用分治法加以實作。

首先對數組a進行分割，一次分割使得所選的元素（一般為a[0]）在正确的位置，其左邊的數都比它小，右邊的數都比它大，傳回這個元素的下标mid。

（1）如果k=mid+1，那麼a[mid]即為第k小元素。

（2）如果k<mid+1，說明第k小元素應該做分割元素的左邊，在分割元素左邊使用同樣方法找第k小元素。

（3）如果k>mid+1，說明第k小元素在分割元素的右邊，應該在分割元素右邊使用同樣方法找第 k-mid-1 小元素。

3.代碼實作

template<class T>
int split(T a[],int start,int end)
{
    int high=end;
    int low=start;
    T temp=a[start];
    
    for(;;)
    {
        if(low==high)
            break;
        while(low<high&&a[high]>=temp)
            high--;
        if(low!=high)//避免出現a={2,3}這種情況
            a[low++]=a[high];
        else
            break;
        
        while(low<high&&a[low]<=temp)
            low++;
        if(low!=high)
            a[high--]=a[low];
        else
            break;
    }
    a[high]=temp;
    return high;
}

template<class T>
T selectK(T a[],int k,int start,int end)
{
    int mid;//中間元素的下标
    mid=split(a,start,end);
    mid=mid-start;

    if(k==mid+1)
        return a[mid+start];
    else if(k<mid+1)
        return selectK(a,k,start,mid+start-1)；//在左邊
    else
        return selectK(a,k-mid-1,mid+start+1,end);//在右邊
}
           

時間複雜度分析

在最壞情況下，即每次選擇的分割元素都是最大值或者最小值，子數組規模減一，求第k小元素需要分割k次

時間複雜度為O(kn)。

後續将會介紹時間複雜度為O(n)的算法