Chinaunix首页 | 论坛 | 博客
  • 博客访问: 543212
  • 博文数量: 129
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1888
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-20 11:09
文章分类

全部博文(129)

文章存档

2016年(1)

2015年(5)

2014年(64)

2013年(59)

我的朋友

分类: C/C++

2013-08-25 16:15:30

利用直接选择排序查找最小的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. }
  

 

阅读(1357) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~