|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
各位朋友你们好,今天教大家写冒泡排序演示程序,使用语言为Java,不会Java也没关系,其他语言一样可以举一反三。
写演示程序有什么好处,第一是加深对编程语言的理解与应用;第二就是加深对数据结构和算法的理解,防遗忘;第三就是通过这个演示程序出一套视频,教大家。
先看程序运行最终截图:
新建按钮可以新建要排序的元素;单步按钮可以观察排序全过程;运行按钮相当于自动点击单步按钮。
代码如下,已经有很多注释,不解释。
Bar.java
- package com.algorithm.sort;
- import java.awt.Color;
- public class Bar {
- //方块的宽、方块与方块的距离、方块的最大宽度
- public static final int WIDTH = 20, INTERVAL = 10, MAX_HEIGHT = 200;
- //方块的高
- private int height;
- //方块的颜色
- private Color color;
- public Bar(int height, Color color) {
- this.height = height;
- this.color = color;
- }
- public int getHeight() {
- return height;
- }
- public void setHeight(int height) {
- this.height = height;
- }
- public Color getColor() {
- return color;
- }
- public void setColor(Color color) {
- this.color = color;
- }
- }
复制代码
BarGroup.java
- package com.algorithm.sort;
- import java.awt.*;
- public abstract class BarGroup {
- //进行相应排序界面绘制,需要子类重写
- public abstract void draw(Graphics g);
- //单步进行相应排序,需要子类重写
- public abstract void sortStep();
- //判断是否完成排序
- public abstract boolean isDone();
-
- /**
- * 初始化方块
- * @param size 创建方块的大小
- * @param isRandom 如果为ture,表示随机生成方块;否则逆序生成方块
- * @return 生成的方块
- */
- public Bar[] initBarArray(int size, boolean isRandom) {
- Bar[] barArray = new Bar[size];
- if (isRandom) {
- for (int i = 0; i < size; i++) {
- int height = (int) (Math.random() * Bar.MAX_HEIGHT);
- int r = (int) (Math.random() * 255);
- int g = (int) (Math.random() * 255);
- int b = (int) (Math.random() * 255);
- barArray[i] = new Bar(height, new Color(r, g, b));
- }
- } else {
- for (int i = 0; i < size; i++) {
- int height = Bar.MAX_HEIGHT - (Bar.MAX_HEIGHT * i) / size;
- int r = (int) (Math.random() * 255);
- int g = (int) (Math.random() * 255);
- int b = (int) (Math.random() * 255);
- barArray[i] = new Bar(height, new Color(r, g, b));
- }
- }
- return barArray;
- }
-
- /**
- * 绘制一个方块
- * @param g 画笔
- * @param barArray 方块数组(根当于要排序的元素)
- * @param index 欲绘制方块的索引号
- */
- public void drawOneBar(Graphics g, Bar[] barArray, int index) {
- int height = barArray[index].getHeight();
- Color color = barArray[index].getColor();
- int x = 35 + index * (Bar.WIDTH + Bar.INTERVAL);
- int y = 250 - height;
-
- g.setColor(color);
- g.fill3DRect(x, y, Bar.WIDTH, height, true);
- }
-
- /**
- * 绘制一个箭头
- * @param g 画笔
- * @param color 箭头的颜色
- * @param str 箭头下面的文本
- * @param index 箭头上方对应的方块索引
- * @param arrowLength 箭头的长度
- */
- public void arrowText(Graphics g, Color color, String str, int index, int arrowLength) {
- int x = 35 + index * (Bar.WIDTH + Bar.INTERVAL);
- int y = 250 + 15 * arrowLength;
- g.setColor(color);
- g.drawString(str, x, y);
- g.drawLine(x + Bar.WIDTH / 2, 252, x + Bar.WIDTH / 2, y - 15);
- g.drawLine(x + Bar.WIDTH / 2, 252, x + Bar.WIDTH / 2 - 3, 257);
- g.drawLine(x + Bar.WIDTH / 2, 252, x + Bar.WIDTH / 2 + 3, 257);
- }
-
- /**
- * 交换两个方块的位置
- * @param barArray 方块数组
- * @param i 第一个要交换的方块
- * @param j 第二个要交换的方块
- */
- public void swap(Bar[] barArray, int i, int j) {
- Bar tmp = barArray[i];
- barArray[i] = barArray[j];
- barArray[j] = tmp;
- }
- }
复制代码
BubbleSort.java
- package com.algorithm.sort;
- import java.awt.*;
- /**
- * 冒泡排序类
- * @author Focus100
- *
- */
- public class BubbleSort extends BarGroup {
- //方块数组的大小
- private static final int ARRAY_SIZE = 10;
- //方块数组
- private Bar barArray[];
- //方块的inner、outer指针
- private int inner, outer;
- //比较次数、交换次数
- private int comps, swaps;
- //是否完成排序
- private boolean isDone;
-
- public BubbleSort(boolean isRandom) {
- //初始化方块数组,大小为10个
- barArray = initBarArray(ARRAY_SIZE, isRandom);
- //inner一开始指向第一个元素
- inner = comps = swaps = 0;
- //outer一开始指向最后一个元素
- outer = ARRAY_SIZE - 1;
- isDone = false;
- }
-
- /**
- * 完成冒泡排序界面的绘制
- */
- public void draw(Graphics g) {
- for (int i = 0; i < barArray.length; i++)
- drawOneBar(g, barArray, i);
- g.setColor(Color.BLACK);
- g.drawString("比较次数 = " + comps, 10, 30);
- g.drawString("交换次数 = " + swaps, 10, 15);
-
- arrowText(g, Color.BLUE, "inner", inner, 3);
- arrowText(g, Color.BLUE, "inner+1", inner + 1, 3);
- arrowText(g, Color.RED, "outer", outer, 4);
- if (isDone) {
- g.drawString("状态:排序完毕", 10, 45);
- return;
- }
- if (barArray[inner].getHeight() > barArray[inner + 1].getHeight())
- g.drawString("状态:需交换", 10, 45);
- else
- g.drawString("状态:不需交换", 10, 45);
- }
-
- /**
- * 单步进行冒泡排序
- */
- public void sortStep() {
- if (isDone)
- return;
- //比较次数加1
- comps++;
- //如果前面的元素大于后面的元素,则交换
- if (barArray[inner].getHeight() > barArray[inner + 1].getHeight()) {
- swap(barArray, inner, inner + 1);
- swaps++; //交换次数加1
- }
- inner++;
- //inner最多到达outer-1的位置,outer后面的元素是排好的元素
- if (inner > outer - 1) {
- inner = 0;
- outer--;
- //outer最多>=1,如果等于0表示排序完成
- if (outer == 0)
- isDone = true;
- }
- }
-
- /**
- * 判断是否完成排序
- */
- public boolean isDone() {
- return isDone;
- }
- }
复制代码
SortPanel.java
- package com.algorithm.sort;
- import java.awt.*;
- import java.awt.event.*;
- import javax.swing.*;
- public class SortPanel extends JPanel implements ActionListener, Runnable {
- private JButton btnNew, btnStep, btnRun;
- private BarGroup barSort; //排序方块类
- private final int WIDTH = 370, HEIGHT = 320;
- private boolean isRun = false, isRandom = true; //是否用线程排序、是否随机排序
- public SortPanel() {
- //设置宽和高
- setPreferredSize(new Dimension(WIDTH, HEIGHT));
- //设置为流式布局,右对齐
- setLayout(new FlowLayout(FlowLayout.RIGHT));
- //添加三个按钮,并添加监听
- btnNew = new JButton("新建");
- btnNew.addActionListener(this);
- add(btnNew);
- btnStep = new JButton("单步");
- btnStep.addActionListener(this);
- add(btnStep);
- btnRun = new JButton("运行");
- btnRun.addActionListener(this);
- add(btnRun);
- //创建方块类
- barSort = new BubbleSort(isRandom);
- //启动线程
- new Thread(this).start();
- }
- @Override
- public void paint(Graphics g) {
- super.paint(g);
- //绘制排序界面
- barSort.draw(g);
- }
- @Override
- public void actionPerformed(ActionEvent e) {
- switch (e.getActionCommand()) {
- case "新建":
- //点一次随机排序,再点一次逆序排序
- isRandom = isRandom ? false : true;
- barSort = new BubbleSort(isRandom);
- isRun = false;
- break;
- case "单步":
- barSort.sortStep();
- isRun = false;
- break;
- case "运行":
- isRun = true;
- break;
- }
- repaint();
- }
-
- /**
- * 用线程自动完成排序
- */
- @Override
- public void run() {
- while (true) {
- if (isRun && barSort.isDone()) {
- isRun = false;
- return;
- }
-
- if (isRun) {
- barSort.sortStep();
- repaint();
- try {
- Thread.sleep(350);
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- }
- }
- }
复制代码
SoftFrame.java
- package com.algorithm.sort;
- import javax.swing.*;
- public class SoftFrame extends JFrame {
-
- public SoftFrame() {
- this.add(new SortPanel());
- this.setTitle("冒泡排序"); //设置窗口标题
- this.setLocation(50, 100); //设置窗口显示位置
- this.pack(); //适应子窗口大小
- this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); //设置窗口关闭方式
- }
-
- public static void main(String[] args) {
- SoftFrame frame = new SoftFrame();
- frame.setVisible(true);
- }
- }
复制代码 |
|