Algorithms Part 1 - Week 3–5之Quick-select筆記

功能: 從N個itmes中找到第k小的item

想法

切開陣列a使其

• a[j]左邊的items都比他小
• a[j]右邊的items都比他大

在一個subarray裡重複select步驟直到j = k

public static Comparable select(Comparable[] a, int k)
{
    StdRandom.shuffle(a);
    int lo = 0, hi = a.length - 1;
    while (hi > lo)
    {
        int j = partition(a, lo, hi);
        if (j < k) lo = j + 1;
        else if (j > k) hi = j - 1;
        else return a[k];
    }
    return a[k];
}

時間

• 平均是線性時間
• 證明在ppt裡P.27
• Quick-select在最差情況下會用~$1/2N^2$個compares，但演算法一開始的shuffle可以讓其有一定機率是線性時間可完成

使用以及展望

• 尚未發現能保證線性時間的選擇演算法
• 在那之前，如果不需要全部都排序，就用quick-select