用直接选择排序实现查找最小的K个数

1350阅读 0评论2013-08-25 double_lq
分类:C/C++

利用直接选择排序查找最小的K个元素的基本思想是:
   基本思想:先遍历K个元素,将其存到大小为K的数组中,对这K个元素,利用选择排序,找到K个数中的最大数kmax(kmax设为k个元素的数组中最大元素),用时O(k),然后记录遍历后n-k个数,xkmax比较:如果x,则x代替kmax,并再次重新找出K个元素的数组中最大元素kmax·;如果x>kamx,则不更新数组。

实现代码如下:
  
  1. //利用选择排序查找最小的k个元素


  2. #include<iostream>
  3. using namespace std;

  4. void swap(int &a,int &b)
  5. {
  6.     int tmp;
  7.     tmp=a;
  8.     a=b;
  9.     b=tmp;
  10. }


  11. int FindKMax(int a[],int k)
  12. {
  13.     int i;
  14.     int max=0;
  15.     for(i=1;i<k;i++)
  16.     {
  17.         if(a[i]>a[max])
  18.             max=i;
  19.     }
  20.     return max;
  21. }



  22. int main()
  23. {
  24.     int i,k,n;
  25.     int a[20];
  26.     printf("please input the array size:\n");
  27.     scanf("%d",&n);
  28.     printf("please input the array:\n");
  29.     for(i=0;i<n;i++)
  30.         scanf("%d",&a[i]);
  31.     printf("please input k:\n");
  32.     scanf("%d",&k);
  33.     int max=FindKMax(a,k);
  34.     for(i=n-k;i<n;i++)
  35.     {
  36.      if(a[i]<a[max])
  37.         {
  38.          swap(a[i],a[max]);
  39.             max=FindKMax(a,k);
  40.         }
  41.     }
  42.     for(i=0;i<k;i++)
  43.         cout<<a[i]<<" ";
  44.     return 0;
  45. }
  

 

上一篇:简单选择排序算法的实现
下一篇:冒泡排序的三种实现方法