【算法笔记】Java Swing实现选择排序算法可视化

待我称王封你为后i 2021-09-23 05:48 377阅读 0赞

## 前言 ##

最近看刘老师视频重新学习算法，记录下学习过程。

## 选择排序算法 ##

选择排序算法是交换算法的一种。  
每一次都从待排序的数据组合里找到最小（或最大）的一个元素放到已排好序的序列中。  
**选择排序算法核心代码：**

public void selectSort(int [] arr){
            for (int i = 0; i < arr.length; i++) {
                int minIndex = i;
                int j;
                // 找出最小值的元素下标
                for (j = i + 1; j < arr.length; j++) {
                    if (arr[j] < arr[minIndex]) {
                       // 保存当前找到的最小值的元素下标
                        minIndex = j;
                    }
                }
                // 将目前找到的最小值放到有序队列中
                int tmp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = tmp;
            }
        }

## 可视化 ##

用四种颜色动态展示排序过程。（在此展示的是由小到大的排序）  
灰色：待排序元素  
红色：已有序元素  
蓝色：正在遍历的元素  
紫色：目前选出的最小元素

**数据层：SelectionSortData.java**

package Demo;
    
    public class SelectionSortData {
    
        private int[] number;
    
        public int orderedIndex = -1;   // 在[0,orderedIndex]内是有序的
        public int currentCompareIndex = -1;  // 当前正在比较的元素下标
        public int currentMinIndex = -1;  // 当前找到的最小值的元素下标
    
        public SelectionSortData(int randomBound,int N){
            if(randomBound <=0 || N<=0)
                throw new IllegalArgumentException("SceneHeight or N must larger than 0 ");
            number = new int[N];
            // 生成随机数组
            for(int i=0;i<N;i++){
                number[i] = (int)(Math.random()*randomBound) + 1;
            }
        }
    
       // 获得数组指定下标的元素
        public int getNumber(int i){
            if ( i < 0 || i >= number.length )
                throw new IllegalArgumentException("out of index ");
            return number[i];
        }
    
       // 获得数组长度
        public int getN() {
            return number.length;
        }
    
        // 元素交换
        public void swap(int i,int j){
            int temp = number[i];
            number[i] = number[j];
            number[j] = temp;
        }
    
    }

**视图层：SortFrame.java**

package Demo;
    
    import javax.swing.*;
    import java.awt.*;
    
    public class SortFrame extends JFrame {
    
        private int canvasWidth;
        private int canvasHeight;
    
        public SortFrame(String title,int canvasWidth,int canvasHeight){
            super(title);
            // 画布
            SortCanvas sortCanvas = new SortCanvas();
            setContentPane(sortCanvas);
            this.canvasWidth = canvasWidth;
            this.canvasHeight = canvasHeight;
            setSize(canvasWidth,canvasHeight);  // 设置窗口大小
            setResizable(true);  // 窗口可进行缩放
            setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            pack();  // 窗口大小自适应
            setVisible(true);  // 窗口可见
        }
    
        // 数据内容渲染
        private SelectionSortData data;
        public void render(SelectionSortData data){
            this.data = data;
            repaint();
        }
    
        private class SortCanvas extends JPanel{
            public SortCanvas(){
                super(true);   // 允许双缓存
            }
    
            @Override
            public void paintComponent(Graphics g){
                super.paintComponent(g);
    
                Graphics2D graphics2D = (Graphics2D)g;
                // 抗锯齿
                RenderingHints renderingHints = new RenderingHints(RenderingHints.KEY_ANTIALIASING,RenderingHints.VALUE_ANTIALIAS_ON);
                graphics2D.addRenderingHints(renderingHints);
    
                // 具体绘制
                int w = canvasWidth / data.getN();  // 矩形宽度
                for(int i=0;i<data.getN();i++){
                    if(i < data.orderedIndex)   // 已有序的数组元素
                        SortVisHelper.setColor(graphics2D,Color.RED); 
                    else   // 无序的数组元素
                        SortVisHelper.setColor(graphics2D,Color.GRAY);
    
                    if(i == data.currentCompareIndex)  // 正在进行比较的元素 
                        SortVisHelper.setColor(graphics2D,Color.BLUE);
                    if(i == data.currentMinIndex)  // 当前找到的最小值的元素
                        SortVisHelper.setColor(graphics2D,Color.MAGENTA);
    				// 画矩形
                    SortVisHelper.filledRectangle(graphics2D,i*w,canvasHeight-data.getNumber(i),w-1,data.getNumber(i));
                }
    
            }
    
            @Override
            public Dimension getPreferredSize(){
                return  new Dimension(canvasWidth,canvasHeight);
            }
    
        }
    }

**控制层：SortVisualizer.java**

package Demo;
    
    import java.awt.*;
    
    public class SortVisualizer {
    
        private SelectionSortData data; // 数据
        private SortFrame sortFrame; // 视图
    
        publicSortVisualizer(int sceneWidth,int sceneHeight,int N){
            // 初始化数据
            data = new SelectionSortData(sceneHeight,N);
    
            // 初始化视图
            sortFrame = new SortFrame("选择排序",sceneWidth,sceneHeight);
            EventQueue.invokeLater(()->{
                new Thread(()->{
                    run();
                }).start();
            });
        }
    
        // 动画逻辑
        private void run(){
           // 更新绘制
            setData(0,-1,-1);
            // 选择排序算法
            for(int i = 0;i < data.getN();i++){
                  int minIndex = i;
                  setData(i,-1,minIndex);
                  for(int j = i+1;j < data.getN();j++){
                      setData(i,j,minIndex);
                      if(data.getNumber(j) < data.getNumber(minIndex))
                          minIndex = j;
                          setData(i,j,minIndex);
                  }
                  data.swap(i,minIndex);
                  setData(i+1,-1,-1);
              }
              setData(data.getN(),-1,-1);
        }
    
      // 实时更新元素状态
        public void setData(int orderedIndex,int currentCompareIndex,int currentMinIndex){
            data.orderedIndex = orderedIndex;
            data.currentCompareIndex = currentCompareIndex;
            data.currentMinIndex = currentMinIndex;
    
            sortFrame.render(data);
            SortVisHelper.pause(50);
        }
    }

**画图辅助类：SortVisHelper.java**

package Demo;
    
    import javax.swing.*;
    import java.awt.*;
    import java.awt.geom.Ellipse2D;
    import java.awt.geom.Rectangle2D;
    
    public class SortVisHelper {
       // 不允许外部类实例化
        private SortVisHelper(){}
    
        // 设置颜色
        public static void setColor(Graphics2D g,Color color){
            g.setColor(color);
        }
    
        // 空心矩形
        public static void storkeRectangle(Graphics2D g,int x,int y,int w,int h){
            Rectangle2D rectangle = new Rectangle2D.Double(x,y,w,h);
            g.draw(rectangle);
        }
    
        // 实心矩形
        public static void filledRectangle(Graphics2D g,int x,int y,int w,int h){
            Rectangle2D rectangle = new Rectangle2D.Double(x,y,w,h);
            g.fill(rectangle);
        }
    
    
        // 暂停
        public static void pause(int time){
            try {
                Thread.sleep(time);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    
    }