基本思想:先遍历K个元素,将其存到大小为K的数组中,对这K个元素,利用选择排序,找到K个数中的最大数kmax(kmax设为k个元素的数组中最大元素),用时O(k),然后记录遍历后n-k个数,x与kmax比较:如果x
实现代码如下:
-
//利用选择排序查找最小的k个元素
-
-
-
#include<iostream>
-
using namespace std;
-
-
void swap(int &a,int &b)
-
{
-
int tmp;
-
tmp=a;
-
a=b;
-
b=tmp;
-
}
-
-
-
int FindKMax(int a[],int k)
-
{
-
int i;
-
int max=0;
-
for(i=1;i<k;i++)
-
{
-
if(a[i]>a[max])
-
max=i;
-
}
-
return max;
-
}
-
-
-
-
int main()
-
{
-
int i,k,n;
-
int a[20];
-
printf("please input the array size:\n");
-
scanf("%d",&n);
-
printf("please input the array:\n");
-
for(i=0;i<n;i++)
-
scanf("%d",&a[i]);
-
printf("please input k:\n");
-
scanf("%d",&k);
-
int max=FindKMax(a,k);
-
for(i=n-k;i<n;i++)
-
{
-
if(a[i]<a[max])
-
{
-
swap(a[i],a[max]);
-
max=FindKMax(a,k);
-
}
-
}
-
for(i=0;i<k;i++)
-
cout<<a[i]<<" ";
-
return 0;
- }