sortframe.java

用 插入排序 堆排序 归并排序 快速排序 对1000000个0到2000000的整数进行排序 对文件进行划分后排序

package sort;
import java.awt.*;
import java.awt.BorderLayout;
import java.awt.event.*;
import java.io.*;
import javax.swing.*;
import javax.swing.JProgressBar;

public class SortFrame extends JFrame {
	private JComboBox fileNumber;// 数据分组个数选择栏，选择数据分组个数

	private JComboBox Sort;// 排序选择栏，选择进行排序的方法

	private JTextField fileaddress;// 用于输入待排序文件的地址

	private JTextArea printResult;// 显示结果的文本域
	final JProgressBar progressBar = new JProgressBar();

	// 窗口的构造方法
	public SortFrame() {
		super();
		setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);

		final JScrollPane scrollPane = new JScrollPane();
		getContentPane().add(scrollPane, BorderLayout.CENTER);

		printResult = new JTextArea();
		printResult.setText("");
		printResult.setEditable(false);
		scrollPane.setViewportView(printResult);

		final JPanel panel = new JPanel();
		panel.setLayout(new BorderLayout(5, 5));
		getContentPane().add(panel, BorderLayout.NORTH);

		final JPanel panel_1 = new JPanel();
		panel_1.setLayout(new GridLayout(2, 0, 5, 5));
		panel.add(panel_1);

		final JLabel label = new JLabel();
		label.setText("在此输入需排序的文件所在的位置(包括文件名)");
		panel_1.add(label);

		fileaddress = new JTextField();
		fileaddress.setText("data_src.txt");
		panel_1.add(fileaddress);

		final JPanel panel_2 = new JPanel();
		panel_2.setLayout(new GridLayout(0, 2, 5, 5));
		panel.add(panel_2, BorderLayout.EAST);

		final String sortItem[] = { "请选择排序类型", "插入排序", "堆排序", "归并排序", "快速排序" };
		Sort = new JComboBox(sortItem);
		panel_2.add(Sort);

		final String numberOfFile[] = { "选择数据分组个数", "400", "200", "100", "50",
				"25" };
		fileNumber = new JComboBox(numberOfFile);
		panel_2.add(fileNumber);

		final JButton sort = new JButton();
		panel_2.add(sort);

