Go语言视频零基础入门到精通

五菱

1. SortListener 用来监听排序时数组中的数据已经交换过等，当监听事件发生时，数组中的数据在SortPainter上更新绘制出来.
2. Sort 接口定义了排序的类需要实现的方法.
3. AbstractSort 实现了 Sort 接口，定义可共用的数据域和实现通用的方法.
4. 具体的排序算法 QuickSort, Bubble 等继承AbstractSort.
5. SortPainter 绘制排序后的数组，实现了 SortListener 接口.
6. SortPainter 被加入到 SortWindow 中在窗口里显示出来.






package sort;
public interface Sort {
    String getSortName();
    void sort();
    int getMaxValue();
    int getTopBoundIndex();
    int getBottomBoundIndex();
    int[] getSortingData();
    boolean isStopped();
   
    boolean isExchanged();
   
    void setExchanged(boolean exchanged);
}
                        
package sort;
public interface SortListener {
    void dataSorted();
}
                        
package sort;
//循环里sleep一次，交换元素sleep三次，赋值sleep一次
public abstract class AbstractSort implements Sort {
    protected int[] numbers; // 原始数据: 为了能重现再次排序，所以保留原始数据
    protected int[] sortNumbers; // 正在排序的数组
    protected int topBoundIndex;
    protected int bottomBoundIndex;
    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 getTopBoundIndex() {
        return topBoundIndex;
    }
    protected void setTopBoundIndex(int index) {
        this.topBoundIndex = index;
    }
    @Override
    public int getBottomBoundIndex() {
        return bottomBoundIndex;
    }
    protected void setBottomBoundIndex(int index) {
        this.bottomBoundIndex = 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;
    }
    public void addSortListener(SortListener sortListener) {
        this.sortListener = sortListener;
    }
   
    public void setDelay(int delay) {
        this.delay = delay;
        this.exchangeDelay = delay * 3;
    }
   
