1. 爱易网页
  2. Java教程
  3. 算法有关问题，着急

算法有关问题，着急

日期：2014-05-20　 浏览次数：21105 次

算法问题，请教高手！！~~着急。。
如何只用一个大小为10的数组或列表来排序1000个随机整数?,但数组或列表之类的集合数据结构只可以用一个(大小为10的数组或列表).使用Java语言实现.请大家指点下,谢谢。我把我所有的分都贡献出来了。。。

------解决方案--------------------
只有伪代码,java不懂，我是用c语言实现过，思路可以参考下

void item_swap(int i，int j);// 需要实现交换文件上第i项和第j项的值
int get_value_from_file(int i); // 需要实现从文件中取第i项的值

// 把数据根据divide_value分为两部分，
static G_LONG partition(G_LONG start, G_LONG end)
{
G_LONG i = start;
G_LONG j = end + 1;
G_LONG divide_value = 0;


int x = rand();
x = absolute_value(x);
x = x % (j - i);
divide_value = get_value_from_file(start + x); 
item_swap(i, start + x);

while(1)
{
while(get_value_from_file(++i) < divide_value && i < end);
while(get_value_from_file(--j) > divide_value && j > start);
if(i >= j)
break;
item_swap(i, j);
}

item_swap(start, j);

return j;
}


static void quick_sort(G_LONG start, G_LONG end)
{
int devide;

if(start < end)
{ 
devide = partition(start, end);
quick_sort(start, devide - 1); // 前半段排序
quick_sort(devide + 1, end); // 后半段排序
}
}
------解决方案--------------------
调试完成，各位高手看看可以么。
楼主要给点分哦，我从下班回来 19：30 调试到 凌晨1：12 。
不过我也进步了，平时没有这么钻研过。
代码如下：我保留了程序输出的中间结果文件，楼主可以检查是否正确，使用时去掉即可，最后结果，raw1000 sort1000.txt
Java code


import java.io.*;
public class waibupaixu {
    static int[] arr=new int[10];
    final static int MAXCOUNT=1000;
    public static void createRandomNumberFile() throws IOException {
        RandomAccessFile raf = new RandomAccessFile("raw", "rw");
        FileOutputStream fos = new FileOutputStream("source.txt");
        PrintStream ps = new PrintStream(fos);
        PrintStream   old   =   System.out;  
        System.setOut(ps);
        int randomNum;
        for (int i = 0; i < MAXCOUNT; i++) {
            randomNum = (int) (Math.random() * 10000);
            raf.writeInt(randomNum);

            System.out.print(randomNum + "\t");
            if ((i + 1) % 5 == 0) {
                System.out.println();
            }
        }
        System.setOut(old);
        ps.close();
        fos.close();
    }
    