		// 向排序按钮添加监听器，点击之后，对fileaddress中显示的文件进行排序
		sort.addActionListener(new ActionListener() {
			public void actionPerformed(final ActionEvent e) {

				// 新建排序线程SortThread，以防用户界面线程阻塞
				Thread SortThread = new Thread() {
					int number = Integer.parseInt(numberOfFile[fileNumber
							.getSelectedIndex()]);// 得到数据分组个数

					int whichSort = Sort.getSelectedIndex();// 得到排序方法的下标

					File files[] = new File[number];// 创建分组文件类数组

					final int ManyNumber = 1000000;// 设置整数的总数

					// run()方法，当调用此线程的start()方法时执行此方法
					public void run() {
						try {
							// 使点击后的排序按钮不可用，以防多次点击造成错误
							sort.setEnabled(false);
							sort.setText("LOADING....");

							long spendTime = System.currentTimeMillis();// 用于记录总时间
							String sortFile = fileaddress.getText();// 获取源文件的地址
							File toSort = new File(sortFile);
							IntegerReader inputSortFile = new IntegerReader(
									new BufferedReader(new FileReader(toSort)));// 创建整数读取对象
							String path = toSort.getParent() + "\\";// 获取源文件的父目录

							// 初始化创建分组文件数组，文件名为data_src_i.txt，i从0到number-1，目录与源文件的目录相同
							for (int i = 0; i < number; i++)
								files[i] = new File(path + "data_src_" + i
										+ ".txt");

							// 判断是否选择了排序方法和数据分组个数，否则抛出NumberFormatException
							if (fileNumber.getSelectedIndex() == 0
									|| Sort.getSelectedIndex() == 0)
								throw new NumberFormatException();

							long Sorttime = 0;// 用于记录排序的总时间
							double pro=0;
							// 分块读取整数到IntList a，再对a调用排序方法，排好序后写入到BufferedWriter
							// partSortFile中
							for (int i = 0; i < number; i++) {
								BufferedWriter partSortFile = new BufferedWriter(
										new FileWriter(files[i]));
								IntList a = new IntList();
								for (int j = 0; j < ManyNumber / number; j++) {
									a.appond(inputSortFile.readerInt());
								}
								switch (whichSort) {
								case 1:
									Sorttime += insertSort(a, partSortFile);
									break;
								case 2:
									Sorttime += heapSort(a, partSortFile);
									break;
								case 3:
									Sorttime += mergeSort(a, partSortFile);
									break;
								case 4:
									Sorttime += quickSort(a, partSortFile);
									break;
								}
								pro+=99/number;
								progressBar.setValue((int)pro);
								panel.add(progressBar, BorderLayout.SOUTH);
							}
							inputSortFile.close();

							/*
							 * 每次分别从每个分组文件中读取一个整数到数组num中，将最小的放写道 BufferedWriter
							 * outputSortFile中，
							 * 并将拥有此次写入的最小整数的文件的下一个整数放到num的同一位置上 再重复直到所有整数都已读入
							 */
							IntegerReader filesreader[] = new IntegerReader[number];// 分组文件整数读取的数组
							int num[] = new int[number];// 用于保存每个分组文件的一个整数的数组

							// 将每个文件的第一个整数读取到num中
							for (int i = 0; i < number; i++) {
								filesreader[i] = new IntegerReader(
										new BufferedReader(new FileReader(
												files[i])));
								num[i] = filesreader[i].readerInt();
							}

							BufferedWriter outputSortFile = new BufferedWriter(
									new FileWriter(path + "data_dst.txt"));// 目标文件的写入器

							// 进行比较并写入
							for (int i = 0; i < ManyNumber; i++) {
								int minindex = Min(num);// 求出num中最小数的下标
								outputSortFile.write(num[minindex] + " ");
								num[minindex] = filesreader[minindex]
										.readerInt();

								// 如果num[minindex]==-1为true，则表示filesreader[minindex]中的所有整数都已读取了，则关闭输入流，否则无法删除文件
								if (num[minindex] == -1)
									filesreader[minindex].close();
							}
							outputSortFile.close();

							// 删除分组文件
							for (int i = 0; i < number; i++)
								files[i].delete();

							// 将按钮复原
							sort.setText("排序");
							sort.setEnabled(true);

							spendTime = System.currentTimeMillis() - spendTime;// 计算时间差

							// 显示结果
							String output = "排序成功啦！！\n" + "排序方法名称" + "\t数据分组个数"
									+ "\t总用时(毫秒)" + "\t排序用时(毫秒)" + "\n"
									+ sortItem[whichSort] + "\t" + number
									+ "\t" + spendTime + "\t" + Sorttime
									+ "\n\n";
							printResult.append(output);
						}

						catch (NumberFormatException ex) {
							JOptionPane.showMessageDialog(null, "请选择方法和数据分组数",
									"错误", JOptionPane.ERROR_MESSAGE);
						} catch (FileNotFoundException ex) {
							JOptionPane.showMessageDialog(null, "初始文件不存在",
									"错误", JOptionPane.ERROR_MESSAGE);
						} catch (IOException ex) {
							JOptionPane.showMessageDialog(null, "文件输出错误", "错误",
									JOptionPane.ERROR_MESSAGE);
						} catch (Exception ex) {
							JOptionPane.showMessageDialog(null, "排序错误"
									+ ex.getMessage(), "错误",
									JOptionPane.ERROR_MESSAGE);
						}

						// 不管怎样，反正就是要把多余文件删了
						finally {
							for (int i = 0; i < number; i++)
								files[i].delete();
						}
					}
				};
				// 调用start()执行run()方法
				SortThread.start();
			}
		});
		sort.setText("排序");

