论坛首页 → Java企业应用论坛 →

光棍年发个排序演示, ^_^

浏览 4452 次
锁定老帖子 主题：光棍年发个排序演示, ^_^
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • jorneyR
  • 等级: 一星会员
  • 性别:
  • 文章: 154
  • 积分: 110
  • 来自: 杭州
   发表时间：2011-01-01   

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


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

                    setBottomBoundIndex(i);
                    showSortedData();
                    Thread.sleep(delay);
                }

                if (end) {
                    break;
                }
                
                // 向上
                end = true;
                setBottomBoundIndex(left);
                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);
                    }

                    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[i];
                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[i];
                    sortNumbers[i] = 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[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);
            }
        }
    }
}


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[i] = 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();
    }
}

  • 大小: 41.3 KB
返回顶楼
         
  • jorneyR
  • 等级: 一星会员
  • 性别:
  • 文章: 154
  • 积分: 110
  • 来自: 杭州
   发表时间：2011-01-01  
1. SortListener 用来监听排序时数组中的数据已经交换过等，当监听事件发生时，数组中的数据在SortPainter上更新绘制出来.
2. Sort 接口定义了排序的类需要实现的方法.
3. AbstractSort 实现了 Sort 接口，定义可共用的数据域和实现通用的方法.
4. 具体的排序算法 QuickSort, Bubble 等继承AbstractSort.
5. SortPainter 绘制排序后的数组，实现了 SortListener 接口.
6. SortPainter 被加入到 SortWindow 中在窗口里显示出来.
返回顶楼
          回帖地址
0 请登录后投票
  • Firklaag
  • 等级: 初级会员
  • 性别:
  • 文章: 11
  • 积分: 30
  • 来自: 杭州
   发表时间：2011-01-02  
。。。。。模仿JDK自带的例子啊。
返回顶楼
          回帖地址
0 请登录后投票
  • 003
  • 等级: 初级会员
  • 性别:
  • 文章: 217
  • 积分: 70
  • 来自: 上海
   发表时间：2011-01-02  
这个得顶，不过建议楼主以后发帖如果加源码，最好打个包放上来
返回顶楼
          回帖地址
0 请登录后投票
  • jorneyR
  • 等级: 一星会员
  • 性别:
  • 文章: 154
  • 积分: 110
  • 来自: 杭州
   发表时间：2011-01-02  
Firklaag 写道
。。。。。模仿JDK自带的例子啊。

是的，看到那个例子，所以模仿着用另一种方式写着玩。
返回顶楼
          回帖地址
0 请登录后投票
  • beneo
  • 等级: 一星会员
  • 性别:
  • 文章: 170
  • 积分: 130
  • 来自: 希伯來
   发表时间：2011-01-02  
本本很好的样子
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics