前言

以前寫了很多算法相關(guān)的博客，每篇博客都會(huì)用word或者processing畫上很多圖，非常浪費(fèi)時(shí)間，那時(shí)候就一直有考慮能不能使用程序來實(shí)現(xiàn)這種過程，不僅不用自己畫那么圖，而且編程實(shí)現(xiàn)可視化的話，還可以動(dòng)態(tài)更清晰的表現(xiàn)算法的過程。于是查找了相關(guān)的資料和自己對算法的理解先實(shí)現(xiàn)一個(gè)冒泡排序的可視化，代碼是Android的。

效果

bubble.gif

實(shí)現(xiàn)

要實(shí)現(xiàn)這個(gè)動(dòng)畫效果，實(shí)際上需要兩個(gè)基本的模塊組成：一個(gè)BubbleView用于繪制，一個(gè)control控制器，用于控制BubbleView的繪制。

在這里插入圖片描述

1、BubbleView的實(shí)現(xiàn)
要實(shí)現(xiàn)上面的動(dòng)畫要定義一個(gè)自己的BubbleView繼承View然后重寫View的onDraw()方法，這個(gè)view要包含以下三個(gè)部分：

1. 每一個(gè)數(shù)組元素的繪制
2. 遍歷數(shù)組中當(dāng)前元素時(shí)的繪制
3. 交換時(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