		final JButton reset = new JButton();
		panel_2.add(reset);

		// 向清空按钮添加监听器，点击之后，将printResult中的文本清空
		reset.addActionListener(new ActionListener() {
			public void actionPerformed(final ActionEvent e) {
				printResult.setText("");
			}
		});
		reset.setText("清空");

		
		progressBar.setStringPainted(true);
		progressBar.setInheritsPopupMenu(true);
		progressBar.setIndeterminate(false);
		panel.add(progressBar, BorderLayout.SOUTH);
	}

	// 插入排序方法，将IntList a中的数升序排序，排好之后写入到BufferedWriter partSortFile中，并返回单次排序的时间
	public long insertSort(IntList a, BufferedWriter partSortFile)
			throws Exception {
		int i, j, temp;
		int n;
		long time = System.currentTimeMillis();// 用于记录排序的时间
		n = a.size();
		for (i = 0; i < n - 1; i++) {
			temp = a.getData(i + 1);
			j = i;
			while (j > -1 && temp <= a.getData(j)) {
				a.setData(j + 1, a.getData(j));
				j--;
			}
			a.setData(j + 1, temp);
		}
		time = System.currentTimeMillis() - time;
		// 将a写入partSortFile中
		for (int k = 0; k < a.size(); k++)
			partSortFile.write(a.getData(k) + " ");
		partSortFile.close();
		return time;
	}

	// 堆排序方法，将IntList a中的数升序排序，排好之后写入到BufferedWriter partSortFile中，并返回单次排序的时间
	public long heapSort(IntList a, BufferedWriter partSortFile)
			throws Exception {
		int temp;
		int n = a.size();
		long time = System.currentTimeMillis();
		// 创建最大堆
		for (int i = (n - 1) / 2; i >= 0; i--)
			createHeap(a, n, i);

		for (int i = n - 1; i > 0; i--) {
			temp = a.getData(0);
			a.setData(0, a.getData(i));
			a.setData(i, temp);
			createHeap(a, i, 0);
		}
		time = System.currentTimeMillis() - time;
		for (int k = 0; k < a.size(); k++)
			partSortFile.write(a.getData(k) + " ");
		partSortFile.close();
		return time;
	}

	// 创建堆的方法
	public void createHeap(IntList a, int n, int h) throws Exception {
		int i, j, flag;
		int temp;
		i = h;
		j = 2 * i + 1;
		temp = a.getData(i);
		flag = 0;
		while (j < n && flag != 1) {
			if (j < n - 1 && a.getData(j) < a.getData(j + 1))
				j++;
			if (temp > a.getData(j))
				flag = 1;
			else {
				a.setData(i, a.getData(j));
				i = j;
				j = 2 * i + 1;
			}
		}
		a.setData(i, temp);
	}

	// 快速排序
	public long quickSort(IntList a, BufferedWriter partSortFile)
			throws Exception {
		long time = System.currentTimeMillis();
		quick(a, 0, a.size() - 1);
		time = System.currentTimeMillis() - time;
		for (int k = 0; k < a.size(); k++)
			partSortFile.write(a.getData(k) + " ");
		partSortFile.close();
		return time;
	}

	public void quick(IntList a, int low, int high) throws Exception {
		int i, j;
		int temp;
		i = low;
		j = high;
		temp = a.getData(low);

		while (i < j) {
			while (i < j && temp <= a.getData(j))
				j--;
			if (i < j) {
				a.setData(i, a.getData(j));
				i++;
			}

			while (i < j && a.getData(i) < temp)
				i++;
			if (i < j) {
				a.setData(j, a.getData(i));
				j--;
			}
		}
		a.setData(i, temp);

		if (low < i)
			quick(a, low, i - 1);
		if (i < high)
			quick(a, i + 1, high);
	}

	// 归并排序
	public long mergeSort(IntList a, BufferedWriter partSortFile)
			throws Exception {
		int i;
		int n = a.size();
		int k = 1;
		int[] swap = new int[n];
		long time = System.currentTimeMillis();
		while (k < n) {
			merge(a, swap, k);
			for (i = 0; i < n; i++)
				a.setData(i, swap[i]);
			k = 2 * k;
		}
		time = System.currentTimeMillis() - time;
		for (int l = 0; l < a.size(); l++)
			partSortFile.write(a.getData(l) + " ");
		partSortFile.close();
		return time;
	}

	public static void merge(IntList a, int[] swap, int k) throws Exception {
		int temp1, temp2, x = 0, i;
		// 每次循环将相邻的两个分块和到一起
		for (i = 2 * k; i < swap.length && x < swap.length; i += 2 * k) {
			int j, l;
			for (j = i - k, l = i - 2 * k; j < i && l < i - k;) {
				temp1 = a.getData(l);
				temp2 = a.getData(j);
				if (temp1 <= temp2) {
					swap[x++] = temp1;
					l++;
				} else {
					swap[x++] = temp2;
					j++;
				}
			}
			// 将剩下的数全部放入swap中
			while (j < i)
				swap[x++] = a.getData(j++);
			while (l < i - k)
				swap[x++] = a.getData(l++);
		}
		// 当剩下的数不足一个分块的时候全部加入到swap中
		if (swap.length - x <= k && swap.length != x)
			for (; x < swap.length; x++)
				swap[x] = a.getData(x);
		// 当剩下的数多于一个分块 但少于两个分块时,将他们看作是两个长度不同的分块合并
		else if (swap.length - x > k && swap.length != x) {
			int m = x + k;
			int j, l;
			for (j = m, l = x; j < swap.length && l < m;) {
				temp1 = a.getData(l);
				temp2 = a.getData(j);
				if (temp1 <= temp2) {
					swap[x++] = temp1;
					l++;
				} else {
					swap[x++] = temp2;
					j++;
				}
			}
			while (j < swap.length)
				swap[x++] = a.getData(j++);
			while (l < m)
				swap[x++] = a.getData(l++);
		}
	}

	// 求数组中除-1外的最小整数的下标
	public int Min(int[] a) {
		int index = 0;
		for (int i = 0; i < a.length; i++)
			if ((a[index] == -1 || a[index] > a[i]) && a[i] != -1)
				index = i;
		return index;
	}
}

