前端開發—讓演算法"動"起來

前言

上一篇介紹了比較簡單數據結構和演算法，但是很多情況下演算法學習是比較枯燥的，但是非常慶幸的是我們作為前端開發可以自己找點樂子。比如，讓演算法"動"起來。

正文

當然在我們不清楚具體操作細節前我們可以先假設一下，我們能夠用什麼來實現。按照以前看過的排序動畫我將其分為

1.Js操作Dom,再搭配簡單的css

2.Canvas動畫

之後在查資料的時候發現還有人用d3這個庫來完成。

作為一個有(被)夢(坑)想(多)的前端，一開始就得考慮到如何實現套入多個演算法，如果實現單步運行(可能的話還得有往回走的功能),如何實現動畫速度的控制等等。

當然幻想那麼多一下子實現是不現實的，我們得先找一個簡單的例子來看看再一步步深入。

先來看下效果圖

之後我們分析源碼：

css:nnn#field {width:500px;height:510px;background:black;position:relative}n.bar {position:absolute;bottom:0;background:orange;border:1px solid brown;width:24px}nnhtml:nn<div id="field">n <div class="bar"></div>n <div class="bar"></div>n <div class="bar"></div>n <div class="bar"></div>n <div class="bar"></div>n <div class="bar"></div>n <div class="bar"></div>n <div class="bar"></div>n <div class="bar"></div>n <div class="bar"></div>n</div>nnjavascript:nn!function(d){nn var bars = [].slice.call(d.querySelectorAll(.bar));n var arr = [8, 10, 3, 5, 6, 9, 2, 4, 7, 1];n var state = [];nn var draw = function(){n var bar, s;n s = state.shift() || [];n for(bar in bars){n bars[bar].style.height = 25 * s[bar] + px;n bars[bar].style.left = 25 * bar + px;n }n }nn var sort = function(arr){n for(var i = 0; i < arr.length; i++){n for(var j = 0; j < arr.length - i - 1; j++){n if(arr[j] > arr[j+1]){n arr[j] = arr[j] + arr[j+1];n arr[j+1] = arr[j] - arr[j+1];n arr[j] = arr[j] - arr[j+1];n tttstate.push(JSON.parse(JSON.stringify(arr)));n tttn tttn }n }n }n }n n sort(arr);n setInterval(draw, 500);nn}(document)n

整個流程其實很清晰，但是其中部分代碼讓我疑惑了一段時間，經過google和問群里的朋友，終於解惑。我們先來理清這段代碼的思路

首先這個動畫是將大小寬度都定死了。以及排序數組的數量需要和html結構里bar的數量一致。

1.html的bar是長方體，它的寬是24px然後有個1px的border，因此在代碼中動態改變left的時候需要設定為25.

2.js代碼中用一個匿名函數包裹代碼。

bars = [].slice.call(d.querySelectorAll(.bar));

這段將獲取的nodelist轉為成一個對象數組，這樣方便對其中每個bar進行單獨修改樣式

3.設定一個state空數組來保存每一個狀態,記住這才是動畫的關鍵。

4.state.shift()臨時像將數組模擬成隊列，draw函數根據其第一個出列的內容來重新排列列表,在

setInterval(draw, 400)的配合下，就能形成一個動畫排序。

5 sort函數和我們之前介紹的冒泡排序是一樣的，只不過這裡有一句

state.push(JSON.parse(JSON.stringify(arr)));

這句是核心，一看是乍看是不是很奇怪，為什麼要JSON.stringify然後再JSON.parse。這裡需要大家認真思考一下。

想想在哪裡看過它？

深拷貝？

對，就是深拷貝。對於深拷貝不理解的我這裡給出它的含義：

深拷貝是複製變數值，對於非基本類型的變數，則遞歸至基本類型變數後，再複製。

我這兩天也整理過深拷貝，但是我還是一下子沒理解為什麼這裡要這麼寫。

一開始我想偏差了，我一開始認為arr作為一個數字數組，對它進行深拷貝和用一個中間變數進行操作不是一樣么，於是我加了這麼幾行代碼

var temp = arr

state.push(temp);

然後 動畫消失了，頁面變成最後排好序的樣子。

這時候群里有人提醒了我一句淺複製會修改原數組。我這才根據state.push反應過來。

在sort內部，每一個push都是為了保存交換後排序數組的狀態，如果我用temp來代替它，那麼state裡面將全放著相同的最後排完序的狀態。而JSON.parse(JSON.stringify(arr))對arr進行深複製，不會改動arr原數組，因此它就類似快照一樣把每次排序的狀態給push到state.然後配合setInterval一張一張的放映形成動畫。

一個簡單的排序動畫其實裡面也包含了不少有價值的內容。

回過頭這麼一看，這不是很容易套公(算)式(法)么

把我們之前學的插入排序拿來改改:

