本文為原創(chuàng)，如需轉載，請注明作者和出處，謝謝！

????第一種算法是最容易想到的，就是利用快速排序的思想，將一個數(shù)組分成以某一個數(shù)X為軸，左邊的所有的數(shù)都比X小，而右邊的數(shù)都比X大。但我快速排序不同的是，在這個算法中只考慮X的一邊，而不是兩邊都考慮。?

?? 如果X的位置是i,那么要得到第k個數(shù)，如果k<=i, 那么這個數(shù)一定在i的左邊，否則在i的右邊。

源碼如下：

#include?<stdio.h>
#include?<stdlib.h>
int?new_random(int?min,?int?max)
{
????return?(min?+?(int)(((float)rand()/RAND_MAX)*(max?-?min)));
}
void?swap(int?*a,?int?*b)
{
????int?c?=?*a;
????*a?=?*b;
????*b?=?c;
}

int?partition(int?A[],?int?p,?int?r)
{
????int?i?=?p?-?1,?j;
????for(j?=?p;?j?<?r;?j++)
????{
????????if(A[j]?<=?A[r])
????????{
????????????i++;
????????????swap(&A[i],?&A[j]);
????????}
????}
????swap(&A[i?+?1],?&A[r]);
????return?i?+?1;
}

int?randomize_partition(int?A[],?int?p,?int?r)
{
????int?i?=?new_random(p,?r);
????swap(&A[i],?&A[r]);
????return?partition(A,?p,?r);
}

//第一種算法
int?randomized_select(int?data[],?int?p,?int?r,?int?k)
{
????if(k?>?(r?-?p?+?1))?return?0;
????if(p?==?r)?return?data[p];
????int?i?=?randomize_partition(data,?p,?r);
????//int?i?=?partition(data,?p,?r);?//不好使，死循環(huán),?必須用隨機數(shù)，在第二步時總是在最大數(shù)處劃分

????int?count?=?i?-?p?+?1;
????if(k?<=?count)
????????return?randomized_select(data,?p,?i,?k);
????else
????????return?randomized_select(data,?i?+?1,?r,?k?-?count);
}

??? 另外一種對這種算法做了一下改進，即將數(shù)組每5個數(shù)一組進行排序，然后取得它的中位數(shù)，再對這些中位數(shù)進行排序。然后先出的軸X最比較好的，因此X的左邊和右邊的數(shù)總是很平均，所以平均查找速度更快。算法如下：

void?quicksort(int?data[],?int?b,?int?e)
{
????if(b?<?e)
????{
????????int?k?=?partition(data,?b,?e);
????????quicksort(data,?b,?k?-?1);
????????quicksort(data,?k?+?1,?e);
????}
}

int?partition1(int?A[],?int?p,?int?r,?int?x)
{
????int?i?=?p?-?1,?j;
????for(j?=?p;?j?<=?r;?j++)
????{
????????if(A[j]?<=?x)
????????{
????????????i++;
????????????swap(&A[i],?&A[j]);
????????}
????}
????A[i?+?1]?=?x;
????return?i?+?1;
}
//第二種算法
int?select_new(int?data[],?int?p,?int?r,?int?k)
{
????if(r?-?p?<?75)
????{
????????quicksort(data,?p,?r);
????????return?data[p?+?k?-?1];
????}???
????int?i;
????for(i?=?0;?i?<=?(r?-?p?-?4)?/?5;?i++)
????{
????????quicksort(data,?p?+?5?*?i,?p?+?5?*?i?+?4);
????????swap(&data[p?+?5?*?i?+?2],?&data[p?+?i]);
????}
????int?x?=?select_new(data,?p,?p?+?(r?-?p?-?4)?/?5,?(r?-?p?-?4)/10);?//?得到更好的軸X
????i?=?partition1(data,?p,?r,?x);
????int?count?=?i?-?p?+?1;?
????if(k?<=?count)
????????return?select_new(data,?p,?i,?k);
????else
????????return?select_new(data,?i?+?1,?r,?k?-?count);
}

int?main()
{
????int?data[]?=?{3,?1,?7,?34,?8,?11,?678,?12,?-1,?100};
????printf("%d\n",?randomized_select(data,?0,?9,?2));
????int?data1[]?=?{3,?1,?7,?34,?8,?11,?678,?12,?-1,?100};
????printf("%d\n",?select_new(data1,?0,?9,?2));
???
?????return?0;
} 本文轉自銀河使者博客園博客，原文鏈接http://www.cnblogs.com/nokiaguy/archive/2008/05/12/1193986.html如需轉載請自行聯(lián)系原作者
銀河使者

總結

以上是生活随笔為你收集整理的得到第K个大的数算法研究的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。