摘要：函數和我們之前介紹的冒泡排序是一樣的，只不過這里有一句這句是核心，一看是乍看是不是很奇怪，為什么要然后再。而且細心的會發(fā)現(xiàn)之前我們看到的冒泡排序它只有一層循環(huán)。

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

1.Js操作Dom,再搭配簡單的css
2.Canvas動畫

之后在查資料的時候發(fā)現(xiàn)還有人用d3這個庫來完成。

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

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

先來看下效果圖

之后我們分析源碼：

css:

#field {width:500px;height:510px;background:black;position:relative}
.bar {position:absolute;bottom:0;background:orange;border:1px solid brown;width:24px}

html:


  

  

  

  

  

  

  

  

  

  



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)

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

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

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

2.js代碼中用一個匿名立即函數包裹代碼。
  bars = [].slice.call(d.querySelectorAll(".bar"));
這段將獲取的nodelist轉為成一個對象數組，這樣方便對其中每個bar進行多帶帶修改樣式

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

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都是為了保存交換后排序數組的狀態(tài)，如果我用temp來代替它，那么state里面將全放著相同的最后排完序的狀態(tài)。而JSON.parse(JSON.stringify(arr))對arr進行深復制，不會改動arr原數組，因此它就類似快照一樣把每次排序的狀態(tài)給push到state.然后配合setInterval一張一張的放映形成動畫。

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

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

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

    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++) {
        /*
         * 當已排序部分的當前元素大于value，
         * 就將當前元素向后移一位，再將前一位與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("此時數組:" + numbers)
        }
     }

   }
   

分分鐘改變動畫效果。

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

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

不過在繼續(xù)深入之前我們先來看看如何用canvans來實現(xiàn)。

先來看效果

代碼如下:

html:

重新生成數據并排序


css:

body {
  background-color: black;
  text-align: center;
}
#restart {
  color: white;
  font-family: monospace;
}    

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);
}    

}()

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

1.首先是常規(guī)canvas操作，如果對canvas不上很熟悉的同學建議把高程相關部分刷一遍。
具體操作就是，獲取整個瀏覽器屏幕長款，減去一部分作為畫布的長寬，這是為了讓生成的序列不會跟瀏覽器邊緣貼合。
CreateData()這個方法就是隨機生成一堆隨機高度的長方形。

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

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

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

之后是本代碼的核心render()
之前我們看到操作dom的版本，動畫效果是通過setInterval(draw, 500)來實現(xiàn)的，那么這里的動畫效果哪里來？
我們可以看到這里用到了HTML5的API：

requestAnimationFrame

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

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

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

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

想想之前js操作dom版是怎么做的？我們同樣可以套進去。
只需要把排序算法換成之前一樣的。然后把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);

        }
    }

  

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

然后配合cancelAnimationFrame(stopId)即可暫停繼續(xù)。

最終效果如下:

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

所有代碼和別的補充已經放在github
而且會不斷更新。有興趣的可以去看看并動手敲一遍。

visualgo.net的排序動畫

David Galles教授Canvas+JS實現(xiàn)排序動畫