面接問題:top kアルゴリズムO(n)時間複雑度

「データ構造とアルゴリズム分析--c言語記述」という本、第7章7.7.6節では、平均的な場合、時間複雑度がO（N）の高速選択アルゴリズムについて述べた.次のようになります.

S中の1つの要素をピボットvとして選択し、集合S-{v}をS 1とS 2に分割し、高速ソートのように

k<=|S 1|の場合、k番目の最小要素は必ずS 1にある.この場合、QuickSelect(S 1,k)が返される.

k=1+|S 1|の場合、ピボット要素はk番目の最小要素であり、すなわち見つけられ、直接それに戻る.

それ以外の場合、k番目の最小要素はS 2、すなわちS 2の(k-|S 1|-1)番目の最小要素であり、QuickSelect(S 2、k-|S 1|-1)を再帰的に呼び出して返す.

このアルゴリズムの平均運転時間はO(n)である.
サンプルコードは次のとおりです.

//QuickSelect   k       a[k-1]  
void QuickSelect( int a[], int k, int left, int right )
{
    int i, j;
    int pivot;

    if( left + cutoff <= right )
    {
        pivot = median3( a, left, right );
        //          ，             
        i = left; j = right - 1;
        for( ; ; )
        {
            while( a[ ++i ] < pivot ){ }
            while( a[ --j ] > pivot ){ }
            if( i < j )
                swap( &a[ i ], &a[ j ] );
            else
                break;
        }
        //     
        swap( &a[ i ], &a[ right - 1 ] );  

        if( k <= i )
            QuickSelect( a, k, left, i - 1 );
        else if( k > i + 1 )
            QuickSelect( a, k, i + 1, right );
    }
    else  
        InsertSort( a + left, right - left + 1 );
}

この高速選択SELECTアルゴリズムは,高速ソートの分割方法に似ている.N個の数を配列Sに格納し、配列から「中位数の中位数」をピボットXとして選択し、配列をSaとSbの2つの部分に分割し、Sa<=X<=Sbとし、検索するk個の要素がSaの要素の数より小さい場合はSaの中の小さいk個の要素を返し、そうでない場合はSaの中にある要素+Sbの中の小さいk-|Sa|個の要素を返し、この解法は平均的にO(n)の複雑さを実現することができる.
さらに,「アルゴリズム導論」9章9.3節では,最悪の場合でもO(n)時間のSELECTアルゴリズムを紹介し,興味のある読者は参照できる.