function exchange(array, i, j) {n var t = array[i];n array[i] = array[j];n array[j] = t;n }nn var sort2 = function(numbers){n for (var i = 0; i < numbers.length; i++) {n /*n * 當已排序部分的當前元素大於value，n * 就將當前元素向後移一位，再將前一位與value比較n */n for (var j = i; j > 0 && numbers[j] < numbers[j - 1]; j--) {n // If the array is already sorted, we never enter this inner loop!n exchange(numbers, j, j - 1);n state.push(JSON.parse(JSON.stringify(numbers)));n console.log("此時數組:" + numbers)n }n }nn }n

分分鐘改變動畫效果。

這樣我們就完成目標中的一小步了。

然後之前考慮的單步運行和動畫速度控制我們都可以改變相應參數來完成。

我們再來看看如何用canvans來實現。

先來看效果

代碼如下:

html:nn<div id="restart">重新生成數據並排序</div>n<canvas id="canvas"><canvas>nncss:nnbody {n background-color: black;n text-align: center;n}n#restart {n color: white;n font-family: monospace;n}tnnjavascript:nn!function(){nn var canvas = document.getElementById(canvas); n var data = [];n canvas.width = window.innerWidth-30;n canvas.height = window.innerHeight-35;n CreateData(IntRandom(300, 100));n Render();nnn function Restart() {n data = [];n CreateData(IntRandom(300, 100));n }nn function CreateData(val) {n for(var i = 0; i <= val; i++) n data[i] = IntRandom(500, 10);n n }nn function BubbleSort() {n var temp;n for(var i = 0; i <= data.length-1; i++) {n if(data[i] > data[i+1]) {n temp = data[i];n data[i] = data[i+1];n data[i+1] = temp;n }n }n }nn function Draw() {n var posX = 0,n posY = canvas.height;nn for(var i = 0; i <= data.length-1; i++) {n c.fillStyle = RandomColor(i);n c.fillRect(posX, canvas.height, 5, -data[i]);n n posY--;n posX+=6;n }n }nn document.onclick = function() {n Clear();n Restart();n };nn function Render() {n requestAnimationFrame(Render);n Clear();n BubbleSort();n Draw();n }nn function Clear() {n c.fillStyle = "black";n c.fillRect(0, 0, canvas.width, canvas.height);n }nn function RandomColor(i) {n var n = Math.random() * 360;n return "hsl("+parseInt(i)+", 100%, 50%)"n }nnfunction IntRandom(max, min) {n return Math.floor(Math.random() * max + min);n}tnn}()n

這份代碼其實是有缺陷的，不過沒關係，在下面的分析中我們可以邊看邊改

1.首先是常規canvas操作，如果對canvas不上很熟悉的同學建議把高程相關部分刷一遍。

具體操作就是，獲取整個瀏覽器屏幕長款，減去一部分作為畫布的長寬，這是為了讓生成的序列不會跟瀏覽器邊緣貼合。

CreateData()這個方法就是隨機生成一堆隨機高度的長方形。

BubbleSort()就是常見的冒泡排序，但是在這裡我們看到這只是一個冒泡演算法，並沒有像之前做一系列快照。(這裡就涉及到了我們提到的缺陷)

draw()方法 從屏幕左側坐標為0的點開始，這個posY其實毫無用處，因為我們的高度是根據之前隨機生成一堆隨機高度的長方形數組data來生成的。posX自加是為了保持間隔。

RandomColor() 這個方法根據高度來改變顏色。

之後是本代碼的核心render()

之前我們看到操作dom的版本，動畫效果是通過setInterval(draw, 500)來實現的，那麼這裡的動畫效果哪裡來？

我們可以看到這裡用到了HTML5的API：

requestAnimationFrame

它的優勢在於保證跟瀏覽器的繪製走，如果瀏覽設備繪製間隔是16.7ms，那就這個間隔繪製；如果瀏覽設備繪製間隔是10ms, 就10ms繪製。不會存在過度繪製的問題，動畫不會掉幀。

這個從我們的效果圖裡也能看齣動畫的確很流暢。然而，這段代碼是有問題的。問題在於它沒有設置中止的標識，也就是它會不停刷新瀏覽器，時間久了將會卡住。而且細心的會發現之前我們看到的冒泡排序它只有一層循環。render()方法靠著循環調用硬生生把這些無序數組給堆成有序了。。。

而且太流暢的動畫一氣呵成，讓我們無法仔細觀察排序的經過，因此我們需要對其進行修改。

這裡我們停下來思考一下，該如何改？

想想之前js操作dom版是怎麼做的？我們同樣可以套進去。

只需要把排序演算法換成之前一樣的。然後把render改成如下：

var fps = 1; //每秒幾幀nn var lastExecution = new Date().getTime();nn function Render() {n if (state.length > 0) { //動畫播放，沒播完繼續nn var now = new Date().getTime();nn if ((now - lastExecution) > (1000 / fps)) {n Clear();n Draw();n lastExecution = new Date().getTime();n }nn requestAnimationFrame(Render);nn }n }n

不過需要注意的是當你想重置requestAnimationFrame的時候，需要一開始就註明var stopId = requestAnimationFrame(Render);

然後配合cancelAnimationFrame(stopId)即可暫停繼續。

最終效果如下:

有了以上基礎你完全可以自己開始構建一個屬於自己的排序動畫。這篇就到這裡。

結尾

所有代碼和別的補充已經放在github

而且會不斷更新。有興趣的可以去看看並動手敲一遍。

PS:前天的文章突然給我增加那麼多關注是未料到的,看著人數肉眼可見的上漲還是很高興的，當然如果你們能花點時間給我github點個star那就再好不過來??

謝謝大家的觀看,下一篇指不定什麼時候,別等啦。(如果star漲了我就加快速度2333)

資料

visualgo.net的排序動畫

David Galles教授Canvas+JS實現排序動畫

推薦閱讀：