算法思想：找一个点，然后放到末尾，然后将小于这个数的值放在数组前面，大于这个值的放在数组后面，然后在将这个末尾的数放回。这个末尾数放入的位置i代表已经找到第i小的数，放入的位置如果是k，就找到了第k小的数

同样找到第k大的数类似的解法，找到前k个最大数也一样。找一个数组的中位数也一样做。求n个数组的中位数也一样的做。求n个数组的前k个大数或小数也类似可以做。

代码：

/***************************************
输入: n:数组元素的个数 k:第几大的数
a:待查找的数组元素
****************************************/
#include
#include
#include

#define N 100

void Rand_select( int*, int, int );
int partition( int*, int, int );
int swap( int&, int& );
int k, ans;

int main()
{
int n, a[N], i;
while( scanf( “%d%d”, &n, &k ) != EOF )
{
srand(time(NULL));
k–;
for( i = 0; i < n; i++ )
scanf( “%d”, a + i );
Rand_select( a, 0, n-1 );
printf( “%d\n”, ans );
}
return 0;
}

void Rand_select( int a[], int p, int q )
{
int m;
if (p <= q)
{
m = partition( a, p, q );
if( k == m )
{ ans = a[m]; return; }
else if( k > m )
Rand_select( a, m+1, q );
else
Rand_select( a, p, m-1 );
}
}

int partition( int a[], int p, int q )
{
int last, i;
if( q != p )
swap( a[rand()%(q-p)+p], a[p] );
for( i = p+1, last = p; i <= q; i++ )
if( a[i] >= a[p] )
swap( a[i], a[++last] );
swap( a[last], a[p] );
return last;
}

int swap( int &p, int &q )
{
int temp = p;
p = q;
q = temp;
return 0;
}

#include ;
using namespace std;

void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}

int k_smallest(int k, int a[], int left, int right)
{
int pivot = a[right]; //the last item as pivot
int i = left;
int j = right-1;
for(;;)
{
for(; a[i] for(; a[j]>;=pivot; j–);
if(i swap(a[i], a[j]);
else
break;
}
swap(a[i], a[right]);
//now i is the pivot index in the array
//i.e. a[i] is the (i+1)th smallest item

if(k==i-left+1)
return a[i];
else if(k < i-left+1) //target before pivot
return k_smallest(k, a, left, i-1);
else //target after pivot
return k_smallest((k-(i-left+1)), a, i+1, right);
}

//find the k_th smallest item in the array
int Kth_smallest(int k, int a[], int size)
{
return k_smallest(k, a, 0, size-1);
}

int main()
{
int a[10] = {4, 8, 1, 5, 2, 9, 3, 7, 10, 6};

for(int i=1; i<=10; i++)
cout< }

可以先用快速排序进行排序，其中用另外一个进行地址查找
代码如下，在VC++6.0运行通过。给分吧^-^

//快速排序

#include

using namespace std;

int Partition (int *L,int low,int high)
{
int temp = L[low];
int pt = L[low];

while (low < high)
{
while (low < high && L[high] >= pt)
–high;
L[low] = L[high];
while (low < high && L[low] <= pt)
++low;
L[low] = temp;
}
L[low] = temp;

return low;
}

void QSort (int *L,int low,int high)
{
if (low < high)
{
int pl = Partition (L,low,high);

QSort (L,low,pl – 1);
QSort (L,pl + 1,high);
}
}

int main ()
{
int narry[100],addr[100];
int sum = 1,t;

cout << “Input number:” << endl;
cin >> t;

while (t != -1)
{
narry[sum] = t;
addr[sum - 1] = t;
sum++;

cin >> t;
}

sum -= 1;
QSort (narry,1,sum);

for (int i = 1; i <= sum;i++)
cout << narry[i] << ‘\t’;
cout << endl;

int k;
cout << “Please input place you want:” << endl;
cin >> k;

int aa = 1;
int kk = 0;
for (;;)
{
if (aa == k)
break;
if (narry[kk] != narry[kk + 1])
{
aa += 1;
kk++;
}

}

cout << “The NO.” << k << “number is:” << narry[sum - kk] << endl;
cout << “And it’s place is:” ;
for (i = 0;i < sum;i++)
{
if (addr[i] == narry[sum - kk])
cout << i << ‘\t’;
}

return 0;
}

这道题去年baidu笔试也出现过，当时写的是这个答案，高手分析下：
#include
#include
#include
#include
#include
using namespace std;

#define n 10
#define k 5