求數組中第K大的數可以基於快排序思想，步驟如下：
1、隨機選擇一個支點
2、將比支點大的數，放到數組左邊；將比支點小的數放到數組右邊；將支點放到中間(屬於左部分)
3、設左部分的長度為L，
當K < L時，遞歸地在左部分找第K大的數
當K > L時，遞歸地在有部分中找第(K - L)大的數
當K = L時，返回左右兩部分的分割點（即原來的支點），就是要求的第K大的數
以上思想的代碼實現如下：
代碼如下：
/**
線性時間復雜度求數組中第K大數
** author :liuzhiwei
** data :2011-08-07
**/
#include "iostream"
using namespace std;
//基於快速排序思想，求數組a中第k大的數，low和high分別為數組的起始和結束位置
//時間復雜度為o(n)，n為數組的長度
//1<=k<=n
//如果存在，返回第k大數的下標，否則返回-1
int selectk(int a[], int low, int high, int k)
{
if(k <= 0)
return -1;
if(k > high - low + 1)
return -1;
int pivot = low + rand()%(high - low + 1); //隨即選擇一個支點
swap(a[low], a[pivot]);
int m = low;
int count = 1;
//一趟遍歷，把較大的數放到數組的左邊
for(int i = low + 1; i <= high; ++i)
{
if(a[i] > a[low])
{
swap(a[++m], a[i]);
count++; //比支點大的數的個數為count-1
}
}
swap(a[m], a[low]); //將支點放在左、右兩部分的分界處
if(count > k)
{
return selectk(a, low, m - 1, k);
}
else if( count < k)
{
return selectk(a, m + 1, high, k - count);
}
else
{
return m;
}
}
int main(void)
{
int a[] = {5, 15, 5, 7, 9, 17,100, 3, 12, 10, 19, 18, 16, 10, 1000,1,1,1,1,1,1,1,1};
int r = selectk(a, 0, sizeof(a) /sizeof(int) - 1, 5);
cout<<(r == -1 ? r : a[r])<<endl;
system("pause");
return 0;
}
稍微改動一下，就可以修改為求數組中第K小數
完整的代碼如下：
代碼如下：
/**
線性時間復雜度求數組中第K小數
** author :liuzhiwei
** data :2011-08-07
**/
#include "iostream"
using namespace std;
//基於快速排序思想，求數組a中第k小的數，low和high分別為數組的起始和結束位置
//時間復雜度為o(n)，n為數組的長度
//1<=k<=n
//如果存在，返回第k小數的下標，否則返回-1
int selectk(int a[], int low, int high, int k)
{
if(k <= 0)
return -1;
if(k > high - low + 1)
return -1;
int pivot = low + rand()%(high - low + 1); //隨即選擇一個支點
swap(a[low], a[pivot]);
int m = low;
int count = 1;
//一趟遍歷，把較小的數放到數組的左邊
for(int i = low + 1; i <= high; ++i)
{
if(a[i]<a[low])
{
swap(a[++m], a[i]);
count++; //比支點小的數的個數為count-1
}
}
swap(a[m], a[low]); //將支點放在左、右兩部分的分界處
if(k < count)
{
return selectk(a, low, m - 1, k);
}
else if( k > count)
{
return selectk(a, m + 1, high, k - count);
}
else
{
return m;
}
}
int main(void)
{
int a[] = {5, 15, 5, 7, 9, 17,100, 3, 12, 10, 19, 18, 16, 10, 1000,1,1,1,1,1,1,1,1};
int r = selectk(a, 0, sizeof(a) /sizeof(int) - 1, 23);
cout<<(r == -1 ? r : a[r])<<endl;
system("pause");
return 0;
}
