前言
以前寫了很多算法相關(guān)的博客诸蚕，每篇博客都會用word或者processing畫上很多圖，非常浪費(fèi)時(shí)間，那時(shí)候就一直有考慮能不能使用程序來實(shí)現(xiàn)這種過程，不僅不用自己畫那么圖垛叨，而且編程實(shí)現(xiàn)可視化的話，還可以動態(tài)更清晰的表現(xiàn)算法的過程钢悲。于是查找了相關(guān)的資料和自己對算法的理解先實(shí)現(xiàn)一個(gè)冒泡排序的可視化点额，代碼是Android的。
效果
bubble.gif
實(shí)現(xiàn)
要實(shí)現(xiàn)這個(gè)動畫效果莺琳，實(shí)際上需要兩個(gè)基本的模塊組成：一個(gè)BubbleView用于繪制，一個(gè)control控制器载慈，用于控制BubbleView的繪制惭等。
在這里插入圖片描述
1、BubbleView的實(shí)現(xiàn)
要實(shí)現(xiàn)上面的動畫要定義一個(gè)自己的BubbleView繼承View然后重寫View的onDraw()方法办铡，這個(gè)view要包含以下三個(gè)部分：
- 每一個(gè)數(shù)組元素的繪制
- 遍歷數(shù)組中當(dāng)前元素時(shí)的繪制
- 交換時(shí)的繪制
BubbleView中onDraw()方法中具體流程如下：
在這里插入圖片描述
1辞做、每一個(gè)數(shù)組元素的繪制
public class SortingVisualizer extends View {
Paint paint;
Paint textPaint;
int[] array;
int lineStrokeWidth = getDimensionInPixel(10);
public SortingVisualizer(Context context) {
super(context);
initialise();
}
public SortingVisualizer(Context context, AttributeSet atrrs) {
super(context, atrrs);
initialise();
}
private void initialise() {
paint = new Paint();
paint.setColor(Color.DKGRAY);
paint.setStyle(Paint.Style.FILL);
paint.setStrokeWidth(lineStrokeWidth);
textPaint = new TextPaint();
textPaint.setColor(Color.BLACK);
textPaint.setTextSize(getDimensionInPixelFromSP(15));
}
@Override
protected void onDraw(Canvas canvas) {
super.onDraw(canvas);
if (array != null) {
int numberOfLines = array.length;
float margin = (getWidth() - (30 * numberOfLines)) / (numberOfLines + 1);
float xPos = margin + getDimensionInPixel(10);
for (int i = 0; i < array.length; i++) {
canvas.drawLine(xPos, getHeight() - (float) ((array[i] / 10.0) * getHeight()), xPos, getHeight(), paint);
canvas.drawText(String.valueOf(array[i]), xPos - lineStrokeWidth / 3, getHeight() - (float) ((array[i] / 10.0) * getHeight()) - 30, textPaint);
xPos += margin + 30;
}
public void setData(int[] integers) {
this.array = integers;
invalidate();
}
上面定義了兩個(gè)畫筆Paint，一個(gè)用于繪制元素的柱體寡具，
canvas.drawLine(xPos, getHeight() - (float) ((array[i] / 10.0) * getHeight()), xPos, getHeight(), paint);
xPos += margin + 30;
一個(gè)用于繪制柱體上面的text
canvas.drawText(String.valueOf(array[i]), xPos - lineStrokeWidth / 3, getHeight() - (float) ((array[i] / 10.0) * getHeight()) - 30, textPaint);
2秤茅、 遍歷數(shù)組中當(dāng)前元素時(shí)的繪制
protected void onDraw(Canvas canvas) {
super.onDraw(canvas);
if (array != null) {
int numberOfLines = array.length;
float margin = (getWidth() - (30 * numberOfLines)) / (numberOfLines + 1);
float xPos = margin + getDimensionInPixel(10);
for (int i = 0; i < array.length; i++) {
if (i == highlightPosition) {
canvas.drawLine(xPos, getHeight() - (float) ((array[i] / 10.0) * getHeight()), xPos, getHeight(), highlightPaintTrace);
//
}
xPos += margin + 30;
}
}
}
highlightPosition是外部排序時(shí)設(shè)置的值
3、交換時(shí)的繪制
protected void onDraw(Canvas canvas) {
super.onDraw(canvas);
if (array != null) {
int numberOfLines = array.length;
float margin = (getWidth() - (30 * numberOfLines)) / (numberOfLines + 1);
float xPos = margin + getDimensionInPixel(10);
for (int i = 0; i < array.length; i++) {
if (i == highlightPositionOne) {
canvas.drawLine(xPos, getHeight() - (float) ((array[i] / 10.0) * getHeight()), xPos, getHeight(), highlightPaintSwap);
}
highlightPositionOne = -1;
highlightPositionTwo = -1;
}
}
control實(shí)現(xiàn)
control里面包括了冒泡排序算法童叠，和控制BubbleView重繪框喳，以及繪制的間隔等功能课幕，
private void sort() {
for (int i = 0; i < array.length; i++) {
boolean swapped = false;
for (int j = 0; j < array.length - 1 - i; j++) {
highlightTrace(j);
sleep();
if (array[j] > array[j + 1]) {
highlightSwap(j, j + 1);
addLog("Swapping " + array[j] + " and " + array[j + 1]);
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
sleep();
}
}
if (!swapped) {
break;
}
sleep();
}
}
public void highlightSwap(final int one, final int two) {
activity.runOnUiThread(new Runnable() {
@Override
public void run() {
bubbleView.highlightSwap(one, two);
}
});
}
public void highlightTrace(final int position) {
activity.runOnUiThread(new Runnable() {
@Override
public void run() {
bubbleView.highlightTrace(position);
}
});
}
冒泡排序算法
for (int i = 0; i < array.length; i++) {
boolean swapped = false;
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
參考
1、https://developer.android.com/reference/android/graphics/Canvas