     public static void main(String[] args) throws IOException 
    {
         RandomAccessFile rafa[] = new RandomAccessFile[10];//外部文件 等待归并
         RandomAccessFile rafb = null;                        //外部文件 归并目标
         int min;                                            //等待归并的元素 定位
         int cnt_all=0;                                        //1000个计数
         
         createRandomNumberFile();
         
         for (int i = 0; i < 100; i++) {
             readRandomNumberFile("raw",i*10,10);    //读10个
             sort_arr();                            //排序
             writeRandomNumberFile("raw10_"+i,0,10);    //写小文件
             Raw2Txt("raw10_"+i,"sort10_"+i+"+.txt",10);
         }
         
         for (int i = 0; i < 10; i++) {
             rafb=new RandomAccessFile("raw100_"+i, "rw");
             //读入10个
             for (int j = 0; j < 10; j++) {
                 rafa[j]=new RandomAccessFile("raw10_"+(10*i+j), "rw");
                 arr[j]=rafa[j].readInt();
             }
             //剩余90个
             for (int j = 0; j < 100; j++) {
                 min=0;
                 for (int k = 0; k< 10; k++) {
                     if(arr[k]!=-1)
                         min=k;
                 } 
                 //找到最小
                 for (int k = 0; k< 10; k++) {
                     System.out.print(""+" || "+arr[k] );
                     System.out.println();
                     
                     if(arr[k]<arr[min]&&arr[k]!=-1)
                         min=k;
                 } 
                 //保存
                 if(arr[min]!=-1){
                     rafb.writeInt(arr[min]);                     
                 }

                 
                 //替补读入
                 System.out.println(""+" || "+j +" || "+min+" || "+arr[min]);
                 
                 if( rafa[min].getFilePointer() < rafa[min].length()&& arr[min]!=-1)
                 {
                         arr[min]=rafa[min].readInt();                     
                 }
                 else
                 {
                         arr[min]=-1;                         
                 }
             }             
         }    
         
         
         
         rafb=new RandomAccessFile("raw1000", "rw");
         //读入10个
         for (int i = 0; i < 10; i++) {
             rafa[i]=new RandomAccessFile("raw100_"+i, "rw");
             Raw2Txt("raw100_"+i,"sort100_"+i+".txt",100);             
             arr[i]=rafa[i].readInt();
         }
         //剩余990个
         for (int i = 0; i < 1000; i++) {
             min=0;
             for (int k = 0; k< 10; k++) {
                 if(arr[k]!=-1)
                     min=k;
             } 
             //找到最小
             for (int k = 0; k< 10; k++) {
                 System.out.print(""+" || "+arr[k] );
                 System.out.println();
                 
                 if(arr[k]<arr[min]&&arr[k]!=-1)
                     min=k;
             } 
            //保存
             cnt_all++;
             System.out.println(""+" ||----------------------------------------> "+cnt_all );             
             if(arr[min]!=-1){
                 rafb.writeInt(arr[min]);                     
             }
             //替补读入
             System.out.println(""+" || "+i +" || "+min+" || "+arr[min]);
             System.out.println(""+"++++++++++++++++++++++++++++++++++++++");             
             if( rafa[min].getFilePointer() < rafa[min].length()  && arr[min]!=-1)
             {
                     arr[min]=rafa[min].readInt();                     
             }
             else
             {
                     arr[min]=-1;                         
             }
         }    
         
         Raw2Txt("raw1000","sort1000.txt",1000);
    }
     public static void sort_arr(  ){
             int tmp;
            for (int i = 0; i < 9; i++) {
                for (int j = i+1; j < 10; j++) {
                    if(arr[i] > arr[j])
                    {
                        tmp=arr[i];
                        arr[i]=arr[j];
                        arr[j]=tmp;
                    }
                }                
            }
        }     
    //从位置m，读入n个整数到arr数组    
    public static void readRandomNumberFile(String file,long m,long n) throws IOException 
    {
        RandomAccessFile raf = new RandomAccessFile(file, "rw");
        raf.seek(Integer.SIZE/8*(m));
        for (int i = 0; i < n; i++) {
            arr[i]=raf.readInt();
        }
    }
    //从位置m，将arr数组的n个整数写入文件       
    public static void writeRandomNumberFile(String file,long m,long n) throws IOException 
    {
        RandomAccessFile raf = new RandomAccessFile(file, "rw");
        raf.seek(Integer.SIZE/8*(m));
        for (int i = 0; i < n; i++) {
            raf.writeInt(arr[i]);
        }
    }
    public static void Raw2Txt(String src,String dst,long n) throws IOException {
        int tmp;
        RandomAccessFile raf = new RandomAccessFile(src, "rw");
        FileOutputStream fos = new FileOutputStream(dst);
        PrintStream ps = new PrintStream(fos);
        System.out.println(""+"file of int "+(raf.length()/4));
        PrintStream   old   =   System.out;  
        System.setOut(ps);
        for (int i = 0; i < n; i++) {
            tmp =raf.readInt();
            System.out.print(tmp + "\t");
            if ((i + 1) % 5 == 0) {
                System.out.println();
            }
        }
        System.setOut(old);
        ps.close();
        fos.close();
    }    
}

相关资料更多>

  1. J2ME模拟器获取网页数据失败解决思路
  2. 在给一个数据库访问类写单元测试时，出现了table or view does not exist异常
  3. rtf2text有关问题?先谢了
  4. JAVA该怎么调用打在jar里的exe文件
  5. 各位大牛来分析下javaweb的发展,并回答下小弟的几个小问题
  6. JAVA连接Access数据库的代码,该如何解决
  7. 关于特殊汉字"堃"的乱码有关问题
  8. java swing jtable,该怎么解决
  9. 刚开始学java,写个猜数字的游戏,功能没写完,不知道为什么第一轮猜,老出乱七八糟的东西,以后就正常了.是不是错误有关问题,如何改?知道一下.