======================================基本思路======================================
1. SortListener 用來監聽排序時數組中的數據已經交換過等，當監聽事件發生時，數組中的數據在SortPainter上更新繪制出來.
2. Sort 接口定義了排序的類需要實現的方法.
3. AbstractSort 實現了 Sort 接口，定義可共用的數據域和實現通用的方法.
4. 具體的排序算法 QuickSort, Bubble 等繼承AbstractSort.
5. SortPainter 繪制排序后的數組，實現了 SortListener 接口.
6. SortPainter 被加入到 SortWindow 中在窗口里顯示出來.
源碼: Sort.zip
======================================SortListener.ava======================================
package sort;
public interface SortListener {
void dataSorted();
}
======================================Sort.java======================================
package sort;
public interface Sort {
String getSortName();
void sort();
int getMaxValue();
int getIndexOne();
int getIndexTwo();
int[] getSortingData();
boolean isStopped();
boolean isExchanged();
void setExchanged(boolean exchanged);
void addSortListener(SortListener sortListener);
}
======================================AbstractSort.java======================================
package sort;
//循環里sleep一次，交換元素sleep三次，賦值sleep一次
public abstract class AbstractSort implements Sort {
protected int[] numbers; // 原始數據: 為了能重現再次排序，所以保留原始數據
protected int[] sortNumbers; // 正在排序的數組
protected int indexOne;
protected int indexTwo;
protected int maxValue; // 數組中最大的值
protected int delay = 500; // 時間間隔
protected int exchangeDelay = delay * 4;
protected boolean stopped = true;
protected boolean exchanged = false;
private SortListener sortListener;
@Override
public int getMaxValue() {
return maxValue;
}
@Override
public int getIndexOne() {
return indexOne;
}
protected void setIndexOne(int index) {
this.indexOne = index;
}
@Override
public int getIndexTwo() {
return indexTwo;
}
protected void setIndexTwo(int index) {
this.indexTwo = index;
}
@Override
public int[] getSortingData() {
return sortNumbers;
}
@Override
public boolean isStopped() {
return stopped;
}
@Override
public boolean isExchanged() {
return exchanged;
}
@Override
public void setExchanged(boolean exchanged) {
this.exchanged = exchanged;
}
@Override
public void addSortListener(SortListener sortListener) {
this.sortListener = sortListener;
}
protected void init(int[] numbers, int delay) {
this.delay = delay;
this.exchangeDelay = delay * 3;
this.numbers = new int[numbers.length];
this.sortNumbers = new int[numbers.length];
System.arraycopy(numbers, 0, this.numbers, 0, numbers.length);
System.arraycopy(numbers, 0, this.sortNumbers, 0, numbers.length);
this.maxValue = numbers[0];
for (int i = 0; i < numbers.length; ++i) {
if (numbers[i] > this.maxValue) {
this.maxValue = numbers[i];
}
}
}
// 顯示排序后的數據
protected void showSortedData() {
if (sortListener != null) {
sortListener.dataSorted();
}
}
protected void reset() {
// 從新初始化數組
System.arraycopy(numbers, 0, sortNumbers, 0, numbers.length);
stopped = false;
}
@Override
abstract public void sort();
}
======================================BubbleSort.java======================================
package sort;
public class BubbleSort extends AbstractSort implements Runnable {
public BubbleSort(int[] numbers, int delay) {
init(numbers, delay);
}
@Override
public String getSortName() {
return "冒泡排序";
}
// 冒泡法排序
@Override
public void sort() {
if (!stopped) { return; }
reset();
new Thread(this).start();
}
@Override
public void run() {
try {
for (int i = sortNumbers.length - 1; i > 0; --i) {
setIndexOne(i);
for (int j = 0; j < i; ++j) {
if (sortNumbers[j] > sortNumbers[j + 1]) {
int temp = sortNumbers[j];
sortNumbers[j] = sortNumbers[j + 1];
sortNumbers[j + 1] = temp;
setExchanged(true);
showSortedData();
Thread.sleep(exchangeDelay);
}
setIndexTwo(j);
showSortedData();
Thread.sleep(delay);
}
}
stopped = true;
showSortedData();
} catch (Exception e) {
}
}
}
======================================DoubleBubbleSort.java======================================
package sort;
public class DoubleBubbleSort extends AbstractSort implements Runnable {
public DoubleBubbleSort(int[] numbers, int delay) {
init(numbers, delay);
}
@Override
public String getSortName() {
return "雙向冒泡排序";
}
// 冒泡法排序
@Override
public void sort() {
if (!stopped) { return; }
reset();
new Thread(this).start();
}
@Override
public void run() {
try {
int left = 0;
int right = sortNumbers.length - 1;
// 如果算法第二行的某次內循環沒有進行元素交換，則說明排序工作已經完成，可以退出外循環.
while (left < right) {
// 向下
setIndexOne(right);
for (int i = left; i < right - 1; ++i) {
if (sortNumbers[i] > sortNumbers[i + 1]) {
int temp = sortNumbers[i];
sortNumbers[i] = sortNumbers[i + 1];
sortNumbers[i + 1] = temp;
setExchanged(true);
showSortedData();
Thread.sleep(exchangeDelay);
}
setIndexTwo(i);
showSortedData();
Thread.sleep(delay);
}
// 向上
setIndexTwo(left);
boolean end = true;
for (int i = right; i > left; --i) {
if (sortNumbers[i] < sortNumbers[i - 1]) {
int temp = sortNumbers[i];
sortNumbers[i] = sortNumbers[i - 1];
sortNumbers[i - 1] = temp;
end = false;
setExchanged(true);
showSortedData();
Thread.sleep(exchangeDelay);
}
setIndexOne(i);
showSortedData();
Thread.sleep(delay);
}
if (end) {
break;
}
++left;
--right;
showSortedData();
Thread.sleep(delay);
}
stopped = true;
showSortedData();
} catch (Exception e) {
}
}
}
======================================InsertSort.java======================================
package sort;
public class InsertSort extends AbstractSort implements Runnable {
public InsertSort(int[] numbers, int delay) {
init(numbers, delay);
}
@Override
public String getSortName() {
return "插入排序";
}
/*
* @Override protected void reset() { Arrays.fill(sortNumbers, 0); stopped =
* false; }
*/
// 冒泡法排序
@Override
public void sort() {
if (!stopped) { return; }
reset();
new Thread(this).start();
}
@Override
public void run() {
try {
for (int i = 0; i < sortNumbers.length; ++i) {
setIndexOne(i);
int temp = sortNumbers[i];
int j = i;
for (; j > 0; --j) {
setIndexTwo(j);
showSortedData();
if (sortNumbers[j - 1] > temp) {
sortNumbers[j] = sortNumbers[j - 1];
setExchanged(true);
showSortedData();
Thread.sleep(delay);
} else {
break;
}
Thread.sleep(delay);
}
sortNumbers[j] = temp;
showSortedData();
Thread.sleep(delay);
}
stopped = true;
showSortedData();
} catch (Exception e) {
}
}
}
======================================QuickSort.java======================================
package sort;
public class QuickSort extends AbstractSort implements Runnable {
public QuickSort(int[] numbers, int delay) {
init(numbers, delay);
}
@Override
public String getSortName() {
return "快速排序";
}
// 快速排序
@Override
public void sort() {
if (!stopped) { return; }
reset();
new Thread(this).start();
}
@Override
public void run() {
try {
quickSort(0, sortNumbers.length - 1);
stopped = true;
showSortedData();
} catch (Exception e) {
}
}
public void quickSort(int low, int height) throws InterruptedException {
if (low < height) {
int pivotLoc = partition(low, height);
quickSort(low, pivotLoc - 1);
quickSort(pivotLoc + 1, height);
}
}
public int partition(int low, int height) throws InterruptedException {
// 設置邊界
setExchanged(true);
setIndexOne(height);
setIndexTwo(low);
showSortedData();
Thread.sleep(delay);
int temp = sortNumbers[low];
while (low < height) {
while (low < height && sortNumbers[height] >= temp) {
--height;
showSortedData();
Thread.sleep(delay);
}
sortNumbers[low] = sortNumbers[height];
while (low < height && sortNumbers[low] <= temp) {
++low;
showSortedData();
Thread.sleep(delay);
}
sortNumbers[height] = sortNumbers[low];
showSortedData();
Thread.sleep(delay * 2);
}
sortNumbers[low] = temp;
return low;
}
}
======================================SelectSort.java======================================
package sort;
public class SelectSort extends AbstractSort implements Runnable {
public SelectSort(int[] numbers, int delay) {
init(numbers, delay);
}
@Override
public String getSortName() {
return "選擇排序";
}
// 選擇法排序
@Override
public void sort() {
if (!stopped) { return; }
reset();
new Thread(this).start();
}
@Override
public void run() {
try {
for (int i = sortNumbers.length - 1; i > 0; --i) {
setIndexOne(i);
int k = i;
// 找到最小值
for (int j = 0; j < i; ++j) {
if (sortNumbers[j] > sortNumbers[k]) {
k = j;
setExchanged(true);
showSortedData();
Thread.sleep(delay);
}
setIndexTwo(j);
showSortedData();
Thread.sleep(delay);
}
if (k != i) {
// 交換數據
int temp = sortNumbers[k];
sortNumbers[k] = sortNumbers[i];
sortNumbers[i] = temp;
setExchanged(true);
showSortedData();
Thread.sleep(exchangeDelay);
}
}
stopped = true;
showSortedData();
} catch (Exception e) {
}
}
}
======================================GuiUtil.java======================================
package ui;
import java.awt.Component;
import java.awt.Dimension;
import java.awt.Toolkit;
public class GuiUtil {
public static void center(Component frame) {
Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
Dimension frameSize = frame.getSize();
int x = (screenSize.width - frameSize.width) / 2;
int y = (screenSize.height - frameSize.height) / 4;
x = x >= 0 ? x : 0;
y = y >= 0 ? y : 0;
frame.setLocation(x, y);
}
}
======================================SortPainter.java======================================
package ui;
import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Component;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
import sort.SortListener;
import sort.Sort;
@SuppressWarnings("serial")
public class SortPainter extends JPanel implements SortListener {
private List<Sort> sorts;
// 小球的顏色與下標
private Color[] ballColors = { Color.PINK, Color.CYAN, Color.MAGENTA };
private int ballColorIndex;
private int paddingX = 20; // 水平方向的邊距
private int paddingY = 20; // 垂直方向的邊距
private int lineDisY = 5; // 兩條線之間的垂直距離
private int maxLineLength = 150; // 每條線最大的長度
public SortPainter() {
sorts = new CopyOnWriteArrayList<Sort>();
setBackground(Color.BLACK);
}
public void addSort(final Sort sort) {
sorts.add(sort);
// 動態的改變窗口大小
Component com = SwingUtilities.getRoot(this);
if (com != null) {
int width = getWidth();
int height = sort.getSortingData().length * lineDisY + 2 * paddingY;
int neededWidth = sorts.size() * (maxLineLength + paddingX) + paddingX;
if (width < neededWidth) {
setMinimumSize(new Dimension(neededWidth, height));
setPreferredSize(new Dimension(neededWidth, height));
}
((JFrame) com).pack();
GuiUtil.center(com);
}
}
public List<Sort> getSorters() {
return sorts;
}
@Override
public void dataSorted() {
repaint();
}
private int unifyLineLength(int value, int maxValue) {
double rate = ((double) (value)) / maxValue;
return (int) (maxLineLength * rate);
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2d = (Graphics2D) g;
g2d.setStroke(new BasicStroke(2));
g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
int startX = paddingX;
for (Sort s : sorts) {
drawSortingData(g2d, s, startX, paddingY);
startX += maxLineLength + paddingX;
}
}
private void drawSortingData(Graphics2D g2d, Sort sorter, final int startX, final int startY) {
int[] data = sorter.getSortingData();
int indexOne = sorter.getIndexOne();
int indexTwo = sorter.getIndexTwo();
int length = 0;
int maxValue = sorter.getMaxValue();
// 繪制數組中的內容
g2d.setColor(Color.WHITE);
int y = startY;
for (int i = 0; i < data.length; ++i) {
length = unifyLineLength(data[i], sorter.getMaxValue());
g2d.drawLine(startX, y, startX + length, y);
y += lineDisY;
}
// 繪制排序時的兩條分界線
if (!sorter.isStopped()) {
g2d.setColor(Color.GREEN);
y = startY + indexTwo * lineDisY;
length = unifyLineLength(data[indexTwo], maxValue);
g2d.drawLine(startX, y, startX + length, y);
g2d.setColor(Color.RED);
y = startY + indexOne * lineDisY;
length = unifyLineLength(data[indexOne], maxValue);
g2d.drawLine(startX, y, startX + length, y);
// 當交換數據時，使用小球閃爍顯示
if (sorter.isExchanged()) {
ballColorIndex = (ballColorIndex + 1) % ballColors.length;
g2d.setColor(ballColors[ballColorIndex]);
g2d.fillOval(startX - 8, startY + indexOne * lineDisY - 4, 8, 8);
g2d.fillOval(startX - 8, startY + indexTwo * lineDisY - 4, 8, 8);
sorter.setExchanged(false);
}
}
}
}
======================================SortWindow.java======================================
package ui;
import java.awt.BorderLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;
import javax.swing.Box;
import javax.swing.JButton;
import javax.swing.JFrame;
import sort.BubbleSort;
import sort.DoubleBubbleSort;
import sort.InsertSort;
import sort.QuickSort;
import sort.SelectSort;
import sort.Sort;
@SuppressWarnings("serial")
public class SortWindow extends JFrame {
private SortPainter sortPainter;
private Box buttonsBox;
public SortWindow() {
initGui();
initData();
}
private void initGui() {
sortPainter = new SortPainter();
getContentPane().add(sortPainter, BorderLayout.CENTER);
JButton sortAllButton = new JButton("全部一起排序");
buttonsBox = Box.createHorizontalBox();
buttonsBox.add(sortAllButton);
buttonsBox.add(Box.createHorizontalGlue());
getContentPane().add(buttonsBox, BorderLayout.SOUTH);
sortAllButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
for (Sort s : sortPainter.getSorters()) {
s.sort();
}
}
});
}
public void addSort(final Sort sort) {
sortPainter.addSort(sort);
sort.addSortListener(sortPainter);
JButton sortButton = new JButton(sort.getSortName());
buttonsBox.add(sortButton);
validate();
sortButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
sort.sort();
}
});
}
private void initData() {
new Thread(new Runnable() {
@Override
public void run() {
// 要排序的數組
int maxValue = 1450;
int[] numbers = new int[50];
Random rand = new Random(System.currentTimeMillis());
for (int i = 0; i < numbers.length; ++i) {
numbers[i] = rand.nextInt(maxValue) + 1;
}
int delay = 10; // 暫停時間
// 雙向冒泡排序
DoubleBubbleSort dbs = new DoubleBubbleSort(numbers, delay);
addSort(dbs);
// 冒泡排序
BubbleSort bs = new BubbleSort(numbers, delay);
addSort(bs);
// 選擇排序
SelectSort ss = new SelectSort(numbers, delay);
addSort(ss);
// 插入排序
InsertSort is = new InsertSort(numbers, delay);
addSort(is);
// 快速排序
QuickSort qs = new QuickSort(numbers, delay);
addSort(qs);
}
}).start();
}
private static void createGuiAndShow() {
// 顯示窗口
JFrame frame = new SortWindow();
frame.setSize(300, 450);
GuiUtil.center(frame);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setVisible(true);
}
public static void main(String[] args) {
createGuiAndShow();
}
}