归并排序自顶向下及自底向上算法可视化

清疚 2022-05-24 03:38 174阅读 0赞

# 归并排序自顶向下 #

## 工具类 ##

import javax.swing.*;
    import java.awt.*;
    import java.awt.geom.*;
    
    import java.lang.InterruptedException;
    
    public class AlgoVisHelper { 
    
        private AlgoVisHelper(){}
    
        public static final Color Red = new Color(0xF44336);
        public static final Color Pink = new Color(0xE91E63);
        public static final Color Purple = new Color(0x9C27B0);
        public static final Color DeepPurple = new Color(0x673AB7);
        public static final Color Indigo = new Color(0x3F51B5);
        public static final Color Blue = new Color(0x2196F3);
        public static final Color LightBlue = new Color(0x03A9F4);
        public static final Color Cyan = new Color(0x00BCD4);
        public static final Color Teal = new Color(0x009688);
        public static final Color Green = new Color(0x4CAF50);
        public static final Color LightGreen = new Color(0x8BC34A);
        public static final Color Lime = new Color(0xCDDC39);
        public static final Color Yellow = new Color(0xFFEB3B);
        public static final Color Amber = new Color(0xFFC107);
        public static final Color Orange = new Color(0xFF9800);
        public static final Color DeepOrange = new Color(0xFF5722);
        public static final Color Brown = new Color(0x795548);
        public static final Color Grey = new Color(0x9E9E9E);
        public static final Color BlueGrey = new Color(0x607D8B);
        public static final Color Black = new Color(0x000000);
        public static final Color White = new Color(0xFFFFFF);
    
        public static void strokeCircle(Graphics2D g, int x, int y, int r){
    
            Ellipse2D circle = new Ellipse2D.Double(x-r, y-r, 2*r, 2*r);
            g.draw(circle);
        }
    
        public static void fillCircle(Graphics2D g, int x, int y, int r){
    
            Ellipse2D circle = new Ellipse2D.Double(x-r, y-r, 2*r, 2*r);
            g.fill(circle);
        }
    
        public static void strokeRectangle(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 fillRectangle(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 setColor(Graphics2D g, Color color){
            g.setColor(color);
        }
    
        public static void setStrokeWidth(Graphics2D g, int w){
            int strokeWidth = w;
            g.setStroke(new BasicStroke(strokeWidth, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND));
        }
    
        public static void pause(int t) {
            try {
                Thread.sleep(t);
            }
            catch (InterruptedException e) {
                System.out.println("Error sleeping");
            }
        }
    
        public static void putImage(Graphics2D g, int x, int y, String imageURL){
    
            ImageIcon icon = new ImageIcon(imageURL);
            Image image = icon.getImage();
    
            g.drawImage(image, x, y, null);
        }
    
        public static void drawText(Graphics2D g, String text, int centerx, int centery){
    
            if(text == null)
                throw new IllegalArgumentException("Text is null in drawText function!");
    
            FontMetrics metrics = g.getFontMetrics();
            int w = metrics.stringWidth(text);
            int h = metrics.getDescent();
            g.drawString(text, centerx - w/2, centery + h);
        }
    }

## 数据层 ##

public class MergeSortData {
    
        public int[] numbers;
        public int l, r;
        public int mergeIndex;
    
        public MergeSortData(int N, int randomBound){
    
            numbers = new int[N];
    
            for( int i = 0 ; i < N ; i ++)
                numbers[i] = (int)(Math.random()*randomBound) + 1;
        }
    
        public int N(){
            return numbers.length;
        }
    
        public int get(int index){
            if( index < 0 || index >= numbers.length)
                throw new IllegalArgumentException("Invalid index to access Sort Data.");
    
            return numbers[index];
        }
    
        public void swap(int i, int j) {
            if( i < 0 || i >= numbers.length || j < 0 || j >= numbers.length)
                throw new IllegalArgumentException("Invalid index to access Sort Data.");
    
            int t = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = t;
        }
    }

## 视图层 ##

import java.awt.Dimension;
    import java.awt.Graphics;
    import java.awt.Graphics2D;
    import java.awt.RenderingHints;
    
    import javax.swing.JFrame;
    import javax.swing.JPanel;
    
    public class AlgoFrame extends JFrame{ 
    
        private int canvasWidth;
        private int canvasHeight;
    
        public AlgoFrame(String title, int canvasWidth, int canvasHeight){
    
            super(title);
    
            this.canvasWidth = canvasWidth;
            this.canvasHeight = canvasHeight;
    
            AlgoCanvas canvas = new AlgoCanvas();
            setContentPane(canvas);
            pack();
    
            setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            setResizable(false);
    
            setVisible(true);
        }
    
        public AlgoFrame(String title){
    
            this(title, 1024, 768);
        }
    
        public int getCanvasWidth(){
       return canvasWidth;}
        public int getCanvasHeight(){
       return canvasHeight;}
    
        // data
        private MergeSortData data;
        public void render(MergeSortData data){
            this.data = data;
            repaint();
        }
    
        private class AlgoCanvas extends JPanel{ 
    
            public AlgoCanvas(){
                // 双缓存
                super(true);
            }
    
            @Override
            public void paintComponent(Graphics g) {
                super.paintComponent(g);
    
                Graphics2D g2d = (Graphics2D)g;
    
                // 抗锯齿
                RenderingHints hints = new RenderingHints(
                        RenderingHints.KEY_ANTIALIASING,
                        RenderingHints.VALUE_ANTIALIAS_ON);
                hints.put(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
                g2d.addRenderingHints(hints);
    
                // 具体绘制
                int w = canvasWidth/data.N();
                for(int i = 0 ; i < data.N() ; i ++ ) {
                    //当前索引是否在区间里
                    if ( i >= data.l && i <= data.r)
                        AlgoVisHelper.setColor(g2d, AlgoVisHelper.Green);
                    else
                        AlgoVisHelper.setColor(g2d, AlgoVisHelper.Grey);
                    //当前索引是否大于区间起始索引并且小于以完成排序索引
                    if( i >= data.l && i <= data.mergeIndex )
                        AlgoVisHelper.setColor(g2d, AlgoVisHelper.Red);
    
                    AlgoVisHelper.fillRectangle(g2d, i * w, canvasHeight - data.get(i), w - 1, data.get(i));
                }
            }
    
            @Override
            public Dimension getPreferredSize(){
                return new Dimension(canvasWidth, canvasHeight);
            }
        }
    }

## 控制层 ##

import java.awt.EventQueue;
    import java.util.Arrays;
    
    public class AlgoVisualizer { 
    
        private static int DELAY = 40;
    
        private MergeSortData data;
        private AlgoFrame frame;
    
        public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){
    
            // 初始化数据
            data = new MergeSortData(N, sceneHeight);
    
            // 初始化视图
            EventQueue.invokeLater(() -> {
                frame = new AlgoFrame("Merge Sort Visualization", sceneWidth, sceneHeight);
    
                new Thread(() -> {
                    run();
                }).start();
            });
        }
    
        public void run(){
            //第一次绘制视图
            setData(-1, -1, -1);
            //排序
            mergeSort(0, data.N()-1);
    
            setData(0, data.N()-1, data.N()-1);
        }
    
        private void mergeSort(int l, int r){
            //区间到底或不合法直接返回
            if( l >= r )
                return;
            //根据区间绘制视图
            setData(l, r, -1);
            //计算分割区域、分成2个区间进行计算
            int mid = (l+r)/2;
            //递归调用函数
            mergeSort(l, mid);
            mergeSort(mid+1, r);
            merge(l, mid, r);
        }
    
        private void merge(int l, int mid, int r){
    
            int[] aux = Arrays.copyOfRange(data.numbers, l, r+1);
    
            // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
            int i = l, j = mid+1;
            for( int k = l ; k <= r; k ++ ){
    
                if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                    data.numbers[k] = aux[j-l]; j ++;
                }
                else if( j > r ){   // 如果右半部分元素已经全部处理完毕
                    data.numbers[k] = aux[i-l]; i ++;
                }
                else if( aux[i-l] < aux[j-l] ){  // 左半部分所指元素 < 右半部分所指元素
                    data.numbers[k] = aux[i-l]; i ++;
                }
                else{  // 左半部分所指元素 >= 右半部分所指元素
                    data.numbers[k] = aux[j-l]; j ++;
                }
                //处理完一轮进行绘制
                setData(l, r, k);
            }
        }
    
        private void setData(int l, int r, int mergeIndex){
            data.l = l;
            data.r = r;
            data.mergeIndex = mergeIndex;
    
            frame.render(data);
            AlgoVisHelper.pause(DELAY);
        }
    
        public static void main(String[] args) {
    
            int sceneWidth = 800;
            int sceneHeight = 800;
            int N = 100;
    
            AlgoVisualizer vis = new AlgoVisualizer(sceneWidth, sceneHeight, N);
        }
    }

## 运行效果图 ##

![这里写图片描述][70]

# 归并排序自底向上 #

归并排序自底向上修改的只是控制层run方法调用的数据、通过以2的倍数循环数组依次进行排序

## 控制层（其余代码没变） ##

import java.awt.EventQueue;
    import java.util.Arrays;
    
    public class AlgoVisualizer { 
    
        private static int DELAY = 40;
    
        private MergeSortData data;
        private AlgoFrame frame;
    
        public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){
    
            // 初始化数据
            data = new MergeSortData(N, sceneHeight);
    
            // 初始化视图
            EventQueue.invokeLater(() -> {
                frame = new AlgoFrame("Merge Sort Visualization", sceneWidth, sceneHeight);
    
                new Thread(() -> {
                    run();
                }).start();
            });
        }
    
        public void run(){
    
            setData(-1, -1, -1);
            //划分区间
            for (int sz = 1; sz < data.N(); sz *= 2)
                //对每个区间循环排序
                for (int i = 0; i < data.N() - sz; i += sz+sz)
                    // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
                    merge(i, i+sz-1, Math.min(i+sz+sz-1,data.N()-1));
    
            this.setData(0, data.N()-1, data.N()-1);
        }
    
        private void merge(int l, int mid, int r){
    
            int[] aux = Arrays.copyOfRange(data.numbers, l, r+1);
    
            // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
            int i = l, j = mid+1;
            for( int k = l ; k <= r; k ++ ){
    
                if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                    data.numbers[k] = aux[j-l]; j ++;
                }
                else if( j > r ){   // 如果右半部分元素已经全部处理完毕
                    data.numbers[k] = aux[i-l]; i ++;
                }
                else if( aux[i-l] < aux[j-l] ){  // 左半部分所指元素 < 右半部分所指元素
                    data.numbers[k] = aux[i-l]; i ++;
                }
                else{  // 左半部分所指元素 >= 右半部分所指元素
                    data.numbers[k] = aux[j-l]; j ++;
                }
    
                setData(l, r, k);
            }
        }
    
        private void setData(int l, int r, int mergeIndex){
            data.l = l;
            data.r = r;
            data.mergeIndex = mergeIndex;
    
            frame.render(data);
            AlgoVisHelper.pause(DELAY);
        }
    
        public static void main(String[] args) {
    
            int sceneWidth = 800;
            int sceneHeight = 800;
            int N = 100;
    
            AlgoVisualizer vis = new AlgoVisualizer(sceneWidth, sceneHeight, N);
        }
    }

## 运行效果图 ##

![这里写图片描述][70 1]

[70]: /images/20220524/5aebadc5b81143b2a3128ce08c434521.png
[70 1]: /images/20220524/854423665d324340920d3a839f1a5491.png