封裝成函數(shù)：
#include <malloc.h>
void swap(int *a,int i,int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int *a,int lo,int hi)
{
int i,j;
i=lo;
j=hi+1;
while(1)
{
while(a[++i]<=a[lo])
{
if(i==hi)
{
break;
}
}
while(a[--j]>a[lo])
{
if(j==lo)
{
break;
}
}
if(i>=j)
{
break;
}
swap(a,i,j);
}
swap(a,lo,j);
return j;
}
int* copy_of(int *a,int len)
{
int *ret = (int*)malloc(sizeof(int)*len);
int i;
for(i=0; i<len; i++)
{
ret[i] = a[i];
}
return ret;
}
//選出第k小元素纱昧，k為1~len
int select_kth_min(int *a, int len,int k)
{
k--;
int lo = 0, hi = len - 1;
while (1)
{
int j = partition(a, lo, hi);
if (j < k)
{
lo = j + 1;
}
else if (j > k)
{
hi = j - 1;
}
else
{
return a[k];
}
}
}
//選出中位數(shù)（比一半的元素小刨啸，比另一半的大）
int select_mid(int *a,int len)
{
return select_kth_min(a, len, len / 2);
}
//選出k個(gè)最小元素，k為1~len
int* select_k_min(int *a, int len,int k)
{
int lo = 0, hi = len - 1;
while (1)
{
int j = partition(a, lo, hi);
if (j < k)
{
lo = j + 1;
}
else if (j > k)
{
hi = j - 1;
}
else
{
return copy_of(a, k);
}
}
}
測(cè)試：
#include <stdio.h>
//打印輸出數(shù)組
void print_arr(int *a,int len)
{
int i;
if(len<1) //數(shù)組長(zhǎng)度必須大于0
{
printf("length greater than 0");
return;
}
//打印整個(gè)數(shù)組
printf("[");
for(i=0; i<len-1; i++)
{
printf("%d ",a[i]);
}
printf("%d]\n",a[len-1]);
}
int main()
{
int a[] = {9,0,6,5,8,2,1,7,4,3};
int len = sizeof(a)/sizeof(int);
printf("%d\n",select_kth_min(a,len,1));//第1小元素：0
printf("%d\n",select_mid(a,len));//中位數(shù)：4
print_arr(select_k_min(a,len,5),5);//最小的5個(gè)數(shù)：0~4
return 0;
}
輸出：
0
4
[0 1 2 3 4]