// 整数读取类，在一个BufferedReader中读取两个空格之间的字符组成字符串输出，因为这是我们data_src.txt文件中整数保存的格式
class IntegerReader {
	BufferedReader reader;

	IntegerReader(BufferedReader read) {
		reader = read;
	}

	// 返回下一个整数，当没有整数时就返回-1
	int readerInt() throws IOException {
		String number = "";
		int temp = reader.read();
		while ((char) temp != ' ' && temp != -1) {
			number += (char) temp;
			temp = reader.read();
		}
		if (temp == -1)
			return -1;
		else
			return Integer.parseInt(number);
	}

	// 关闭流
	void close() throws IOException {
		reader.close();
	}
}

// 顺序表类，用来储存整数
class IntList {
	private int size = 0;

	private int[] shu;

	public IntList() {
		shu = new int[10];
		size = 0;
	}

	public void appond(int intobj) {
		// 如果数组空间不够就将其长度扩大一倍
		if (size + 1 > shu.length) {
			int[] sh = shu;
			shu = new int[sh.length * 2];
			for (int j = 0; j < size; j++)
				shu[j] = sh[j];
			shu[size] = intobj;
			size++;
		} else {
			shu[size] = intobj;
			size++;
		}
	}

	public int getData(int i) throws Exception {
		if (i < 0 || i >= size)
			throw new Exception();
		return shu[i];
	}

	public void setData(int i, int intobj) {
		shu[i] = intobj;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}
}