摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 分堆作插入排序+前插+後插

我是分成2500堆

也就是

0~3999 放一堆
4000~7999 放一堆...類推

之後對一個輸入的數字做排序時,找到它是要放第幾堆

找到之後,讓它比較該堆的中位數
若>中位數 , 從後面插入
若<中位數 , 從前面插入
剩餘的部分都是小細節 自己看看程式碼吧!

誰能提供更好的解法!!

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
int num[2502][4000]={0},top[2502]={0},down[2502]={0};
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
main()
{
  int data,a,b,c,time=0;
  char s[10];
  for(a=0;a<2500;a++)
    {top[a]=2000;down[a]=2000;}
  while(scanf("%s",s)==1&&s[0]!='E')
      {
        data=input();
        int divide=data/4000;
        if(s[0]=='G')
           {
             if(data>num[divide][top[divide]+down[divide]/2])
              {
              num[divide][++top[divide]]=data;
              for(a=top[divide];a>down[divide];a--)
                 if(num[divide][a]>num[divide][a-1])
                    {
                       int temp=num[divide][a];
                       num[divide][a]=num[divide][a-1];
                       num[divide][a-1]=temp;
                    }
                 else break;
              }
              else
              {
               num[divide][--down[divide]]=data;
               for(a=down[divide];a<top[divide];a++)
                  if(num[divide][a]<num[divide][a+1])
                     {
                        int temp=num[divide][a];
                        num[divide][a]=num[divide][a+1];
                        num[divide][a+1]=temp;
                     }
                  else break;
              }
           }
        else
           {
              for(a=2501;a>=0;a--)
                 if(data>top[a]-down[a])
                    data-=(top[a]-down[a]);
                 else
                    {
                      printf("%d\n",num[a][down[a]+data-1]);break;
                    }
           }
      }
  return 0;
}