黑马程序员技术交流社区

标题: 如何只用一个小容量数组或列表来排序大量的数据 [打印本页]

作者: hanrongle    时间: 2013-8-15 08:45
标题: 如何只用一个小容量数组或列表来排序大量的数据
如题所述,限制条件是只用一个数组或列表,而且大小很小比如10来排序比如100个甚至1000或者10000个随机数,不能再用数组或列表或其他集合类的数据结构了,怎么排???小弟我想了好久还没有一个比较好的方案,于是上来请大家给点思路,谢谢。
作者: 黑马-张明    时间: 2013-8-15 15:48
  1. package src;

  2. import java.io.*;
  3. public class OutSort {
  4.     static int[] arr=new int[10];
  5.     final static int MAXCOUNT=1000;
  6.     public static void createRandomNumberFile() throws IOException {
  7.         RandomAccessFile raf = new RandomAccessFile("raw", "rw");
  8.         FileOutputStream fos = new FileOutputStream("d://source.txt");
  9.         PrintStream ps = new PrintStream(fos);
  10.         PrintStream   old   =   System.out;  
  11.         System.setOut(ps);
  12.         int randomNum;
  13.         for (int i = 0; i < MAXCOUNT; i++) {
  14.             randomNum = (int) (Math.random() * 10000);
  15.             raf.writeInt(randomNum);

  16.             System.out.print(randomNum + "/t");
  17.             if ((i + 1) % 5 == 0) {
  18.                 System.out.println();
  19.             }
  20.         }
  21.         System.setOut(old);
  22.         ps.close();
  23.         fos.close();
  24.     }
  25.    
  26.      public static void main(String[] args) throws IOException
  27.     {
  28.          RandomAccessFile rafa[] = new RandomAccessFile[10];//外部文件 等待归并
  29.          RandomAccessFile rafb = null;                        //外部文件 归并目标
  30.          int min;                                            //等待归并的元素 定位
  31.          int cnt_all=0;                                        //1000个计数
  32.          
  33.          createRandomNumberFile();
  34.          
  35.          for (int i = 0; i < 100; i++) {
  36.              readRandomNumberFile("raw",i*10,10);    //读10个
  37.              sort_arr();                            //排序
  38.              writeRandomNumberFile("raw10_"+i,0,10);    //写小文件
  39.              Raw2Txt("raw10_"+i,"sort10_"+i+"+.txt",10);
  40.          }
  41.          
  42.          for (int i = 0; i < 10; i++) {
  43.              rafb=new RandomAccessFile("raw100_"+i, "rw");
  44.              //读入10个
  45.              for (int j = 0; j < 10; j++) {
  46.                  rafa[j]=new RandomAccessFile("raw10_"+(10*i+j), "rw");
  47.                  arr[j]=rafa[j].readInt();
  48.              }
  49.              //剩余90个
  50.              for (int j = 0; j < 100; j++) {
  51.                  min=0;
  52.                  for (int k = 0; k< 10; k++) {
  53.                      if(arr[k]!=-1)
  54.                          min=k;
  55.                  }
  56.                  //找到最小
  57.                  for (int k = 0; k< 10; k++) {
  58.                      System.out.print(""+" || "+arr[k] );
  59.                      System.out.println();
  60.                      
  61.                      if(arr[k]<arr[min]&&arr[k]!=-1)
  62.                          min=k;
  63.                  }
  64.                  //保存
  65.                  if(arr[min]!=-1){
  66.                      rafb.writeInt(arr[min]);                     
  67.                  }

  68.                  
  69.                  //替补读入
  70.                  System.out.println(""+" || "+j +" || "+min+" || "+arr[min]);
  71.                  
  72.                  if( rafa[min].getFilePointer() < rafa[min].length()&& arr[min]!=-1)
  73.                  {
  74.                          arr[min]=rafa[min].readInt();                     
  75.                  }
  76.                  else
  77.                  {
  78.                          arr[min]=-1;                        
  79.                  }
  80.              }            
  81.          }   
  82.          
  83.          
  84.          
  85.          rafb=new RandomAccessFile("raw1000", "rw");
  86.          //读入10个
  87.          for (int i = 0; i < 10; i++) {
  88.              rafa[i]=new RandomAccessFile("raw100_"+i, "rw");
  89.              Raw2Txt("raw100_"+i,"sort100_"+i+".txt",100);            
  90.              arr[i]=rafa[i].readInt();
  91.          }
  92.          //剩余990个
  93.          for (int i = 0; i < 1000; i++) {
  94.              min=0;
  95.              for (int k = 0; k< 10; k++) {
  96.                  if(arr[k]!=-1)
  97.                      min=k;
  98.              }
  99.              //找到最小
  100.              for (int k = 0; k< 10; k++) {
  101.                  System.out.print(""+" || "+arr[k] );
  102.                  System.out.println();
  103.                  
  104.                  if(arr[k]<arr[min]&&arr[k]!=-1)
  105.                      min=k;
  106.              }
  107.             //保存
  108.              cnt_all++;
  109.              System.out.println(""+" ||----------------------------------------> "+cnt_all );            
  110.              if(arr[min]!=-1){
  111.                  rafb.writeInt(arr[min]);                     
  112.              }
  113.              //替补读入
  114.              System.out.println(""+" || "+i +" || "+min+" || "+arr[min]);
  115.              System.out.println(""+"++++++++++++++++++++++++++++++++++++++");            
  116.              if( rafa[min].getFilePointer() < rafa[min].length()  && arr[min]!=-1)
  117.              {
  118.                      arr[min]=rafa[min].readInt();                     
  119.              }
  120.              else
  121.              {
  122.                      arr[min]=-1;                        
  123.              }
  124.          }   
  125.          
  126.          Raw2Txt("raw1000","sort1000.txt",1000);
  127.     }
  128.      public static void sort_arr(  ){
  129.              int tmp;
  130.             for (int i = 0; i < 9; i++) {
  131.                 for (int j = i+1; j < 10; j++) {
  132.                     if(arr[i] > arr[j])
  133.                     {
  134.                         tmp=arr[i];
  135.                         arr[i]=arr[j];
  136.                         arr[j]=tmp;
  137.                     }
  138.                 }               
  139.             }
  140.         }     
  141.     //从位置m,读入n个整数到arr数组   
  142.     public static void readRandomNumberFile(String file,long m,long n) throws IOException
  143.     {
  144.         RandomAccessFile raf = new RandomAccessFile(file, "rw");
  145.         raf.seek(Integer.SIZE/8*(m));
  146.         for (int i = 0; i < n; i++) {
  147.             arr[i]=raf.readInt();
  148.         }
  149.     }
  150.     //从位置m,将arr数组的n个整数写入文件      
  151.     public static void writeRandomNumberFile(String file,long m,long n) throws IOException
  152.     {
  153.         RandomAccessFile raf = new RandomAccessFile(file, "rw");
  154.         raf.seek(Integer.SIZE/8*(m));
  155.         for (int i = 0; i < n; i++) {
  156.             raf.writeInt(arr[i]);
  157.         }
  158.     }
  159.     public static void Raw2Txt(String src,String dst,long n) throws IOException {
  160.         int tmp;
  161.         RandomAccessFile raf = new RandomAccessFile(src, "rw");
  162.         FileOutputStream fos = new FileOutputStream(dst);
  163.         PrintStream ps = new PrintStream(fos);
  164.         System.out.println(""+"file of int "+(raf.length()/4));
  165.         PrintStream   old   =   System.out;  
  166.         System.setOut(ps);
  167.         for (int i = 0; i < n; i++) {
  168.             tmp =raf.readInt();
  169.             System.out.print(tmp + "/t");
  170.             if ((i + 1) % 5 == 0) {
  171.                 System.out.println();
  172.             }
  173.         }
  174.         System.setOut(old);
  175.         ps.close();
  176.         fos.close();
  177.     }   
  178. }
复制代码

作者: 神之梦    时间: 2013-8-15 23:06
楼上哥们好给力




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2