如何只用一个大小为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(); } }