問題描述：無序找第k小的數(shù)？

臺(tái)山網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、成都響應(yīng)式網(wǎng)站建設(shè)公司等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)從2013年成立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

1、解法一

  先排好序，再找第k小個(gè)數(shù)；返回A[k-1]；此解法的時(shí)間復(fù)雜度為：O(nlogn)；

2、解法二

  情況一：k = 1 和 k = n 就是找數(shù)組的最小值和最大值；

  情況二：找出中位數(shù)

3、找中位數(shù)(隨機(jī)選擇算法)

  利用快速排序的原理，一輪排序，有2種情況：

  if i = k-1；返回a[i]；

  if i != k-1；左邊/右邊遞歸查找，時(shí)間復(fù)雜度為：O(n)；

具體思想：

  分析：在大多數(shù)情況下的時(shí)間復(fù)雜度是：O(n)；但是最壞情況，完全順序下找第k = n-1大數(shù)，此時(shí)的時(shí)間復(fù)雜度是：O(n^2)；

4、無序找第k小值

 快排的升序?qū)崿F(xiàn)思想，在加上遞歸查找；

  (1)、代碼實(shí)現(xiàn)

#include

void findKSmall(int *a, int start, int end, int key);

void findKSmall(int *a, int start, int end, int key){
    int i = start;
    int j = end;
    int tmp = a[i];
//快排中的升序
    while(i < j){
        while(i < j && a[j] > tmp){
            j--;
        }
        if(i < j){
            a[i++] = a[j];
        }
        while(i < j && a[i] < tmp){
            i++;
        }
        if(i < j){
            a[j--] = a[i];
        }
    }
    a[i] = tmp;

    if(key-1 < i){
        findKSmall(a, 0, i-1, key);
    }else if(key-1 > i){
        findKSmall(a, i+1, end, key);
    }else{
        return;
    }
}

void main(void){
    int a[] = {8, 4, 6, 9, 2, 3, 7, 9, 11, 10};
    int count = sizeof(a)/sizeof(int);
    int k;
    int i;

    printf("請(qǐng)輸入要查找的第k小的數(shù)：");
    scanf("%d", &k);
    findKSmall(a, 0, count-1, k);
    for(i = 0; i < count; i++){
        printf("%d ", a[i]);
    }

    printf("\n%d\n", a[k-1]);

}

  結(jié)果截圖

5、無序找第k大值

 快排的降序?qū)崿F(xiàn)思想，在加上遞歸查找；

 (1)、代碼實(shí)現(xiàn)

#include

void findKBigger(int *a, int start, int end, int key);

void findKBigger(int *a, int start, int end, int key){
    int i = start;
    int j = end;
    int tmp = a[i];
//快排中的降序
    while(i < j){
        while(i < j && a[j] < tmp){
            j--;
        }
        if(i < j){
            a[i++] = a[j];
        }
        while(i < j && a[i] > tmp){
            i++;
        }
        if(i < j){
            a[j--] = a[i];
        }
    }
    a[i] = tmp;

    if(key-1 < i){
        findKBigger(a, 0, i-1, key);
    }else if(key-1 > i){
        findKBigger(a, i+1, end, key);
    }else{
        return;
    }
}

void main(void){
    int a[] = {8, 4, 6, 9, 2, 3, 7, 9, 11, 10};
    int count = sizeof(a)/sizeof(int);
    int k;
    int i;

    printf("請(qǐng)輸入要查找的第k大的數(shù)：");
    scanf("%d", &k);
    findKBigger(a, 0, count-1, k);
    for(i = 0; i < count; i++){
        printf("%d ", a[i]);
    }

    printf("\n%d\n", a[k-1]);

}

  (2)、結(jié)果截圖

6、線性算法

  (1)、劃分為5個(gè)一組的元素，在找出每一組的中值(對(duì)這5個(gè)數(shù)進(jìn)行排序，找出中值)，時(shí)間復(fù)雜度：O(n)

  (2)、用遞歸去找這些中值中的那一個(gè)中值(中值中的中值)；

  (3)、此時(shí)用這個(gè)最中值的下標(biāo)和k作比較，之后和上面的隨機(jī)選擇算法一樣！??！

具體模型如下：

算法分析

  找中值和第k小數(shù)時(shí)間復(fù)雜度均為：O(n)；比較好的解決了上述最壞時(shí)間復(fù)雜度為O(n^2)的情況；

  3個(gè)元素一組的話，結(jié)果不成立；

 5是這個(gè)算法能成功的最小數(shù)字，7個(gè)元素為一組算法也能成立，但是性能不會(huì)有所提高；