1 package com.wyb.dyi.test;
  2 
  3 import java.awt.Color;
  4 import java.awt.Graphics;
  5 import java.awt.Toolkit;
  6 import java.util.Random;
  7 
  8 import javax.swing.JFrame;
  9 import javax.swing.JPanel;
 10 
 11 public class ShowMergeSort {
 12     static int[] array = getArray(Tool.W);/* 获得长度为屏幕宽度的乱序数组 */
 13     static updateShowArrayImg m = new updateShowArrayImg(array);/* 先显示当前乱序数组 */
 14 
 15     /**
 16      * 归并排序，并将排序过程打印成图像
 17      * @param args
 18      */
 19     public static void main(String[] args) {
 20         MyJPanel show = m.show;
 21         /* 开局暂停两秒 */
 22         try {
 23             Thread.currentThread();
 24             Thread.sleep(2000);
 25         } catch (Exception e) {
 26         }
 27 
 28         /* 开始归并排序 */
 29         m.updateShowArray(array);
 30         devide(array, 0, array.length - 1);
 31         m.updateShowArray(array);
 32     }
 33 
 34     /* 构造一个长度为length的高度为length/2的数组 */
 35     public static int[] getArray(int length) {
 36         /* 生成空数组 */
 37         int[] re = new int[length];
 38         /* 给数组附上高为length/2的升序数值 */
 39         for (int i = 0; i < re.length; i++)
 40             re[i] = i / 2;
 41         /* 讲有序数组打乱 */
 42         for (int i = 0; i < 20 * re.length; i++) {
 43             int index1 = new Random().nextInt(length);
 44             int index2 = new Random().nextInt(length);
 45             int temp = re[index1];
 46             re[index1] = re[index2];
 47             re[index2] = temp;
 48         }
 49 
 50         return re;
 51     }
 52 
 53     /* 分解数据 */
 54     public static void devide(int[] array, int left, int right) {
 55 
 56         if (left < right) {
 57             /* 寻找到中间下标 */
 58             int mid = (right + left) / 2;
 59             /* 从中间下标隔断，将前后两段分别分解 */
 60             devide(array, left, mid);
 61             /* 继续分割第二段 */
 62             devide(array, mid + 1, right);
 63             /* 分割完了，调用归并 */
 64             merge(array, left, mid, mid + 1, right);
 65         }
 66     }
 67 
 68     /* 归并，包含排序 */
 69     public static void merge(int[] array, int leftStart, int leftEnd,
 70             int rightStart, int rightEnd) {
 71         /* 新建临时数组，存放该次归并后的数据 */
 72         int[] temp = new int[array.length];
 73         /* 记录归并的左组和右组开始结束下标 */
 74         int ls = leftStart, le = leftEnd, rs = rightStart, re = rightEnd;
 75         /* 记录临时数组的存放位置 */
 76         int index = ls;
 77         /* 第一次比较归并，左组合右组中较小的入temp */
 78         while (ls <= le && rs <= re) {
 79             if (array[ls] <= array[rs]) {
 80                 temp[index] = array[ls];
 81                 index++;
 82                 ls++;
 83             } else {
 84                 temp[index] = array[rs];
 85                 index++;
 86                 rs++;
 87             }
 88         }
 89         /* 第二次选择归并，将array中剩余的未加入temp的数加入到temp中 */
 90         while (ls <= le) {
 91             temp[index] = array[ls];
 92             ls++;
 93             index++;
 94         }
 95         while (rs <= re) {
 96             temp[index] = array[rs];
 97             rs++;
 98             index++;
 99         }
100         /* temp是经过调整后的array，此时一次归并完毕，返回数据进行下一次归并 */
101         while (leftStart <= rightEnd) {
102             array[leftStart] = temp[leftStart];
103             leftStart += 1;
104         }
105         /* 打印本次归并结果,输出成图像 */
106         m.updateShowArray(array);
107     }
108 
109     /* 打印数组 */
110     public static void printArray(int[] array) {
111         for (int i = 0; i < array.length; i++)
112             System.out.print(array[i] + "  ");
113         System.out.println();
114     }
115 
116 }
117 
118 /* 工具类，获取当前屏幕大小，用户初始化显示组件和new乱序数组 */
119 class Tool {
120     public static int W = (int) Toolkit.getDefaultToolkit().getScreenSize()
121             .getWidth();/* 当前屏幕宽度 */
122     public static int H = (int) Toolkit.getDefaultToolkit().getScreenSize()
123             .getHeight();/* 当前屏幕高度 */
124 }
125 
126 /* 画图面板 */
127 class MyJPanel extends JPanel {
128     private static final long serialVersionUID = 1L;
129     int[] array;/* 用于接收构造方法传过来的数组，用于绘图 */
130 
131     public MyJPanel(int[] a) {
132         array = a;
133     }
134 
135     /* 绘图函数 */
136     public void paintComponent(Graphics g) {
137         /* 画笔置白色 */
138         g.setColor(Color.WHITE);
139         /* 擦除上一次绘制的团 */
140         g.fillRect(0, 0, Tool.W, Tool.H);
141         /* 画笔置黑色 */
142         g.setColor(Color.black);
143         /* 开始绘制当前数组图像，以（0,Tool.H）为原点，向右为x轴表数组下标，向上为y轴表当前下标所对应数组存置大小 */
144         for (int i = 0; i < array.length; i++) {
145             g.drawLine(i, Tool.H - 80, i, Tool.H - array[i] - 80);
146         }
147 
148     }
149 }
150 
151 /* 显示主框架JFrame类 */
152 class updateShowArrayImg extends JFrame {
153     private static final long serialVersionUID = 1L;
154     MyJPanel show;
155 
156     /* 构造函数，初始化显示框架 */
157     public updateShowArrayImg(int[] a) {
158         show = new MyJPanel(a);
159         show.setBounds(0, 0, Tool.W, Tool.H);
160         this.setSize(Tool.W, Tool.H);
161         this.setTitle("归并排序");
162         this.setLocation(0, 0);
163         this.add(show);
164         this.setVisible(true);
165         this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
166     }
167 
168     /**
169      * 更新画布
170      * 
171      * @param a
172      */
173     public void updateShowArray(int[] a) {
174         this.remove(show);
175         show = new MyJPanel(a);
176         this.add(show);
177         this.setVisible(true);
178     }
179 }