外部排序实现的思考(准备工作)

简介 之前一直想不太清楚外部排序怎么实现这里呢,就将会从还没有认识到这件事基础上来探讨一下。

    假设我们已经得到了m个文件块,每个块这些文件的数据量早已经超过了单机的储存量了,那么我们怎么能够对这些数据进行排序呢?

    笔者思路是这样的:

    类似于归并排序的想法,如果有n个块已经排序(有序)当一个新的块来时其实也就是将这一个这个块的数数据一个一个顺序的插入到已经排序的n个块中。思路是比较简单的,直接没有考用效率,直接考虑可行性。

    对于以上的实现过程这里有点假设

    这里先假设有5个文件in1.txt-in5.txt

     * 每个文件有10个数(没有顺序的)

     * 

     * 首先对10个文件每一个进排序

     * 然后加载两个文件归并后写入到文件


下面前期的准备工作

  1. 首先能够进行文件的读写工作

  2. 能够产生随机数

  3. 手头上已经有基本的排序方法(冒泡都可以)

下面是有关于准备的java实现代码


package algorithm;


import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.FileReader;

import java.io.FileWriter;

import java.util.Arrays;


/*

 * 时间:2019 10 4

 * 作者:latefly

 * 功能实现一个外部排序

 * 

 * 这里先假设有5个文件in1.txt-in5.txt

 * 每个文件有10个数(没有顺序的)

 * 

 * 首先对10个文件每一个进排序

 * 然后加载两个文件归并后写入到文件

 * 

 */


public class ExternalSort {

// 此处的用静态变量是用于直接访问

static int maxLoadSize = 10;

static int filesNum = 5;

static int sortedBloks = 0;// 记录已经排序的个数


// 用于排序这里定义三个数用于中转数据

static int sortBuffIn1[] = new int[maxLoadSize];

static int sortBuffIn2[] = new int[maxLoadSize];

static int sortBuffOut[] = new int[maxLoadSize];


static FileInputAndOutput file = new FileInputAndOutput(maxLoadSize, filesNum);


public static void main(String[] args) {

// TODO Auto-generated method stub

int arr[] = new int[maxLoadSize];


// 产生数据

for (int index = 1; index <= filesNum; index++) {

for (int i = 0; i < maxLoadSize; i++) {

arr[i] = (int) (Math.random() * 100);

}

file.saveFile("in" + index + ".txt", arr);

//file.saveFile("inCopy" + index + ".txt", arr);

System.out.println("before:" + Arrays.toString(arr));

}


// 清除数据

for (int i = 0; i < maxLoadSize; i++) {

arr[i] = 0;

}

// System.out.println("after:" + Arrays.toString(arr));

// rectifySelectSort(arr);

// System.out.println("after:" + Arrays.toString(arr));

// file.saveFile("out1.txt", arr);


}


// 利用选择排序

public static void rectifySelectSort(int arr[]) {

int min;

int minIndex;

int counter;

boolean ischange = false;

for (int i = 0; i < arr.length - 1; i++) {

// 每次选择一个最小的然后交换顺序

counter = i;

min = arr[i];

minIndex = i;

ischange = false;

while (counter < arr.length) {

// 找到小的然后交换

if (arr[counter] < min) {

min = arr[counter];

minIndex = counter;

ischange = true;

}


counter++;

}

if (ischange) {

arr[minIndex] = arr[i];

arr[i] = min;

}

}

}

}


class FileInputAndOutput {


// 此处的用静态变量是用于直接访问

int maxLoadSize = 10;

int filesNum = 10;


static FileReader fin = null;

static FileWriter fout = null;

static BufferedReader bin = null;

static BufferedWriter bout = null;


public FileInputAndOutput(int maxSize, int num) {

this.maxLoadSize = maxSize;

this.filesNum = num;


}


public void loadFile(String fileName, int load[]) {

try {

fin = new FileReader("src/testFolder/" + fileName);

bin = new BufferedReader(fin);


String numBuff[] = bin.readLine().split(" ");

// 转换数字

for (int i = 0; i < maxLoadSize; i++) {

load[i] = Integer.parseInt(numBuff[i]);

}


} catch (Exception e) {

e.printStackTrace();

} finally {

try {

bin.close();

fin.close();

} catch (Exception e2) {

e2.printStackTrace();

}

}

}


public void saveFile(String fileName, int arr[]) {

try {

fout = new FileWriter("src/testFolder/" + fileName);

bout = new BufferedWriter(fout);

for (int i = 0; i < this.maxLoadSize; i++) {

bout.write(arr[i] + " ");

}

bout.write("\nend");

} catch (Exception e) {

e.printStackTrace();

} finally {

try {

bout.close();

fout.close();

} catch (Exception e2) {

e2.printStackTrace();

}

}

}

}


利用以上的代码可以在你的工作目录/src/testFloder(没有需要创建)中创建in1.txt-in5.txt当然你也可以修改每个文件都有10个随机数

文章评论

Top