查找最小的k个元素 （C语言代码）

解题思路:

    1.对于初学者来说，可能会对n个整数用冒泡或者选择排序从小到大排序，然后输出最小的k个数即可。

    2.但是如果数据量真的到1万或者10万的话，用普通排序肯定会超时哦，可以用桶排序来实现。如果数据量在1万之内，也可以直接用简化版的桶排序就可以了，建议大家学一下这种方法哦。


参考代码:

//方法1：选择排序，自己写排序算法
#include<stdio.h>
int main()
{
	int a[10001],n,min,i,j,k,t;
	scanf("%d%d",&n,&k);  //n表示个数，k表示查找最小k个 
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(i=0;i<n-1;i++) //选择排序 
	{ 
		min=i;  //min表示每一趟最小值下标 
		for(j=i;j<n;j++)
			if(a[min]>a[j])
				min=j;
		if(min!=i)
		{
			t=a[i];a[i]=a[min];a[min]=t;
		}
	}
	for(i=0;i<k;i++) //输出最小k个数 
	{
		printf("%d",a[i]);
		if(i!=k)
			printf(" ");
	}		
	return 0;
}

//方法2：这一题数据量应该不够，如果真的有10000个数据排序，用普通的排序方法会超时哦。所以可以用桶排序。
//在这里因为数据只有10000个，也不多。可以用简化版的桶排序就可以了。桶排序Bucket Sort
//请看源程序吧，还是用C语言写的。
#include<stdio.h>
#include<string.h>
#define N 10000+5
int main()
{
	int bucket[N]={0}; //bucket 是桶的意思 Bucket Sort（桶排序） 
	int i,n,k,index; 
	scanf("%d%d",&n,&k);  //n表示个数，k表示查找最小k个 
	memset(bucket,0,sizeof(bucket));  //清零，这里也可以不要，因为数组定义初始化为0了 
	for(i=0;i<n;i++)
	{ 
		scanf("%d",&index);
		bucket[index]++;    //按输入的数据作为下标，放到桶里面去，统计该数出现的次数。
		//例如输入10，则bucket[10]++,bucket[10]=1,下次再输入10，会得到bucket[10]=2 
	}
	index=0;  
	while(k) //输出最小k个数 
	{
		if(bucket[index]==0) //如果为0，表示没有出现index,否则就是index出现bucket[index]次 
		{
			index++;
		} 
		else //index出现bucket[index]次 ,输出 
		{
			printf("%d ",index);
			bucket[index]--; 
			k--;  //输出之后才减1，不输出不能减1哦 
		}
	}		
	return 0;
}