Tips:
形象化演示排序算法可以让初学者快速理解，最近在看canvas，试着用js+canvas自己做了一个。
已有比较好的demo：jun-lu的SortAnimate，旧金山大学的David Galles教授的算法演示课件。

实现思路

  • 获取输入字符串
  • 存入数组S[]中
  • 新建一个对象数组Rect[]{ x , y , target_x , target_y , text:S[i]}（注：x , y 是当前坐标，target_x , target_y 是目的坐标，text 记录字符）
  • 排序
  • 使用插入排序进行顺序排序，当数值有交换行为时， 用track_insert[]记录进行交换的元素在数组中的位置（方便在绘制动画时进行坐标定位）
  • 因为我用的是插入排序，属于arr[i]和arr[i+1]进行交换，所以只需要记录i就可以。
    • 绘制
  • 图片绘制function Draw(){}
  • 图片坐标更新function Update(){}
  • 使用setInterval()定时调用Draw()和Update()函数进行页面刷新

效果

初始界面

排序过程

gif演示

小结

做动画都是一个原理，不短刷新更新坐标，擦除，绘制，之前用opencv做的2d的小游戏也是同样的原理。

Source code

.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="Content-Type" content="text/html;charset=utf-8">
    <link rel="stylesheet" type="text/css" href="css/demo.css"/>
    <script type="text/javascript"src="js/demo2.js"></script>
    <title>Demo</title>
</head>
<body>  
    <div id="container">
        <div>
            <p>Input String：
                <input  name="string" id="tin" type="text"/>
            </p>                    
        </div>
        <div>
            <p> 
                <input type="button" onclick="showDemo()"id="bin" value="Show"/>
            </p>
            <canvas id="mycanvas"  ></canvas>
        </div>
    </div>
</body>
</html>

.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
var S;
var Coordinate_y = 40;
var Rect = new Array();
var track_insert = new Array();
var cons = 0;
var cnt;

function func() {
//获取字符串，存入数组
    S = document.getElementsByName("string")[0].value.split("");
//依据数组元素，完成对象数组
    for (var i = 0; i < S.length; i++) {
        var rect = {
            x: 30 * i,
            y: Coordinate_y,
            target_x: 30 * i,
            target_y: Coordinate_y,
            text: S[i]
        }
        Rect.push(rect);
    }
    insertSort(S);
}

function insertSort(arr) {
    var i = 1,
    j, key, temp;
    for (; i < arr.length; i++) {
        j = i;
        key = arr[i];
        while (--j >= 0) {
            if (arr[j] > key) {
                arr[j + 1] = arr[j];
                arr[j] = key;
//当数据有交换时，记录下标
                track_insert.push(j);
            } else {
                break;
            }
        }
    }
}
//坐标更新
function update() {
    if (cons > track_insert.length) {
        return;
    }
    if (cons == 0) {
        cnt = track_insert[cons];
        Rect[cnt].target_x = Rect[cnt + 1].x;
        Rect[cnt + 1].target_x = Rect[cnt].x;
        cons += 1;
        console.log(cnt);
    }
    if (Rect[cnt].x == Rect[cnt].target_x) {
        if (cons == track_insert.length) {
            cons += 1;
            return;
        }
        var tem = Rect[cnt];
        Rect[cnt] = Rect[cnt + 1];
        Rect[cnt + 1] = tem;
        cnt = track_insert[cons];
        Rect[cnt].target_x = Rect[cnt + 1].x;
        Rect[cnt + 1].target_x = Rect[cnt].x;
        cons += 1;
        console.log(cnt);
    } else {
        Rect[cnt].x += 1;
        Rect[cnt + 1].x -= 1;
    }
}
//绘制图像
function draw(context) {
    context.clearRect(0, 0, context.canvas.width, context.canvas.height);
    for (var i = 0; i < Rect.length; i++) {
        if ((Rect[i].x - Rect[i].target_x) >= 2 || (Rect[i].x - Rect[i].target_x) < -2) {
            context.fillStyle = "yellow";
            context.fillRect(Rect[i].x, Rect[i].y, 25, 25);
            context.fillStyle = "blue";
            context.fillText(Rect[i].text, Rect[i].x + 10, Rect[i].y + 15);
        } else {
            context.strokeStyle = "blue";
            context.strokeRect(Rect[i].x, Rect[i].y, 25, 25);
            context.fillStyle = "blue";
            context.fillText(Rect[i].text, Rect[i].x + 10, Rect[i].y + 15);
        }
    }
    context.fillText("插入排序", 40, 80);
}
function showDemo() {
    func();
    var c = document.getElementById("mycanvas");
    c.width = 600;
    c.height = 300;
    var context = c.getContext("2d");
//40ms调用一次函数
    setInterval(function() {
        draw(context);
        update();
    }, 40);
}

.css

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
input#tin{
    margin-bottom: 5px;
    background-color: #fff;opacity:0.85;8
    width:20px;
    height:25px; 
    border-width: 1;
    font-size: 17px; 
    color: #000; 
    font-weight: 500; 
    border-radius: 5px;
    cursor:pointer; 
}
input#bin{
    background-color: gray;
    width:80; 
    height:25; 
    border-width: 2; 
    font-size: 20px; 
    color: #FFFFFF; 
    font-weight: 500;
    cursor:pointer; 
    border-radius: 5px;
}
canvas#mycanvas{
    border:1px solid;
    width: 600px;
    height: 300px;
    margin-top: 5px;
    border-radius: 5px;
}
div#container{
    margin-left: 70px;
}