Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Selection Algorithm

算法描述：

問題：給定序列中的找到第 k 小數字。
一般會使用 sorting algorithm 在 O(n logn) 排序後找到 k-th 小數字。
又或者使用一個 heap 維護，在效率 O(n logk) 內找到，但這一算法可以在 O(n) 時間內完成。

算法步驟：

詳細步驟&證明請參考：
http://www.cnblogs.com/hibernate6/archive/2011/04/28/2522298.html

稍微描述一下核心，通常使用 RANDOM-SELECT 也可以達到平均複雜度 O(n)，但這裡要找到最慘情況下可以在 O(n) 的算法，RANDOM-SELECT 類似於 quick sort 的一部分，只要能確保 pivot 盡可能是中位數的話，效率就能在最慘達到 O(n)。

於是這裡設計一個遞迴的操作：
首先，定義函數：
(1) selectionAlgorithm() 回傳指定序列中的第 k 小的索引值
(2) medianOfMedians() 回傳序列的 "近似中位數" 的索引值

由於 selectionAlgorithm() 寫法與 RANDOM-SELECT 的做法一樣，這裡著重於找到近似中位數。

medianOfMedians()：
1. 將數列 5 個數字分一堆，最後一堆少於 5 個，每組找到中位數。
2. 對於這 5 個數字使用 "插入排序" 得到中位數，假設這個操作 O(1)。
3. 得到所有中位數後，調用 selectionAlgorithm 確切找到中位數們的中位數。

selectionAlgoithm()：
1. 增加修改的地方為 pivot 調用 medianOfMedians() 得到。

由於 "近似中位數" 的效用，保證劃分的位置可以在 [3/10 * n, 7/10 * n] 之間。

換而言之，如果將 medianOfMedians() 放回 selectionAlgorithm()：

得到遞迴 T(n) = T(n/5) + T(7n/10+6) + O(n)
其中 T(n/5) 是 medianOfMedians() 調用 selectionAlgorithm()
T(7n/10) 則是在最慘的情況下，繼續在 7n/10 個數字下遞歸。

證明：O(n)，將使用數學歸納法證明。
假設 T(n) <= cn, c > 0 是常數
規定 T(n) = O(1), when n < 140
    T(n) <= T(n/5) + T(7n/10+6) + O(n)
=>  T(n) <= c(n/5+1) + c(7n/10+6) + an
=>  T(n) <= 9cn/10 + 7c + an
=>  T(n) <= cn + (-cn/10 + 7c + an)

解 (-cn/10 + 7c + an) <= 0，
=> c >= 10a(n / (n-70) )
=> for n >= 140, n/(n-70) >= 2, c >= 20a 即可。
因此得到最慘情況 O(n)。

範例輸入：

10 0
14 11 25 17 17 14 14 3 19 12
10 8
4 1 4 9 22 25 10 19 6 23
10 9
16 6 9 20 15 21 5 21 6 26

範例輸出：

3
23
26

---

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#define debug 0
using namespace std;
int selectionAlgorithm(int[], int, int, int);
int medianOfMedians(int[], int, int);
int selectionAlgorithm(int a[], int l, int r, int k) {
/**
 * k = 0, 1, 2, ...
 * return k-th smallest value.
 */
    if(r-l+1 <= 5) {// insert sort.
        int i, j, v;
        for(i = l+1; i <= r; i++) {
            v = a[i], j = i;
            while(j-1 >= l && a[j-1] > v)
                a[j] = a[j-1], j--;
            a[j] = v;
        }
        return l+k;
    }
    //printf("%d %d\n", l, r);
    int pivot = medianOfMedians(a, l, r);
    // partition begin.
    swap(a[l], a[pivot]);
    int i, j, t = a[l];
    for(i = l, j = l+1; j <= r; j++) {
        if(a[j] <= t)
            i++, swap(a[i], a[j]);
    }
    swap(a[l], a[i]);
    // partition end.
    int position = i;
#if debug == 1
    printf("pivot = %d ", t);
    printf("[");
    for(i = l; i <= position; i++)
        printf("%d ", a[i]);
    printf("]");
    printf("[");
    for(i = position+1; i <= r; i++)
        printf("%d ", a[i]);
    printf("]\n");
#endif
    if(position-l == k)    return position;
    if(position-l < k)
        return selectionAlgorithm(a, position+1, r, k-(position-l+1));
    else
        return selectionAlgorithm(a, l, position, k);
}
int medianOfMedians(int a[], int l, int r) {
    int numMedians = (r-l+4)/5;
    int i, subl, subr;
    int medianIdx;
    for(i = 0; i < numMedians; i++) {
        subl = l + i*5;
        subr = subl + 4;
        if(subr > r)    subr = r;
        medianIdx = selectionAlgorithm(a, subl, subr, (subr-subl)/2);
        swap(a[l+i], a[medianIdx]);
    }
    //printf("median %d %d\n", l, r);
    return selectionAlgorithm(a, l, l+numMedians, numMedians/2);
}
int a[1000005];
int main() {
    clock_t st, ed;
    st = clock();
    //srand(time(NULL));
    freopen("in.txt","r+t",stdin);
    freopen("out.txt","w+t",stdout);
    int n, m;
    int i;
    while(scanf("%d %d", &n, &m) == 2) {
        for(i = 0; i < n; i++)
            scanf("%d", &a[i]);
        int idx = selectionAlgorithm(a, 0, n-1, m);
        printf("%d\n", a[idx]);
    }
    ed = clock();
    printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
    return 0;
}