Это как раз и есть источник QuickSort , тогда в памяти не хватало оперативной памяти для сортировки в памяти, поэтому они должны хранить частичные результаты на диске.
Итак, что вы можете сделать:
- Выберите опору.
- Последовательно считывайте ваш файл и сохраняйте данные ниже чем pivot в temp_file_1, а данные больше или равны pivot в temp_file_2
- Повторите процедуру в temp_file_1 и добавьте результат к result_file
- Повторите процедуру для файла temp_file_2 и добавьте результат к файлу result_file
Когда детали достаточно малы ( как 2, просто поменяйте их местами Достаточно, чтобы отсортировать их в памяти)
Таким образом, вы сможете сортировать по частям и сохранять частичные результаты во временных файлах, и вы получите окончательный файл с отсортированным результатом.
РЕДАКТИРОВАТЬ Я говорил вам, что возможна быстрая сортировка.
Кажется, вам все-таки понадобится дополнительное место для временных файлов.
Вот что я сделал.
Я создаю 40-мегабайтный файл с номерами, разделенными запятыми.
Я называю это input:
вход http://img200.imageshack.us/img200/5129/capturadepantalla201003t.png
Ввод 40mb
Во время сортировки создаются файлы tmp с сегментами «больше чем», «меньше чем», а после завершения сортировки значения отправляются в файл с именем (угадайте, что) output
обработка http://img200.imageshack.us/img200/1672/capturadepantalla201003y.png
Временные файлы создаются с частичными результатами
Наконец, все файлы tmp удаляются, и результат сохраняется в файле «output» с правильной отсортированной последовательностью чисел:
вывод http://img203.imageshack.us/img203/5950/capturadepantalla201003w.png
Наконец, файл "output" создан, обратите внимание, что он тоже составляет 40 МБ
Вот полная программа.
import java.io.*;
import java.util.*;
public class FileQuickSort {
static final int MAX_SIZE = 1024*1024*16; // 16 megabytes in this sample, the more memory your program has, less disk writing will be used.
public static void main( String [] args ) throws IOException {
fileQuickSort( new File("input"), new File("output"));
System.out.println();
}
//
static void fileQuickSort( File inputFile, File outputFile ) throws IOException {
Scanner scanner = new Scanner( new BufferedInputStream( new FileInputStream( inputFile ), MAX_SIZE));
scanner.useDelimiter(",");
if( inputFile.length() > MAX_SIZE && scanner.hasNextInt()) {
System.out.print("-");
// put them in two buckets...
File lowerFile = File.createTempFile("quicksort-","-lower.tmp",new File("."));
File greaterFile = File.createTempFile("quicksort-","-greater.tmp", new File("."));
PrintStream lower = createPrintStream(lowerFile);
PrintStream greater = createPrintStream(greaterFile);
PrintStream target = null;
int pivot = scanner.nextInt();
// Read the file and put the values greater than in a file
// and the values lower than in other
while( scanner.hasNextInt() ){
int current = scanner.nextInt();
if( current < pivot ){
target = lower;
} else {
target = greater;
}
target.printf("%d,",current);
}
// avoid dropping the pivot
greater.printf("%d,",pivot);
// close the stream before reading them again
scanner.close();
lower.close();
greater.close();
// sort each part
fileQuickSort( lowerFile , outputFile );
lowerFile.delete();
fileQuickSort( greaterFile , outputFile);
greaterFile.delete();
// And you're done.
} else {
// Else , if you have enough RAM to process it
//
System.out.print(".");
List<Integer> smallFileIntegers = new ArrayList<Integer>();
// Read it
while( scanner.hasNextInt() ){
smallFileIntegers.add( scanner.nextInt() );
}
scanner.close();
// Sort them in memory
Collections.sort( smallFileIntegers );
PrintStream out = createPrintStream( outputFile);
for( int i : smallFileIntegers ) {
out.printf("%d,",i);
}
out.close();
// And your're done
}
}
private static PrintStream createPrintStream( File file ) throws IOException {
boolean append = true;
return new PrintStream( new BufferedOutputStream( new FileOutputStream( file, append )));
}
}
Формат файлов number,number,number,number
Ваш текущий формат: n u m b e r , n u m b , b e r
Чтобы исправить это, вам просто нужно прочитать все и пропустить пропуски.
Добавьте еще один вопрос для этого.