DIV CSS 佈局教程網

把冒泡排序畫出來:排序算法的可視化實作
編輯:JavaScript基礎知識     

在百度前端技術學院的任務清單裡,看到一題要求用 JavaScript 做「可視化的排序算法」,覺得挺有意思就研究了一下。原本打算把冒泡排序和快速排序一起做掉,無奈快排在「如何呈現遞迴與分區過程」這一步卡得有點久,只好先放一邊。

冒泡排序的原理

冒泡排序應該不陌生,兩個巢狀 for 迴圈就能搞定。它的運作方式是:先比較第 1 個與第 2 個數,若前者較大就交換位置;接著比較第 2 個與第 3 個,同樣規則處理,就這樣一路比到底。一趟下來,最大的數字必然被推到最右端。

然而一趟只能確定一個最大值,我們還需要第二大、第三大……一路到最小值,所以外面還得再包一層迴圈。JavaScript 版本如下:

/* 冒泡排序 */
function bubbleSort(arr) {
  if (arr.length <= 1) { return arr; }
  var temp = 0;
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

可視化的兩條思路

要把排序過程「演出來」,可以選擇其中一種做法:

1、每完成一步就讓程式暫停一下(JavaScript 沒有 sleep,得自己變相實作),這樣在觀看者眼中,排序就是一格一格往前推進的,而不會一瞬間結束。

2、維護一個陣列,把每一步之後的狀態都存成快照,等排序全部跑完,再依序把這些快照畫出來。我這裡採用的就是第二種。

var snapshots = [];  // 快照集合
var timer = null;    // 定時器
var arr = [50,21,5,89,13,35,69,44,60,15,51,80,55,71]; // 待排序陣列

/* 冒泡排序 */
function bubbleSort(arr) {
  if (arr.length <= 1) { return arr; }
  var temp = 0;
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        snapshots.push(JSON.parse(JSON.stringify(arr))); // 記錄一次快照
      }
    }
  }
  return arr;
}

Array.prototype.bubbleSort = function() {
  return bubbleSort(this);
}

這裡用 JSON.parse(JSON.stringify(arr)) 做深拷貝,是為了避免快照之間互相參照到同一個陣列——否則存下來的每一筆都會是最終狀態,動畫就白做了。

排序結束後,我們手上就有了一整組記錄著完整蛻變過程的快照;接著只要按固定時間間隔逐筆繪製,過程便可視化。

/* 繪圖 */
function painting() {
  var container = document.getElementById("container");
  var bars = [].slice.call(document.querySelectorAll(".bar")); // 把 NodeList 轉成真陣列

  for (var i = 0; i < arr.length; i++) {
    if (bars.length != arr.length) {
      var bar = document.createElement("div");
      bar.className = "bar";
      container.appendChild(bar);
    } else {
      break; // bar 數量已等於陣列長度,停止建立
    }
  }

  var snapshot = snapshots.shift() || []; // 取出最前面那筆快照
  console.log(snapshot);

  if (snapshot.length != 0) {
    for (var i = 0; i < bars.length; i++) {
      bars[i].innerHTML = snapshot[i];
      bars[i].style.height = snapshot[i] * 5 + "px";
      bars[i].style.left = (i + 1) * 50 + "px";
    }
  } else {
    clearInterval(timer); // 快照畫完,收工
    return;
  }
}

arr.bubbleSort();               // 先排序並收集快照
timer = setInterval(painting, 200); // 每 200ms 畫一格

實際執行的樣子如下:

線上展示:https://jerellin.github.io/visualization.html

小結

看起來還算炫對吧?只是快排的可視化到最後仍沒做出來,這件事讓我頗為苦惱,看來基礎還是不到家,得繼續補。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved