yxCoding

I am a coder

找数组中第k大的数

yxjoey posted @ 2008年3月27日 11:20 in C语言 with tags c 程序 , 3302 阅读

今天复习的时候遇到这个题目，觉得挺有意思，而且搜索一下，网上解法各式各样，从冒泡，选择..到快速排序，堆排序。我不是想得到效率最高的算法，只是想练习一下。

  1. /* @(#)find_orderk.c
  2. */
  3. #include <stdio.h>
  4. int find_orderk1(const int* narray,const int n,const int k){
  5.   int top[k+1];
  6.   int i,j;
  7.   for(i=0; i<k+1; i++)
  8.     top[i]=-1000;
  9.   for(i=0; i<n; i++){
  10.     for(j=k; j>0; j--)
  11.       if(narray[i]>top[j-1])
  12.         top[j]=top[j-1];
  13.       else
  14.         break;
  15.     if(j!=k)
  16.       top[j]=narray[i];
  17.   }
  18.   return top[k-1];
  19. }
  20.  
  21. void swap(int *a, int *b){
  22.   int tmp = *a;
  23.   *a = *b;
  24.   *b = tmp;
  25. }
  26.  
  27. void shiftdown(int *narray, const int n, const int k){
  28.   int biggest=k;
  29.   if(2*k+1<n&&narray[biggest]<narray[2*k+1])
  30.     biggest = 2*k+1;
  31.   if(2*k+2<n&&narray[biggest]<narray[2*k+2])
  32.     biggest = 2*k+2;
  33.   if(biggest!=k){
  34.     swap(&narray[biggest], &narray[k]);
  35.     shiftdown(narray, n, biggest);
  36.   }
  37. }
  38.  
  39. void shiftup(int *narray, const int n, const int k){
  40.   int bigger=k;
  41.   if(narray[bigger]<narray[k/2])
  42.     bigger = k/2; 
  43.   if(bigger!=k/2){
  44.     swap(&narray[bigger], &narray[k/2]);
  45.     shiftup(narray, n, k/2);
  46.   }
  47. }
  48.  
  49. void printheap(int *narray, const int n){
  50.   int i;
  51.   for(i=0; i<n; i++){
  52.     printf("%d\t", narray[i]);
  53.     if(((i+2)&i)==0)
  54.       printf("\n");
  55.   }
  56.   printf("\n=========\n");
  57. }
  58.  
  59. int find_orderk2(const int* narray,const int n,const int k){
  60.   int new_array[n];
  61.   int i;
  62.   //Build maxHeap
  63.   for(i=0; i<n; i++){
  64.     new_array[i]=narray[i];
  65.     shiftup(new_array, i+1, i);
  66.   }
  67.   for(i=1; i<k; i++){
  68.     swap(&new_array[0], &new_array[n-i]);
  69.     shiftdown(new_array, n-i-1, 0);
  70.     printheap(new_array, n-i-1);
  71.   }
  72.   return new_array[0];
  73. }
  74.  
  75. int main(int argc, char *argv[]){
  76.   int array[]={1,5,2,98,3221,4532,3421,32143,5,68,-3, 65321,44,-34};
  77.   printf("\n%d\n", find_orderk2(array, sizeof(array)/sizeof(array[0]), 6));
  78.   printf("\n%d\n", find_orderk1(array, sizeof(array)/sizeof(array[0]), 6));
  79. }
  80.  

堆排序这个算法不错，就是建立堆的时候挺耗的。

Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

yxjoey

分类

标签云

最新评论

最新留言

友情链接

我的豆瓣收藏

浏览计数器

64200
designed by: Website Builder | coded by: Web Hosting Geeks | Host by is-Programmer.com | Power by Chito 1.3.3 beta