算法可视化 顶
Java GUI可视化
运动的小球
小球实体类
@AllArgsConstructor
public class Circle {
@Getter
@Setter
private int x; //圆心横坐标
@Getter
@Setter
private int y; //圆心纵坐标
@Getter
private int r; //半径
@Getter
@Setter
private int vx; //横坐标运动速度
@Getter
@Setter
private int vy; //纵坐标运动速度
@Getter
@Setter
private boolean isFilled; //是否是一个实心圆
/**
* 小球的移动
* @param minx
* @param miny
* @param maxx
* @param maxy
*/
public void move(int minx,int miny,int maxx,int maxy) {
x += vx;
y += vy;
checkCollision(minx,miny,maxx,maxy);
}
/**
* 小球的边缘碰撞
* @param minx
* @param miny
* @param maxx
* @param maxy
*/
private void checkCollision(int minx,int miny,int maxx,int maxy) {
if (x - r < minx) {
x = r;
vx = -vx;
}
if (x + r >= maxx) {
x = maxx - r;
vx = -vx;
}
if (y - r < miny) {
y = r;
vy = -vy;
}
if (y + r >= maxy) {
y = maxy - r;
vy = -vy;
}
}
/**
* 点是否在圆中
* @param p
* @return
*/
public boolean contain(Point p) {
return (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y) <= r * r;
}
}Java窗体类
@Getter
public class AlgoFrame extends JFrame {
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);
g2d.addRenderingHints(hints);
AlgoVisHelper.setStrokeWidth(g2d,1);
AlgoVisHelper.setColor(g2d,Color.RED);
for (Circle circle : circles) {
if (!circle.isFilled()) {
AlgoVisHelper.strokeCircle(g2d,circle.getX(),circle.getY(),circle.getR());
}else {
AlgoVisHelper.fillCircle(g2d,circle.getX(),circle.getY(),circle.getR());
}
}
}
@Override
public Dimension getPreferredSize() {
return new Dimension(canvasWidth,canvasHeight);
}
}
private int canvasWidth;
private int canvasHeight;
private Circle[] circles;
public AlgoFrame(String title,int canvasWidth,int canvasHeight) {
super(title);
this.canvasWidth = canvasWidth;
this.canvasHeight = canvasHeight;
AlgoCanvas canvas = new AlgoCanvas();
canvas.setOpaque(true);
this.setContentPane(canvas);
this.pack();
this.setResizable(false);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setVisible(true);
}
public AlgoFrame(String title) {
this(title,1024,768);
}
public void render(Circle[] circles) {
this.circles = circles;
this.repaint();
}
}绘制工具类
public class AlgoVisHelper {
private AlgoVisHelper() {
}
public static void setStrokeWidth(Graphics2D g2d,int w) {
int strokeWidth = w;
g2d.setStroke(new BasicStroke(strokeWidth,BasicStroke.CAP_ROUND,BasicStroke.JOIN_ROUND));
}
public static void setColor(Graphics2D g2d,Color color) {
g2d.setColor(color);
}
public static void strokeCircle(Graphics2D g2d,int x,int y,int r) {
Ellipse2D circle = new Ellipse2D.Double(x - r,y - r,2 * r,2 * r);
g2d.draw(circle);
}
public static void fillCircle(Graphics2D g2d,int x,int y,int r) {
Ellipse2D circle = new Ellipse2D.Double(x - r,y - r,2 * r,2 * r);
g2d.fill(circle);
}
public static void pause(int t) {
try {
Thread.sleep(t);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}可视化显示器类
public class AlgoVisualizer {
private class AlgoKeyListener extends KeyAdapter {
@Override
public void keyReleased(KeyEvent e) {
if (e.getKeyChar() == ' ') {
isAnimated = !isAnimated;
}
}
}
private class AlgoMouseListener extends MouseAdapter {
@Override
public void mousePressed(MouseEvent e) {
e.translatePoint(0,-(frame.getBounds().height - frame.getCanvasHeight()));
Stream.of(circles).filter(circle -> circle.contain(e.getPoint()))
.forEach(circle -> circle.setFilled(!circle.isFilled()));
}
}
private Circle[] circles;
private AlgoFrame frame;
private boolean isAnimated = true;
public AlgoVisualizer(int sceneWidth,int sceneHeight,int N) {
circles = new Circle[N];
int R = 50;
for (int i = 0;i < N;i++) {
int x = (int) (Math.random() * (sceneWidth - 2 * R)) + R;
int y = (int) (Math.random() * (sceneHeight - 2 * R)) + R;
int vx = (int) (Math.random() * 11) - 5;
int vy = (int) (Math.random() * 11) - 5;
circles[i] = new Circle(x,y,R,vx,vy,false);
}
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
frame.addKeyListener(new AlgoKeyListener());
frame.addMouseListener(new AlgoMouseListener());
new Thread(() -> {
run();
}).start();
});
}
private void run() {
while (true) {
frame.render(circles);
AlgoVisHelper.pause(20);
if (isAnimated) {
Stream.of(circles)
.forEach(circle ->
circle.move(0, 0, frame.getCanvasWidth(),
frame.getCanvasHeight()));
}
}
}
}main方法
public class FrameMain {
public static void main(String[] args) {
int sceneWidth = 800;
int sceneHeight = 800;
int N = 10;
AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth,sceneHeight,N);
}
}显示效果
这里面有两个交互事件，一个是点击空格暂停，一个是鼠标点到圆的内部的时候变换颜色。
- 绘制模版
根据以上的圆球的代码，我们将其抽象成一个以后用于填充各种算法的绘制模版，根据MVC的原理
显示层
@Getter
public class AlgoFrame extends JFrame {
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);
g2d.addRenderingHints(hints);
//具体绘制
// TODO: 绘制自己的数据data
}
@Override
public Dimension getPreferredSize() {
return new Dimension(canvasWidth,canvasHeight);
}
}
private int canvasWidth;
private int canvasHeight;
//设置自己的数据
private Object data;
public AlgoFrame(String title,int canvasWidth,int canvasHeight) {
super(title);
this.canvasWidth = canvasWidth;
this.canvasHeight = canvasHeight;
AlgoCanvas canvas = new AlgoCanvas();
canvas.setOpaque(true);
this.setContentPane(canvas);
this.pack();
this.setResizable(false);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setVisible(true);
}
public AlgoFrame(String title) {
this(title,1024,768);
}
public void render(Object data) {
this.data = data;
this.repaint();
}
}控制层
public class AlgoVisualizer {
// TODO: 根据情况决定是否实现键盘鼠标交互事件监听器类
private class AlgoKeyListener extends KeyAdapter {
}
private class AlgoMouseListener extends MouseAdapter {
}
//创建自己的数据
private Object data; //数据
private AlgoFrame frame; //视图
public AlgoVisualizer(int sceneWidth,int sceneHeight,int N) {
//初始化数据
// TODO: 初始化数据
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
//根据情况决定是否加入键盘鼠标监听器
frame.addKeyListener(new AlgoKeyListener());
frame.addMouseListener(new AlgoMouseListener());
new Thread(() -> {
run();
}).start();
});
}
/**
* 动画逻辑
*/
private void run() {
// TODO: 编写自己的动画逻辑
}
}显示工具类
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 Whitr = new Color(0xFFFFFF);
/**
* 设置线条宽度
* @param g2d
* @param w
*/
public static void setStrokeWidth(Graphics2D g2d,int w) {
int strokeWidth = w;
g2d.setStroke(new BasicStroke(strokeWidth,BasicStroke.CAP_ROUND,BasicStroke.JOIN_ROUND));
}
/**
* 设置颜色
* @param g2d
* @param color
*/
public static void setColor(Graphics2D g2d,Color color) {
g2d.setColor(color);
}
/**
* 绘制空心圆形
* @param g2d
* @param x
* @param y
* @param r
*/
public static void strokeCircle(Graphics2D g2d,int x,int y,int r) {
Ellipse2D circle = new Ellipse2D.Double(x - r,y - r,2 * r,2 * r);
g2d.draw(circle);
}
/**
* 绘制实心圆形
* @param g2d
* @param x
* @param y
* @param r
*/
public static void fillCircle(Graphics2D g2d,int x,int y,int r) {
Ellipse2D circle = new Ellipse2D.Double(x - r,y - r,2 * r,2 * r);
g2d.fill(circle);
}
/**
* 绘制空心矩形
* @param g2d
* @param x
* @param y
* @param w
* @param h
*/
public static void strokeRectangle(Graphics2D g2d,int x,int y,int w,int h) {
Rectangle2D rectangle = new Rectangle2D.Double(x,y,w,h);
g2d.draw(rectangle);
}
/**
* 绘制实心矩形
* @param g2d
* @param x
* @param y
* @param w
* @param h
*/
public static void fillRectangel(Graphics2D g2d,int x,int y,int w,int h) {
Rectangle2D rectangle = new Rectangle2D.Double(x,y,w,h);
g2d.fill(rectangle);
}
public static void pause(int t) {
try {
Thread.sleep(t);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
/**
* 导入图片
* @param g2d
* @param x
* @param y
* @param imageURL
*/
public static void putImage(Graphics2D g2d,int x,int y,String imageURL) {
ImageIcon icon = new ImageIcon(imageURL);
Image image = icon.getImage();
g2d.drawImage(image,x,y,null);
}
/**
* 绘制文字
* @param g2d
* @param text
* @param centerx
* @param centery
*/
public static void drawText(Graphics2D g2d,String text,int centerx,int centery) {
if (text == null) {
throw new IllegalArgumentException("文字为空");
}
FontMetrics metrics = g2d.getFontMetrics();
int w = metrics.stringWidth(text);
int h = metrics.getDescent();
g2d.drawString(text,centerx - w / 2,centery + h);
}
}- 一个有意思的分钱问题
房间里有100个人，每个人都有100元钱，他们在玩一个游戏。每轮游戏中，每个人都要拿出1元钱随机给另一个人，最后这100个人的财富分布是怎样的？
通过之前的模版进行修改。
显示层
@Getter
public class AlgoFrame extends JFrame {
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);
g2d.addRenderingHints(hints);
//具体绘制
// TODO: 绘制自己的数据data
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Blue);
int w = canvasWidth / money.length;
for (int i = 0;i < money.length;i++) {
AlgoVisHelper.fillRectangel(g2d,i * w + 1,canvasHeight - money[i],
w - 1,money[i]);
}
}
@Override
public Dimension getPreferredSize() {
return new Dimension(canvasWidth,canvasHeight);
}
}
private int canvasWidth;
private int canvasHeight;
//设置自己的数据
private int[] money;
public AlgoFrame(String title,int canvasWidth,int canvasHeight) {
super(title);
this.canvasWidth = canvasWidth;
this.canvasHeight = canvasHeight;
AlgoCanvas canvas = new AlgoCanvas();
canvas.setOpaque(true);
this.setContentPane(canvas);
this.pack();
this.setResizable(false);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setVisible(true);
}
public AlgoFrame(String title) {
this(title,1024,768);
}
public void render(int[] money) {
this.money = money;
this.repaint();
}
}控制层
public class AlgoVisualizer {
//创建自己的数据
private int[] money; //数据
private AlgoFrame frame; //视图
private static int DELAY = 10;
public AlgoVisualizer(int sceneWidth,int sceneHeight) {
//初始化数据
// TODO: 初始化数据
money = new int[100];
for (int i = 0;i < money.length;i++) {
money[i] = 100;
}
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
new Thread(() -> {
run();
}).start();
});
}
/**
* 动画逻辑
*/
private void run() {
// TODO: 编写自己的动画逻辑
while (true) {
frame.render(money);
AlgoVisHelper.pause(DELAY);
for (int i = 0;i < money.length;i++) {
if (money[i] > 0) {
int j = (int) (Math.random() * money.length);
money[i] -= 1;
money[j] += 1;
}
}
}
}
}main方法
public class MoneyMain {
public static void main(String[] args) {
int sceneWidth = 1000;
int sceneHeight = 800;
AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth,sceneHeight);
}
}图像显示
加快该进程，并进行排序
public class AlgoVisualizer {
//创建自己的数据
private int[] money; //数据
private AlgoFrame frame; //视图
private static int DELAY = 10;
public AlgoVisualizer(int sceneWidth,int sceneHeight) {
//初始化数据
// TODO: 初始化数据
money = new int[100];
for (int i = 0;i < money.length;i++) {
money[i] = 100;
}
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
new Thread(() -> {
run();
}).start();
});
}
/**
* 动画逻辑
*/
private void run() {
// TODO: 编写自己的动画逻辑
while (true) {
Arrays.sort(money);
frame.render(money);
AlgoVisHelper.pause(DELAY);
for (int k = 0;k < 50;k++) {
for (int i = 0; i < money.length; i++) {
if (money[i] > 0) {
int j = (int) (Math.random() * money.length);
money[i] -= 1;
money[j] += 1;
}
}
}
}
}
}图像显示
这样我们就可以看到，经过一段时间后，整个屋子的人的财富分配情况。
现在我们把它调整为允许为负值
@Getter
public class AlgoFrame extends JFrame {
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);
g2d.addRenderingHints(hints);
//具体绘制
// TODO: 绘制自己的数据data
int w = canvasWidth / money.length;
for (int i = 0;i < money.length;i++) {
if (money[i] > 0) {
AlgoVisHelper.setColor(g2d, AlgoVisHelper.Blue);
AlgoVisHelper.fillRectangel(g2d, i * w + 1, canvasHeight / 2 - money[i],
w - 1, money[i]);
}else if (money[i] < 0) {
AlgoVisHelper.setColor(g2d, AlgoVisHelper.Red);
AlgoVisHelper.fillRectangel(g2d, i * w + 1, canvasHeight / 2,
w - 1, -money[i]);
}
}
}
@Override
public Dimension getPreferredSize() {
return new Dimension(canvasWidth,canvasHeight);
}
}
private int canvasWidth;
private int canvasHeight;
//设置自己的数据public class AlgoVisualizer {
//创建自己的数据
private int[] money; //数据
private AlgoFrame frame; //视图
private static int DELAY = 10;
public AlgoVisualizer(int sceneWidth,int sceneHeight) {
//初始化数据
// TODO: 初始化数据
money = new int[100];
for (int i = 0;i < money.length;i++) {
money[i] = 100;
}
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
new Thread(() -> {
run();
}).start();
});
}
/**
* 动画逻辑
*/
private void run() {
// TODO: 编写自己的动画逻辑
while (true) {
Arrays.sort(money);
frame.render(money);
AlgoVisHelper.pause(DELAY);
for (int k = 0;k < 50;k++) {
for (int i = 0; i < money.length; i++) {
// if (money[i] > 0) {
int j = (int) (Math.random() * money.length);
money[i] -= 1;
money[j] += 1;
// }
}
}
}
}
}图像显示
- 蒙特卡洛方法
蒙特卡洛方法是一种统计学的方法；是一种模拟。
蒙特卡洛模拟是二战期间，为解决原子弹研制工作中，裂变物质的中子随机扩散问题，美国数学家冯诺伊曼和乌拉姆等提出的一种统计方法，代号：蒙特卡洛。
通过大量的随机样本，去了解一个系统，进而得到所要计算的值。
求PI的值
这里我们依然修改之前的模版
圆的实体类
@AllArgsConstructor
public class Circle {
@Getter
private int x; //圆心横坐标
@Getter
private int y; //圆心纵坐标
@Getter
private int r; //半径
/**
* 点是否在圆中
* @param p
* @return
*/
public boolean contain(Point p) {
return Math.pow(p.getX() - x,2) + Math.pow(p.getY() - y,2) <= r * r;
}
}视图层
@Getter
public class AlgoFrame extends JFrame {
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);
g2d.addRenderingHints(hints);
//具体绘制
// TODO: 绘制自己的数据data
AlgoVisHelper.setStrokeWidth(g2d,3);
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Blue);
AlgoVisHelper.strokeCircle(g2d,circle.getX(),circle.getY(),circle.getR());
for (int i = 0;i < points.size();i++) {
Point p = points.get(i);
if (circle.contain(p)) {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Red);
}else {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Green);
}
AlgoVisHelper.fillCircle(g2d,p.x,p.y,3);
}
}
@Override
public Dimension getPreferredSize() {
return new Dimension(canvasWidth,canvasHeight);
}
}
private int canvasWidth;
private int canvasHeight;
//设置自己的数据
private Circle circle;
private List<Point> points;
public AlgoFrame(String title,int canvasWidth,int canvasHeight) {
super(title);
this.canvasWidth = canvasWidth;
this.canvasHeight = canvasHeight;
AlgoCanvas canvas = new AlgoCanvas();
canvas.setOpaque(true);
this.setContentPane(canvas);
this.pack();
this.setResizable(false);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setVisible(true);
}
public AlgoFrame(String title) {
this(title,1024,768);
}
public void render(Circle circle,List<Point> points) {
this.circle = circle;
this.points = points;
this.repaint();
}
}控制层
public class AlgoVisualizer {
private static int DELAY = 10;
//创建自己的数据
private Circle circle; //数据
private List<Point> points;
private int insideCircle = 0;
private AlgoFrame frame; //视图
private int N;
public AlgoVisualizer(int sceneWidth,int sceneHeight,int N) {
if (sceneWidth != sceneHeight) {
throw new IllegalArgumentException("必须创建为一个正方形窗口");
}
//初始化数据
// TODO: 初始化数据
this.N = N;
circle = new Circle(sceneWidth / 2,sceneHeight / 2,sceneWidth / 2);
points = new LinkedList<>();
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
new Thread(() -> {
run();
}).start();
});
}
/**
* 动画逻辑
*/
private void run() {
// TODO: 编写自己的动画逻辑
for (int i = 0;i < N;i++) {
frame.render(circle,points);
AlgoVisHelper.pause(DELAY);
int circleArea = insideCircle;
int squareArea = points.size();
double piEstimation = 4 * (double) circleArea / squareArea;
System.out.println(piEstimation);
int x = (int) (Math.random() * frame.getCanvasWidth());
int y = (int) (Math.random() * frame.getCanvasHeight());
Point p = new Point(x,y);
points.add(p);
if (circle.contain(p)) {
insideCircle++;
}
}
}
}main方法
public class PIMain {
public static void main(String[] args) {
int sceneWidth = 800;
int sceneHeight = 800;
int N = 10000;
AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth,sceneHeight,N);
}
}显示图
圆周率打印结果
...............
3.1404947656197906 3.140523420570095 3.1405520736098147 3.1404473780711406 3.140342689512634 3.140238007933598
建立数据层，来分离控制层的数据运算。
public class MonteCarloPiData {
@Getter
private Circle circle;
private List<Point> points;
private int insideCircle = 0;
public MonteCarloPiData(Circle circle) {
this.circle = circle;
points = new LinkedList<>();
}
public Point getPoint(int i) {
if (i < 0 || i >= points.size()) {
throw new IllegalArgumentException("超出点列表的范围");
}
return points.get(i);
}
public int getPointsNumber() {
return points.size();
}
public void addPoint(Point p) {
points.add(p);
if (circle.contain(p)) {
insideCircle++;
}
}
public double estimatePi() {
if (points.size() == 0) {
return 0.0;
}
int circleArea = insideCircle;
int squareArea = points.size();
return (double) circleArea * 4 / squareArea;
}
}视图层
@Getter
public class AlgoFrame extends JFrame {
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);
g2d.addRenderingHints(hints);
//具体绘制
// TODO: 绘制自己的数据data
Circle circle = data.getCircle();
AlgoVisHelper.setStrokeWidth(g2d,3);
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Blue);
AlgoVisHelper.strokeCircle(g2d,circle.getX(),circle.getY(),circle.getR());
for (int i = 0;i < data.getPointsNumber();i++) {
Point p = data.getPoint(i);
if (circle.contain(p)) {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Red);
}else {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Green);
}
AlgoVisHelper.fillCircle(g2d,p.x,p.y,3);
}
}
@Override
public Dimension getPreferredSize() {
return new Dimension(canvasWidth,canvasHeight);
}
}
private int canvasWidth;
private int canvasHeight;
//设置自己的数据
private MonteCarloPiData data;
public AlgoFrame(String title,int canvasWidth,int canvasHeight) {
super(title);
this.canvasWidth = canvasWidth;
this.canvasHeight = canvasHeight;
AlgoCanvas canvas = new AlgoCanvas();
canvas.setOpaque(true);
this.setContentPane(canvas);
this.pack();
this.setResizable(false);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setVisible(true);
}
public AlgoFrame(String title) {
this(title,1024,768);
}
public void render(MonteCarloPiData data) {
this.data = data;
this.repaint();
}
}控制层
public class AlgoVisualizer {
private static int DELAY = 10;
//创建自己的数据
private MonteCarloPiData data; //数据
private AlgoFrame frame; //视图
private int N;
public AlgoVisualizer(int sceneWidth,int sceneHeight,int N) {
if (sceneWidth != sceneHeight) {
throw new IllegalArgumentException("必须创建为一个正方形窗口");
}
//初始化数据
// TODO: 初始化数据
this.N = N;
Circle circle = new Circle(sceneWidth / 2,sceneHeight / 2,sceneWidth / 2);
data = new MonteCarloPiData(circle);
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
new Thread(() -> {
run();
}).start();
});
}
/**
* 动画逻辑
*/
private void run() {
// TODO: 编写自己的动画逻辑
for (int i = 0;i < N;i++) {
if (i % 100 == 0) {
frame.render(data);
AlgoVisHelper.pause(DELAY);
System.out.println(data.estimatePi());
}
int x = (int) (Math.random() * frame.getCanvasWidth());
int y = (int) (Math.random() * frame.getCanvasHeight());
data.addPoint(new Point(x,y));
}
}
}由于可视化在屏幕上绘制占用的内存较大，我们很难用更大的数据来进行模拟，所以我们使用非可视化，控制台的输出来进行模拟
public class MonteCarloExperiment {
private int squareSide;
private int N;
private int outputInterval = 100;
public MonteCarloExperiment(int squareSide,int N) {
if (squareSide <= 0 || N <= 0) {
throw new IllegalArgumentException("squareSide,N必须大于0");
}
this.squareSide = squareSide;
this.N = N;
}
public void setOutputInterval(int outputInterval) {
if (outputInterval <= 0) {
throw new IllegalArgumentException("outputInterval必须大于0");
}
this.outputInterval = outputInterval;
}
public void run() {
Circle circle = new Circle(squareSide / 2,squareSide / 2,squareSide / 2);
MonteCarloPiData data = new MonteCarloPiData(circle);
for (int i = 0;i < N;i++) {
if (i % outputInterval == 0) {
System.out.println(data.estimatePi());
}
int x = (int) (Math.random() * squareSide);
int y = (int) (Math.random() * squareSide);
data.addPoint(new Point(x,y));
}
}
public static void main(String[] args) {
int squareSide = 800;
int N = 10000000;
MonteCarloExperiment exp = new MonteCarloExperiment(squareSide,N);
exp.setOutputInterval(10000);
exp.run();
}
}这里我们看到，我们将模拟数据调到了一千万。
运行结果
................
3.14157139979859 3.1415686116700203 3.141554974874372 3.141551004016064 3.14154704112337 3.1415038076152304 3.141508308308308
- 三门问题
三门问题(Monty Hall Problem)
出自美国的电视游戏节目Let's Make a Deal。问题的名字来自该节目的主持人蒙提.霍尔(Monty Hall)。
参赛者会看见三扇关闭了的门，其中一扇的后面有一辆汽车，选中后面有车的那扇门就可以赢得该汽车，而另外两扇门后面则什么都没有。当参赛者选定一扇门，但开启的时候，节目主持人会开启剩下两扇门的其中一扇，这扇门背后一定没有汽车。主持人会问参赛者要不要换另一扇门。问题是：换另一扇门会否会增加参赛者获奖概率？
由于该问题需要大量模拟数据，就不进行可视化操作了，我们直接使用控制台输出
public class ThreeGatesExperiment {
private int N;
public ThreeGatesExperiment(int N) {
if (N <= 0) {
throw new IllegalArgumentException("N必须大于0");
}
this.N = N;
}
public void run(boolean changeDoor) {
int wins = 0;
for (int i = 0; i < N; i++) {
if (play(changeDoor)) {
wins++;
}
}
System.out.println(changeDoor ? "换门" : "不换门");
System.out.println("中奖概率: " + (double) wins / N);
}
private boolean play(boolean changeDoor) {
int prizeDoor = (int) (Math.random() * 3);
int playerChoice = (int) (Math.random() * 3);
if (playerChoice == prizeDoor) {
return !changeDoor;
} else {
return changeDoor;
}
}
public static void main(String[] args) {
int N = 10000000;
ThreeGatesExperiment exp = new ThreeGatesExperiment(N);
exp.run(true);
exp.run(false);
}
}运行结果
换门 中奖概率: 0.6667727 不换门 中奖概率: 0.3335902
- 抽宝箱的概率
在游戏里有一种宝箱，打开这个宝箱获得传奇武器的概率是20%，现在你开5个这样的宝箱，获得传奇武器的概率是多少？
这里我们依然使用控制台来输出。
public class WinningPrize {
private double chance;
private int playTime;
private int N;
public WinningPrize(double chance,int playTime,int N) {
if (chance < 0.0 || chance > 1.0) {
throw new IllegalArgumentException("chance必须在0和1之间");
}
if (playTime <= 0 || N <= 0) {
throw new IllegalArgumentException("playTime和N必须大于0");
}
this.chance = chance;
this.playTime = playTime;
this.N = N;
}
public void run() {
int wins = 0;
for (int i = 0;i < N; i++) {
if (play()) {
wins++;
}
}
System.out.println("中奖概率为: " + (double) wins / N);
}
private boolean play() {
for (int i = 0;i < playTime;i++) {
if (Math.random() < chance) {
return true;
}
}
return false;
}
public static void main(String[] args) {
double chance = 0.2;
int playTime = 5;
int N = 1000000;
WinningPrize winningPrize = new WinningPrize(chance,playTime,N);
winningPrize.run();
}
}这段代码的意思是我们连续开100万次，每次开5个宝箱。
运行结果
中奖概率为: 0.672504
根据结果可知，我们连续开5个宝箱的概率大概在67%。当然在概率论中也有一个基本的公式
1 - (0.8)^5 = 0.67232
现在我们可以来看一下，如果我们的心理值是95%的概率能拿到传奇武器，那么我们需要开多少次呢？
1 - (0.8)^x > 0.95，根据该公式，我们可以反解x的值。
而具有迷惑的1 / 0.2 = 5的真实意义是平均值(期望值)，也就是说我们是有可能被平均的，比如别人可能开1个宝箱就拿到了传奇武器，而我们却可能要开10个，20个。
- 选择排序可视化
选择排序算法就是通过扫描数组中的最小值然后跟数组最前端的值交换来达到排序的目的的算法，它是一个O(n^2)时间复杂度的算法。以下红色表示发生变动的元素，蓝色表示固定下来的元素。
现在我们还是通过我们的模版来进行修改
数据层
public class SelectionSortData {
private int[] numbers;
public SelectionSortData(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("无效的排序数组索引");
}
return numbers[index];
}
public void swap(int i,int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}视图层
@Getter
public class AlgoFrame extends JFrame {
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);
g2d.addRenderingHints(hints);
//具体绘制
// TODO: 绘制自己的数据data
int w = canvasWidth / data.N();
AlgoVisHelper.setColor(g2d,AlgoVisHelper.LightBlue);
for (int i = 0;i < data.N();i++) {
AlgoVisHelper.fillRectangel(g2d,i * w,canvasHeight - data.get(i),
w - 1,data.get(i));
}
}
@Override
public Dimension getPreferredSize() {
return new Dimension(canvasWidth,canvasHeight);
}
}
private int canvasWidth;
private int canvasHeight;
//设置自己的数据
private SelectionSortData data;
public AlgoFrame(String title,int canvasWidth,int canvasHeight) {
super(title);
this.canvasWidth = canvasWidth;
this.canvasHeight = canvasHeight;
AlgoCanvas canvas = new AlgoCanvas();
canvas.setOpaque(true);
this.setContentPane(canvas);
this.pack();
this.setResizable(false);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setVisible(true);
}
public AlgoFrame(String title) {
this(title,1024,768);
}
public void render(SelectionSortData data) {
this.data = data;
this.repaint();
}
}控制层
public class AlgoVisualizer {
private static int DELAY = 10;
//创建自己的数据
private SelectionSortData data; //数据
private AlgoFrame frame; //视图
public AlgoVisualizer(int sceneWidth,int sceneHeight,int N) {
//初始化数据
// TODO: 初始化数据
data = new SelectionSortData(N,sceneHeight);
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
new Thread(() -> {
run();
}).start();
});
}
/**
* 动画逻辑
*/
private void run() {
frame.render(data);
AlgoVisHelper.pause(DELAY);
// TODO: 编写自己的动画逻辑
for (int i = 0;i < data.N();i++) {
//寻找[i,n)区间里的最小值索引
int minIndex = i;
for (int j = i + 1;j < data.N();j++) {
if (data.get(j) < data.get(minIndex)) {
minIndex = j;
}
}
data.swap(i,minIndex);
frame.render(data);
AlgoVisHelper.pause(DELAY);
}
frame.render(data);
AlgoVisHelper.pause(DELAY);
}
}main方法
public class SelectionSortMain {
public static void main(String[] args) {
int sceneWidth = 800;
int sceneHeight = 800;
int N = 100;
AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth,sceneHeight,N);
}
}显示的图样
由于此种方式无法展现排序的主要过程，所以我们做出修改。
数据层
public class SelectionSortData {
private int[] numbers;
@Getter
@Setter
private int orderedIndex = -1; //[0..orderedIndex)是有序的
@Getter
@Setter
private int currentMinIndex = -1; //当前找到的最小元素的索引
@Getter
@Setter
private int currentCompareIndex = -1; //当前正在比较的元素索引
public SelectionSortData(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("无效的排序数组索引");
}
return numbers[index];
}
public void swap(int i,int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}视图层
@Getter
public class AlgoFrame extends JFrame {
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);
g2d.addRenderingHints(hints);
//具体绘制
// TODO: 绘制自己的数据data
int w = canvasWidth / data.N();
for (int i = 0;i < data.N();i++) {
if (i < data.getOrderedIndex()) {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Red);
}else {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Grey);
}
if (i == data.getCurrentCompareIndex()) {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.LightBlue);
}
if (i == data.getCurrentMinIndex()) {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Indigo);
}
AlgoVisHelper.fillRectangel(g2d,i * w,canvasHeight - data.get(i),
w - 1,data.get(i));
}
}
@Override
public Dimension getPreferredSize() {
return new Dimension(canvasWidth,canvasHeight);
}
}
private int canvasWidth;
private int canvasHeight;
//设置自己的数据
private SelectionSortData data;
public AlgoFrame(String title,int canvasWidth,int canvasHeight) {
super(title);
this.canvasWidth = canvasWidth;
this.canvasHeight = canvasHeight;
AlgoCanvas canvas = new AlgoCanvas();
canvas.setOpaque(true);
this.setContentPane(canvas);
this.pack();
this.setResizable(false);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setVisible(true);
}
public AlgoFrame(String title) {
this(title,1024,768);
}
public void render(SelectionSortData data) {
this.data = data;
this.repaint();
}
}控制层
public class AlgoVisualizer {
private static int DELAY = 20;
//创建自己的数据
private SelectionSortData data; //数据
private AlgoFrame frame; //视图
public AlgoVisualizer(int sceneWidth,int sceneHeight,int N) {
//初始化数据
// TODO: 初始化数据
data = new SelectionSortData(N,sceneHeight);
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
new Thread(() -> {
run();
}).start();
});
}
/**
* 动画逻辑
*/
private void run() {
setData(0,-1,-1);
// TODO: 编写自己的动画逻辑
for (int i = 0;i < data.N();i++) {
//寻找[i,n)区间里的最小值索引
int minIndex = i;
setData(i,-1,minIndex);
for (int j = i + 1;j < data.N();j++) {
setData(i,j,minIndex);
if (data.get(j) < data.get(minIndex)) {
minIndex = j;
setData(i,j,minIndex);
}
}
data.swap(i,minIndex);
setData(i + 1,-1,-1);
}
setData(data.N(),-1,-1);
}
private void setData(int orderedIndex,int currentCompareIndex,int currentMinIndex) {
data.setOrderedIndex(orderedIndex);
data.setCurrentCompareIndex(currentCompareIndex);
data.setCurrentMinIndex(currentMinIndex);
frame.render(data);
AlgoVisHelper.pause(DELAY);
}
}运行效果图
- 插入排序可视化
插入排序算法是将数组中的元素不断向前比较，直到放入到一个适当合适的位置的排序算法，它就好像我们在玩扑克牌的时候进行整理牌面一样。插入排序也是一个O(n^2)时间复杂度的算法。
由于8是第一个元素，它前面没有元素，所以8不需要移动，并被确定下来
我们来看第二个元素6，6与前面的元素8比较，6比8小，所以6要放到8的前面，并被确定下来。
然后我们来看第三个元素2，2与之前的8比较，2比8小，与8交换位置，再与6比较，2比6小，再与6交换位置，此时确定了下来。
然后我们来看第四个元素3
数据层
public class InsertionSortData {
private int[] numbers;
@Getter
@Setter
private int orderedIndex = -1; //[0..orderedIndex)是有序的
@Getter
@Setter
private int currentIndex = -1; //当前正在处理的元素的索引
public InsertionSortData(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("无效的排序数组索引");
}
return numbers[index];
}
public void swap(int i,int j) {
if (i < 0 || i >= numbers.length || j <0 || j >= numbers.length) {
throw new IllegalArgumentException("无效的排序数组索引");
}
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}视图层
@Getter
public class AlgoFrame extends JFrame {
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);
g2d.addRenderingHints(hints);
//具体绘制
// TODO: 绘制自己的数据data
int w = canvasWidth / data.N();
for (int i = 0;i < data.N();i++) {
if (i < data.getOrderedIndex()) {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Red);
}else {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Grey);
}
if (i == data.getCurrentIndex()) {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.LightBlue);
}
AlgoVisHelper.fillRectangel(g2d,i * w,canvasHeight - data.get(i),
w - 1,data.get(i));
}
}
@Override
public Dimension getPreferredSize() {
return new Dimension(canvasWidth,canvasHeight);
}
}
private int canvasWidth;
private int canvasHeight;
//设置自己的数据
private InsertionSortData data;
public AlgoFrame(String title,int canvasWidth,int canvasHeight) {
super(title);
this.canvasWidth = canvasWidth;
this.canvasHeight = canvasHeight;
AlgoCanvas canvas = new AlgoCanvas();
canvas.setOpaque(true);
this.setContentPane(canvas);
this.pack();
this.setResizable(false);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setVisible(true);
}
public AlgoFrame(String title) {
this(title,1024,768);
}
public void render(InsertionSortData data) {
this.data = data;
this.repaint();
}
}控制层
public class AlgoVisualizer {
private static int DELAY = 20;
//创建自己的数据
private InsertionSortData data; //数据
private AlgoFrame frame; //视图
public AlgoVisualizer(int sceneWidth,int sceneHeight,int N) {
//初始化数据
// TODO: 初始化数据
data = new InsertionSortData(N,sceneHeight);
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
//根据情况决定是否加入键盘鼠标监听器
new Thread(() -> {
run();
}).start();
});
}
/**
* 动画逻辑
*/
private void run() {
setData(0,-1);
// TODO: 编写自己的动画逻辑
for (int i = 0;i < data.N();i++) {
setData(i,i);
for (int j = i;j > 0 && data.get(j) < data.get(j - 1);j--) {
data.swap(j,j - 1);
setData(i + 1,j - 1);
}
}
setData(data.N(),-1);
}
private void setData(int orderedIndex,int currentIndex) {
data.setOrderedIndex(orderedIndex);
data.setCurrentIndex(currentIndex);
frame.render(data);
AlgoVisHelper.pause(DELAY);
}
}main方法
public class InsertionSortMain {
public static void main(String[] args) {
int sceneWidth = 800;
int sceneHeight = 800;
int N = 100;
AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth,sceneHeight,N);
}
}展示图形
插入排序的优化
由于以上的插入排序算法需要经过大量的交换的过程，我们可以对这个交换的过程进行优化
此时我们不直接将6与8比较，而是将6复制一份出来。
由于8比6大，我们将8后移一位。
由于第0个位置前面没有元素，6不需要再做比较，就将6放入该位置，并确认。
，
然后考察2的位置，将2复制一份。
由于8比2大，所以8后移一位
由于6比2大，所以将6也后移一位。
由于6是第0个位置，没有可比较的了，我们将2放到该位置。
现在我们将3复制一份出来
8比3大，将8后移一位
6比3大，6后移一位
2比3小，所以3放到第1个位置，并确认
优化后跟原方法的对比
public class InsertionSort {
private InsertionSort() {
}
@SuppressWarnings("unchecked")
public static Comparable[] betterSort(Comparable[] arr) {
for (int i = 0;i < arr.length;i++) {
Comparable e = arr[i];
int j;
for (j = i;j > 0 && arr[j - 1].compareTo(e) > 0;j--) {
arr[j] = arr[j - 1];
}
arr[j] = e;
}
return arr;
}
@SuppressWarnings("unchecked")
public static Comparable[] sort(Comparable[] arr) {
for (int i = 0;i < arr.length;i++) {
for (int j = i;j > 0 && arr[j].compareTo(arr[j - 1]) < 0;j--) {
swap(j,j - 1,arr);
}
}
return arr;
}
private static void swap(int i,int j,Comparable[] arr) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
Integer[] numbers1 = new Integer[1000];
for (int i = 0;i < numbers1.length;i++) {
numbers1[i] = (int) (Math.random() * 1000) + 1;
}
Integer[] numbers2 = numbers1.clone();
long start1 = System.nanoTime();
System.out.println(Arrays.toString(InsertionSort.sort(numbers1)));
System.out.println((System.nanoTime() - start1) / 1000000000.0);
long start2 = System.nanoTime();
System.out.println(Arrays.toString(InsertionSort.betterSort((numbers2))));
System.out.println((System.nanoTime() - start2) / 1000000000.0);
}
}运行结果
[2, 5, 5, 5, 6, 6, 9, 10, 12, 12, 14, 14, 14, 15, 15, 15, 18, 19, ...] 0.007879546 [2, 5, 5, 5, 6, 6, 9, 10, 12, 12, 14, 14, 14, 15, 15, 15, 18, 19, ...] 0.00452523
在一个近乎有序的数组进行排序时，我们的插入排序的时间复杂度可以进化到O(n)级别，在这种特殊的情况下，它是最快的一种排序方式。
数据层
public class InsertionSortData {
public enum Type {
Default,
NearlyOrdered;
}
private int[] numbers;
@Getter
@Setter
private int orderedIndex = -1; //[0..orderedIndex)是有序的
@Getter
@Setter
private int currentIndex = -1; //当前正在处理的元素的索引
public InsertionSortData(int N,int randomBound,Type dataType) {
numbers = new int[N];
for (int i = 0;i < N;i++) {
numbers[i] = (int) (Math.random() * randomBound) + 1;
}
//生成一个近乎有序的数组
if (dataType == Type.NearlyOrdered) {
Arrays.sort(numbers);
int swapTime = (int)(0.02 * N);
for (int i = 0;i < swapTime;i++) {
int a = (int)(Math.random() * N);
int b = (int)(Math.random() * N);
swap(a,b);
}
}
}
public InsertionSortData(int N,int randomBound) {
this(N,randomBound,Type.Default);
}
public int N() {
return numbers.length;
}
public int get(int index) {
if (index < 0 || index >= numbers.length) {
throw new IllegalArgumentException("无效的排序数组索引");
}
return numbers[index];
}
public void swap(int i,int j) {
if (i < 0 || i >= numbers.length || j <0 || j >= numbers.length) {
throw new IllegalArgumentException("无效的排序数组索引");
}
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}控制层
public class AlgoVisualizer {
private static int DELAY = 20;
//创建自己的数据
private InsertionSortData data; //数据
private AlgoFrame frame; //视图
public AlgoVisualizer(int sceneWidth,int sceneHeight,int N,InsertionSortData.Type dataType) {
//初始化数据
// TODO: 初始化数据
data = new InsertionSortData(N,sceneHeight,dataType);
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
//根据情况决定是否加入键盘鼠标监听器
new Thread(() -> {
run();
}).start();
});
}
public AlgoVisualizer(int sceneWidth,int sceneHeight,int N) {
this(sceneWidth,sceneHeight,N,InsertionSortData.Type.Default);
}
/**
* 动画逻辑
*/
private void run() {
setData(0,-1);
// TODO: 编写自己的动画逻辑
for (int i = 0;i < data.N();i++) {
setData(i,i);
for (int j = i;j > 0 && data.get(j) < data.get(j - 1);j--) {
data.swap(j,j - 1);
setData(i + 1,j - 1);
}
}
setData(data.N(),-1);
}
private void setData(int orderedIndex,int currentIndex) {
data.setOrderedIndex(orderedIndex);
data.setCurrentIndex(currentIndex);
frame.render(data);
AlgoVisHelper.pause(DELAY);
}
}main方法
public class InsertionSortMain {
public static void main(String[] args) {
int sceneWidth = 800;
int sceneHeight = 800;
int N = 100;
AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth,sceneHeight,N,InsertionSortData.Type.NearlyOrdered);
}
}显示图形
最后值得一提的是，在n比较小的时候，插入排序比O(nlog n)的排序算法有优势。插入排序算法经常用作是高级排序算法在处理到小样本时的一个优化。
- 归并排序可视化
归并排序算法是将一个数组分成两部分——左边和右边，然后使用同样的算法对左边进行排序，再使用同样的算法对右边进行排序。之后将两个有序的数组，归并成一个有序的数组。
对于划分成一个元素的部分，它本身就是有序的
然后我们对其不同的划分，进行两两归并
再通过相应的划分，两两归并成有序数组
最后将剩下的两个有序数组，归并成一个有序的数组
所以我们这里给出一个归并排序的算法类
public class MergeSort {
private MergeSort() {
}
public static void sort(Comparable[] arr) {
int n = arr.length;
sort(arr,0,n - 1);
}
/**
* 递归使用归并排序，对arr[l..r]的范围进行排序
* @param arr
* @param l
* @param r
*/
private static void sort(Comparable[] arr,int l,int r) {
if (l >= r) {
return;
}
//此处l + r是有可能造成整型溢出的
// int mid = (l + r) /2;
int mid = l + (r - l) / 2;
sort(arr,l,mid);
sort(arr,mid + 1,r);
merge(arr,l,mid,r);
}
/**
* 将arr[l..mid]和arr[mid+1..r]两部分进行归并
* @param arr
* @param l
* @param mid
* @param r
*/
@SuppressWarnings("unchecked")
private static void merge(Comparable[] arr,int l,int mid,int r) {
Comparable[] aux = Arrays.copyOfRange(arr,l,r + 1);
int i = l; // i指向左半部分的起始索引位置l
int j = mid + 1; // j指向右半部分起始索引位置mid + 1
for (int k = l;k <= r;k++) {
if (i > mid) { //如果左半部分元素已经全部处理完毕
arr[k] = aux[j - l];
j++;
}else if (j > r) { //如果右半部分元素已经全部处理完毕
arr[k] = aux[i - l];
i++;
}else if (aux[i - l].compareTo(aux[j - l]) < 0) { //左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i - l];
i++;
}else { //左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j - l];
j++;
}
}
}
}现在我们来写可视化的部分
数据层
public class MergeSortData {
@Getter
private int[] numbers;
@Getter
@Setter
private int l;
@Getter
@Setter
private int r;
@Getter
@Setter
private 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("无效的排序数组索引");
}
return numbers[index];
}
public void set(int index,int value) {
if (index < 0 || index >= numbers.length) {
throw new IllegalArgumentException("无效的排序数组索引");
}
numbers[index] = value;
}
public void swap(int i,int j) {
if (i < 0 || i >= numbers.length || j <0 || j >= numbers.length) {
throw new IllegalArgumentException("无效的排序数组索引");
}
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}视图层
@Getter
public class AlgoFrame extends JFrame {
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);
g2d.addRenderingHints(hints);
//具体绘制
// TODO: 绘制自己的数据data
int w = canvasWidth / data.N();
for (int i = 0;i < data.N();i++) {
if (i >= data.getL() && i <= data.getR()) {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Green);
}else {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Grey);
}
if (i >= data.getL() && i <= data.getMergeIndex()) {
AlgoVisHelper.setColor(g2d,AlgoVisHelper.Red);
}
AlgoVisHelper.fillRectangel(g2d,i * w,canvasHeight - data.get(i),
w - 1,data.get(i));
}
}
@Override
public Dimension getPreferredSize() {
return new Dimension(canvasWidth,canvasHeight);
}
}
private int canvasWidth;
private int canvasHeight;
//设置自己的数据
private MergeSortData data;
public AlgoFrame(String title,int canvasWidth,int canvasHeight) {
super(title);
this.canvasWidth = canvasWidth;
this.canvasHeight = canvasHeight;
AlgoCanvas canvas = new AlgoCanvas();
canvas.setOpaque(true);
this.setContentPane(canvas);
this.pack();
this.setResizable(false);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setVisible(true);
}
public AlgoFrame(String title) {
this(title,1024,768);
}
public void render(MergeSortData data) {
this.data = data;
this.repaint();
}
}控制层
public class AlgoVisualizer {
private static int DEALY = 20;
//创建自己的数据
private MergeSortData data; //数据
private AlgoFrame frame; //视图
public AlgoVisualizer(int sceneWidth,int sceneHeight,int N) {
//初始化数据
// TODO: 初始化数据
data = new MergeSortData(N,sceneHeight);
//初始化视图
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("欢迎",sceneWidth,sceneHeight);
new Thread(() -> {
run();
}).start();
});
}
/**
* 动画逻辑
*/
private void run() {
setData(-1,-1,-1);
// TODO: 编写自己的动画逻辑
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);
// int mid = (l + r) / 2;
int mid = l + (r - l) / 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.getNumbers(),l,r + 1);
int i = l;
int j = mid + 1;
for (int k = l;k <= r;k++) {
if (i > mid) {
data.set(k,aux[j - l]);
j++;
}else if (j > r) {
data.set(k,aux[i - l]);
i++;
}else if (aux[i - l] < aux[j - l]) {
data.set(k,aux[i - l]);
i++;
}else {
data.set(k,aux[j - l]);
j++;
}
setData(l,r,k);
}
}
private void setData(int l,int r,int mergeIndex) {
data.setL(l);
data.setR(r);
data.setMergeIndex(mergeIndex);
frame.render(data);
AlgoVisHelper.pause(DEALY);
}
}main方法
public class MergeSortMain {
public static void main(String[] args) {
int sceneWidth = 800;
int sceneHeight = 800;
int N = 100;
AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth,sceneHeight,N);
}
}图像显示
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读