前言
上一篇介紹了比較簡單數(shù)據(jù)結(jié)構(gòu)和算法蒋纬，但是很多情況下算法學(xué)習(xí)是比較枯燥的召边，但是非常慶幸的是我們作為前端開發(fā)可以自己找點樂子。比如缎谷，讓算法”動”起來。
正文
當(dāng)然在我們不清楚具體操作細(xì)節(jié)前我們可以先假設(shè)一下灶似，我們能夠用什么來實現(xiàn)列林。按照以前看過的排序動畫我將其分為
1.Js操作Dom,再搭配簡單的css
2.Canvas動畫
之后在查資料的時候發(fā)現(xiàn)還有人用d3這個庫來完成。
作為一個有(被)夢(坑)想(多)的前端酪惭，一開始就得考慮到如何實現(xiàn)套入多個算法席纽，如果實現(xiàn)單步運行(可能的話還得有往回走的功能),如何實現(xiàn)動畫速度的控制等等。
當(dāng)然幻想那么多一下子實現(xiàn)是不現(xiàn)實的撞蚕，我們得先找一個簡單的例子來看看再一步步深入润梯。
先來看下效果圖
之后我們分析源碼：
javascript:
!function(d){
? var bars = [].slice.call(d.querySelectorAll('.bar'));
? var arr = [8, 10, 3, 5, 6, 9, 2, 4, 7, 1];
? var state = [];
? var draw = function(){
? ? var bar, s;
? ? s = state.shift() || [];
? ? for(bar in bars){
? ? ? bars[bar].style.height = 25 * s[bar] + 'px';
? ? ? bars[bar].style.left = 25 * bar? + 'px';
? ? }
? }
? var sort = function(arr){
? ? for(var i = 0; i < arr.length; i++){
? ? ? for(var j = 0; j < arr.length - i - 1; j++){
? ? ? ? if(arr[j] > arr[j+1]){
? ? ? ? ? arr[j]? = arr[j] + arr[j+1];
? ? ? ? ? arr[j+1] = arr[j] - arr[j+1];
? ? ? ? ? arr[j]? = arr[j] - arr[j+1];
? ? ? ? ? state.push(JSON.parse(JSON.stringify(arr)));
? ? ? ? }
? ? ? }
? ? }
? }
? sort(arr);
? setInterval(draw, 500);
}(document)
整個流程其實很清晰，但是其中部分代碼讓我疑惑了一段時間甥厦，經(jīng)過google和問群里的朋友纺铭，終于解惑。我們先來理清這段代碼的思路
首先這個動畫是將大小寬度都定死了刀疙。以及排序數(shù)組的數(shù)量需要和html結(jié)構(gòu)里bar的數(shù)量一致舶赔。
1.html的bar是長方體，它的寬是24px然后有個1px的border谦秧，因此在代碼中動態(tài)改變left的時候需要設(shè)定為25.
2.js代碼中用一個匿名立即函數(shù)包裹代碼竟纳。
? bars = [].slice.call(d.querySelectorAll('.bar'));
這段將獲取的nodelist轉(zhuǎn)為成一個對象數(shù)組，這樣方便對其中每個bar進(jìn)行單獨修改樣式
3.設(shè)定一個state空數(shù)組來保存每一個狀態(tài),記住這才是動畫的關(guān)鍵疚鲤。
4.state.shift()臨時像將數(shù)組模擬成隊列锥累，draw函數(shù)根據(jù)其第一個出列的內(nèi)容來重新排列列表,在
setInterval(draw, 400)的配合下，就能形成一個動畫排序集歇。
5 sort函數(shù)和我們之前介紹的冒泡排序是一樣的桶略，只不過這里有一句
state.push(JSON.parse(JSON.stringify(arr)));
這句是核心，一看是乍看是不是很奇怪，為什么要JSON.stringify然后再JSON.parse际歼。這里需要大家認(rèn)真思考一下惶翻。
想想在哪里看過它？
深拷貝鹅心？
對吕粗，就是深拷貝。對于深拷貝不理解的我這里給出它的含義：
深拷貝是復(fù)制變量值旭愧，對于非基本類型的變量溯泣，則遞歸至基本類型變量后，再復(fù)制榕茧。
我這兩天也整理過深拷貝，但是我還是一下子沒理解為什么這里要這么寫客给。
一開始我想偏差了用押，我一開始認(rèn)為arr作為一個數(shù)字?jǐn)?shù)組，對它進(jìn)行深拷貝和用一個中間變量進(jìn)行操作不是一樣么靶剑，于是我加了這么幾行代碼
var temp = arr
state.push(temp);
然后 動畫消失了蜻拨，頁面變成最后排好序的樣子。
這時候群里有人提醒了我一句淺復(fù)制會修改原數(shù)組桩引。我這才根據(jù)state.push反應(yīng)過來缎讼。
在sort內(nèi)部，每一個push都是為了保存交換后排序數(shù)組的狀態(tài)坑匠，如果我用temp來代替它血崭，那么state里面將全放著相同的最后排完序的狀態(tài)。而JSON.parse(JSON.stringify(arr))對arr進(jìn)行深復(fù)制厘灼，不會改動arr原數(shù)組夹纫，因此它就類似快照一樣把每次排序的狀態(tài)給push到state.然后配合setInterval一張一張的放映形成動畫。
一個簡單的排序動畫其實里面也包含了不少有價值的內(nèi)容设凹。
回過頭這么一看舰讹，這不是很容易套公(算)式(法)么
把我們之前學(xué)的插入排序拿來改改:
? ? function exchange(array, i, j) {
? ? ? var t = array[i];
? ? ? array[i] = array[j];
? ? ? array[j] = t;
? ? }
? var sort2 = function(numbers){
? ? for (var i = 0; i < numbers.length; i++) {
? ? ? ? /*
? ? ? ? * 當(dāng)已排序部分的當(dāng)前元素大于value，
? ? ? ? * 就將當(dāng)前元素向后移一位闪朱，再將前一位與value比較
? ? ? ? */
? ? for (var j = i; j > 0 && numbers[j] < numbers[j - 1]; j--) {
? ? ? ? ? // If the array is already sorted, we never enter this inner loop!
? ? ? ? ? exchange(numbers, j, j - 1);
? ? ? ? ? state.push(JSON.parse(JSON.stringify(numbers)));
? ? ? ? ? console.log("此時數(shù)組:" + numbers)
? ? ? ? }
? ? }
? }
分分鐘改變動畫效果月匣。
這樣我們就完成目標(biāo)中的一小步了。
然后之前考慮的單步運行和動畫速度控制我們都可以改變相應(yīng)參數(shù)來完成奋姿。
不過在繼續(xù)深入之前我們先來看看如何用canvans來實現(xiàn)锄开。
先來看效果
代碼如下:
html:
javascript:
!function(){
? var canvas = document.getElementById('canvas');
? var data = [];
? canvas.width = window.innerWidth-30;
? canvas.height = window.innerHeight-35;
? CreateData(IntRandom(300, 100));
? Render();
? function Restart() {
? ? data = [];
? ? CreateData(IntRandom(300, 100));
? }
? function CreateData(val) {
? ? for(var i = 0; i <= val; i++)
? ? ? data[i] = IntRandom(500, 10);
? }
? function BubbleSort() {
? ? var temp;
? ? for(var i = 0; i <= data.length-1; i++) {
? ? ? if(data[i] > data[i+1]) {
? ? ? ? temp = data[i];
? ? ? ? data[i] = data[i+1];
? ? ? ? data[i+1] = temp;
? ? ? }
? ? }
? }
? function Draw() {
? ? var posX = 0,
? ? ? ? posY = canvas.height;
? ? for(var i = 0; i <= data.length-1; i++) {
? ? ? c.fillStyle = RandomColor(i);
? ? ? c.fillRect(posX, canvas.height, 5, -data[i]);
? ? ? posY--;
? ? ? posX+=6;
? ? }
? }
? document.onclick = function() {
? ? Clear();
? ? Restart();
? };
? function Render() {
? ? ? requestAnimationFrame(Render);
? ? ? Clear();
? ? ? BubbleSort();
? ? ? Draw();
? }
? function Clear() {
? ? c.fillStyle = "black";
? ? c.fillRect(0, 0, canvas.width, canvas.height);
? }
? function RandomColor(i) {
? ? var n = Math.random() * 360;
? ? return "hsl("+parseInt(i)+", 100%, 50%)"
? }
function IntRandom(max, min) {
? return Math.floor(Math.random() * max + min);
}
}()
這份代碼其實是有缺陷的，不過沒關(guān)系称诗，在下面的分析中我們可以邊看邊改
1.首先是常規(guī)canvas操作院刁，如果對canvas不上很熟悉的同學(xué)建議把高程相關(guān)部分刷一遍。
具體操作就是粪狼，獲取整個瀏覽器屏幕長款退腥，減去一部分作為畫布的長寬任岸，這是為了讓生成的序列不會跟瀏覽器邊緣貼合。
CreateData()這個方法就是隨機(jī)生成一堆隨機(jī)高度的長方形狡刘。
BubbleSort()就是常見的冒泡排序享潜，但是在這里我們看到這只是一個冒泡算法，并沒有像之前做一系列快照嗅蔬。(這里就涉及到了我們提到的缺陷)
draw()方法 從屏幕左側(cè)坐標(biāo)為0的點開始剑按，這個posY其實毫無用處，因為我們的高度是根據(jù)之前隨機(jī)生成一堆隨機(jī)高度的長方形數(shù)組data來生成的澜术。posX自加是為了保持間隔艺蝴。
RandomColor() 這個方法根據(jù)高度來改變顏色。
之后是本代碼的核心render()
之前我們看到操作dom的版本鸟废，動畫效果是通過setInterval(draw, 500)來實現(xiàn)的猜敢，那么這里的動畫效果哪里來？
我們可以看到這里用到了HTML5的API：
requestAnimationFrame
它的優(yōu)勢在于保證跟瀏覽器的繪制走盒延，如果瀏覽設(shè)備繪制間隔是16.7ms缩擂，那就這個間隔繪制；如果瀏覽設(shè)備繪制間隔是10ms, 就10ms繪制添寺。不會存在過度繪制的問題胯盯，動畫不會掉幀。
這個從我們的效果圖里也能看出動畫的確很流暢计露。然而博脑，這段代碼是有問題的。問題在于它沒有設(shè)置中止的標(biāo)識票罐，也就是它會不停刷新瀏覽器趋厉，時間久了將會卡住。而且細(xì)心的會發(fā)現(xiàn)之前我們看到的冒泡排序它只有一層循環(huán)胶坠。render()方法靠著循環(huán)調(diào)用硬生生把這些無序數(shù)組給堆成有序了君账。。沈善。
而且太流暢的動畫一氣呵成乡数，讓我們無法仔細(xì)觀察排序的經(jīng)過，因此我們需要對其進(jìn)行修改闻牡。
這里我們停下來思考一下净赴，該如何改？
想想之前js操作dom版是怎么做的罩润？我們同樣可以套進(jìn)去玖翅。 只需要把排序算法換成之前一樣的。然后把render改成如下：
? ? var fps = 1; //每秒幾幀
? ? var lastExecution = new Date().getTime();
? ? function Render() {
? ? ? ? if (state.length > 0) { //動畫播放，沒播完繼續(xù)
? ? ? ? ? ? var now = new Date().getTime();
? ? ? ? ? ? if ((now - lastExecution) > (1000 / fps)) {
? ? ? ? ? ? ? ? Clear();
? ? ? ? ? ? ? ? Draw();
? ? ? ? ? ? ? ? lastExecution = new Date().getTime();
? ? ? ? ? ? }
? ? ? ? ? ? requestAnimationFrame(Render);
? ? ? ? }
? ? }
不過需要注意的是當(dāng)你想重置requestAnimationFrame的時候金度，需要一開始就注明var stopId = requestAnimationFrame(Render);
然后配合cancelAnimationFrame(stopId)即可暫停繼續(xù)应媚。
最終效果如下:
有了以上基礎(chǔ)你完全可以自己開始構(gòu)建一個屬于自己的排序動畫。這篇就到這里猜极。
結(jié)尾
所有代碼和別的補(bǔ)充已經(jīng)放在github?而且會不斷更新中姜。有興趣的可以去看看并動手敲一遍讥珍。
資料