    protected void init(int[] numbers, int delay) {
        setDelay(delay);
        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 > this.maxValue) {
                this.maxValue = numbers;
            }
        }
    }
    // 显示排序后的数据
    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();
}
                        


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) {
                setTopBoundIndex(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);
                    }
                    setBottomBoundIndex(j);
                    showSortedData();
                    Thread.sleep(delay);
                }
            }
            stopped = true;
            showSortedData();
        } catch (Exception e) {
        }
    }
}
                        


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) {
                boolean end = true;
               
                // 向下
                setTopBoundIndex(right);
                for (int i = left; i < right - 1; ++i) {
                    if (sortNumbers > sortNumbers[i + 1]) {
                        int temp = sortNumbers;
                        sortNumbers = sortNumbers[i + 1];
                        sortNumbers[i + 1] = temp;
                        end = false;
                        setExchanged(true);
                        showSortedData();
                        Thread.sleep(exchangeDelay);
                    }
                    setBottomBoundIndex(i);
                    showSortedData();
                    Thread.sleep(delay);
                }
                if (end) {
                    break;
                }
               
                // 向上
                end = true;
                setBottomBoundIndex(left);
                for (int i = right; i > left; --i) {
                    if (sortNumbers < sortNumbers[i - 1]) {
                        int temp = sortNumbers;
                        sortNumbers = sortNumbers[i - 1];
                        sortNumbers[i - 1] = temp;
                        end = false;
                        setExchanged(true);
                        showSortedData();
                        Thread.sleep(exchangeDelay);
                    }
                    setTopBoundIndex(i);
                    showSortedData();
                    Thread.sleep(delay);
                }
                if (end) {
                    break;
                }
                ++left;
                --right;
                showSortedData();
                Thread.sleep(delay);
            }
            stopped = true;
            showSortedData();
        } catch (Exception e) {
        }
    }
}
                        


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) {
                setTopBoundIndex(i);
                int temp = sortNumbers;
                int j = i;
               
                for (; j > 0; --j) {
                    setBottomBoundIndex(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 * 2);
            }
            stopped = true;
            showSortedData();
        } catch (Exception e) {
        }
    }
}
                        


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);
        setTopBoundIndex(height);
        setBottomBoundIndex(low);
        showSortedData();
        Thread.sleep(delay);
        int temp = sortNumbers[low];
        while (low < height) {
            while (low < height && sortNumbers[height] >= temp) {
                --height;
                setExchanged(true);
                showSortedData();
                Thread.sleep(delay);
            }
            sortNumbers[low] = sortNumbers[height];
            while (low < height && sortNumbers[low] <= temp) {
                ++low;
                setExchanged(true);
                showSortedData();
                Thread.sleep(delay);
            }
            sortNumbers[height] = sortNumbers[low];
            setExchanged(true);
            showSortedData();
            Thread.sleep(delay * 2);
        }
        sortNumbers[low] = temp;
        return low;
    }
}
                        


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) {
                setTopBoundIndex(i);
                int k = i;
                // 找到最小值
                for (int j = 0; j < i; ++j) {
                    if (sortNumbers[j] > sortNumbers[k]) {
                        k = j;
                        setExchanged(true);
                        showSortedData();
                        Thread.sleep(delay);
                    }
                    setBottomBoundIndex(j);
                    showSortedData();
                    Thread.sleep(delay);
                }
                if (k != i) {
                    // 交换数据
                    int temp = sortNumbers[k];
                    sortNumbers[k] = sortNumbers;
                    sortNumbers = temp;
                    setExchanged(true);
                    showSortedData();
                    Thread.sleep(exchangeDelay);
                }
            }
            stopped = true;
            showSortedData();
        } catch (Exception e) {
        }
    }
}
                        


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);
    }
}
                        


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.AbstractSort;
import sort.Sort;
import sort.SortListener;
@SuppressWarnings("serial")
public class SortPainter extends JPanel implements SortListener {
    private List<AbstractSort> 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<AbstractSort>();
        setBackground(Color.BLACK);
    }
    public void addSort(final AbstractSort 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<AbstractSort> 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.getTopBoundIndex();
        int indexTwo = sorter.getBottomBoundIndex();
        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, 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);
            }
        }
    }
}
                        


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 javax.swing.JLabel;
import javax.swing.JSlider;
import javax.swing.UIManager;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;
import sort.AbstractSort;
import sort.BubbleSort;
import sort.DoubleBubbleSort;
import sort.InsertSort;
import sort.QuickSort;
import sort.SelectSort;
@SuppressWarnings("serial")
public class SortWindow extends JFrame {
    private SortPainter sortPainter;
    private Box buttonsBox;
    int delay = 10; // 暂停时间
    public SortWindow() {
        super("Sort live demo");
        initGui();
        initData();
    }
    private void initGui() {
        sortPainter = new SortPainter();
        getContentPane().add(sortPainter, BorderLayout.CENTER);
        final JButton sortAllButton = new JButton("全部一起排序");
        final JSlider delaySlider = new JSlider(5, 1000);
        delaySlider.setValue(delay);
        final JLabel delayLabel = new JLabel(" 延迟(" + delay + "): ");
        buttonsBox = Box.createHorizontalBox();
        buttonsBox.add(sortAllButton);
        buttonsBox.add(delayLabel);
        buttonsBox.add(delaySlider);
        
        buttonsBox.add(Box.createHorizontalGlue());
        getContentPane().add(buttonsBox, BorderLayout.SOUTH);
        sortAllButton.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(ActionEvent e) {
                for (AbstractSort s : sortPainter.getSorters()) {
                    s.sort();
                }
            }
        });
        
        delaySlider.addChangeListener(new ChangeListener() {
            @Override
            public void stateChanged(ChangeEvent e) {
                delayLabel.setText(" 延迟(" + delaySlider.getValue() + "): ");
                if (!delaySlider.getValueIsAdjusting()) {
                    for (AbstractSort s : sortPainter.getSorters()) {
                        s.setDelay(delaySlider.getValue());
                    }
                }
            }
        });
    }
    public void addSort(final AbstractSort 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 = rand.nextInt(maxValue) + 1;
                }
                // 双向冒泡排序
                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) {
        try {
            UIManager.setLookAndFeel("com.sun.java.swing.plaf.nimbus.NimbusLookAndFeel");
        } catch (Exception e) {
            e.printStackTrace();
        }
        createGuiAndShow();
    }
}