|
如何只用一个大小为10的数组或列表来排序1000个随机整数?,但数组或列表之类的集合数据结构只可以用一个(大小为10的数组或列表).使用java语言实现.
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; //等待归并的元素 定位
createRandomNumberFile();
long t1,t2;
t1=System.currentTimeMillis();
System.out.println(""+"排序开始："+t1);
for (int i = 0; i < 100; i++) {
readRandomNumberFile("raw",i*10,10); //读10个
sort_arr(); //排序
writeRandomNumberFile("raw10_"+i,0,10); //写小文件
}
for (int i = 0; i < 10; i++) {
rafb=new RandomAccessFile("raw100_"+i, "rwd");
//读入10个
for (int j = 0; j < 10; j++) {
rafa[j]=new RandomAccessFile("raw10_"+(10*i+j), "rwd");
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++) {
if(arr[k]<arr[min]&&arr[k]!=-1)
min=k;
}
//保存
rafb.writeInt(arr[min]);
//替补读入
if(arr[min]!=-1)
{
if( rafa[min].getFilePointer() < rafa[min].length())
{
arr[min]=rafa[min].readInt();
}
else
{
arr[min]=-1;
}
}
}
for (int j = 0; j < 10; j++) {
rafa[j].close();
rafa[j]=null;
}
rafb.close();
rafb=null;
}
rafb=new RandomAccessFile("raw1000", "rw");
//读入10个
for (int i = 0; i < 10; i++) {
rafa[i]=new RandomAccessFile("raw100_"+i, "rw");
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++) {
if(arr[k]<arr[min]&&arr[k]!=-1)
min=k;
}
//保存
rafb.writeInt(arr[min]);
//替补读入
if(arr[min]!=-1)
{
if( rafa[min].getFilePointer() < rafa[min].length())
{
arr[min]=rafa[min].readInt();
}
else
{
arr[min]=-1;
}
}
}
for (int j = 0; j < 10; j++) {
rafa[j].close();
rafa[j]=null;
}
rafb.close();
rafb=null;
t2 = System.currentTimeMillis();
System.out.println(""+"排序结束："+t2);
System.out.println(""+"用时 (" + (t2-t1) + " ms)");
Raw2Txt("raw1000","sort1000.txt",1000);
System.gc();
for (int i = 0; i < 10; i++) {
File n=new File("raw100_"+i);
forceDeleteFile(n);
}
for (int i = 0; i < 100; i++) {
File n=new File("raw10_"+i);
forceDeleteFile(n);
}
}
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, "rwd");
raf.seek(Integer.SIZE/8*(m));
for (int i = 0; i < n; i++) {
arr[i]=raf.readInt();
}
raf.close();
raf=null;
}
//从位置m，将arr数组的n个整数写入文件
public static void writeRandomNumberFile(String file,long m,long n) throws IOException
{
RandomAccessFile raf = new RandomAccessFile(file, "rwd");
raf.seek(Integer.SIZE/8*(m));
for (int i = 0; i < n; i++) {
raf.writeInt(arr[i]);
}
raf.close();
raf=null;
}
public static void Raw2Txt(String src,String dst,long n) throws IOException {
int tmp;
RandomAccessFile raf = new RandomAccessFile(src, "rwd");
FileOutputStream fos = new FileOutputStream(dst);
PrintStream ps = new PrintStream(fos);
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();
}
}
raf.close();
raf=null;
System.setOut(old);
ps.close();
fos.close();
}
static boolean forceDeleteFile(File file)
{
boolean result=false;
int delCount=0;
while(!result && delCount++ <9)
{
System.gc();
result = file.delete();
}
return result;
}
}
|