2017/3/26 17:03 更新
我把一大堆算法的代碼放最后了胰伍，要不影響閱讀乱顾，要看的同學(xué)去最后找
正文開始
這個題目，老早就知道了肛循，但是當(dāng)時因為忙著學(xué)習(xí)別的東西，雖然感覺挺有趣银择，但是一直也沒著手去做多糠。這幾天在補全排序算法的知識，剛好欢摄，也把這個給做了出來熬丧。
下邊是demo笋粟，和代碼地址
簡介
首先簡單分析下問題怀挠，大概有這幾個點需要解決
- 排序算法
- 動畫
- 如何將算法用動畫展示
很顯然析蝴，第三點是最難的。
想要實現(xiàn)這個绿淋，首先要會排序算法闷畸，關(guān)于常用的排序算法，在文章里就不在多說吞滞，這個不是我們的重點佑菩，我僅僅貼出我寫的算法代碼。
動畫其實也很簡單裁赠，用css設(shè)置一些過度效果殿漠，比如顏色啊，漸漸消失佩捞，漸漸出現(xiàn)啊绞幌，之類的。也不多說一忱，大家可以隨意發(fā)揮莲蜘。我做的，只設(shè)置了顏色的漸變帘营。
我們重點分析票渠，如何將算法的每一步用動畫展示。
如果你對排序算法還不太了解芬迄，我把排序算法的基本代碼都用JavaScript寫了一遍问顷，放在文章結(jié)尾。大家可以根據(jù)下文說的禀梳，自行改造择诈，
分析，如何展示算法動畫
如果要把排序過程用柱狀圖變換來表示出皇，很顯然羞芍，也就是說，把對數(shù)組的操作過程郊艘，轉(zhuǎn)變成了對一組dom的操作荷科。
我們對算法都有一定了解了，縱觀來看纱注，實現(xiàn)可視化動畫畏浆，其實就是表現(xiàn)出幾個關(guān)鍵的元素。
- 每趟的關(guān)鍵目標元素（target——藍色）
- 正在比較的元素（checked——綠色）
- 經(jīng)過比較狞贱，需要與target元素進行交換的checked元素（selecked——紅色）
那么如何把上邊這些關(guān)鍵元素刻获，以動畫效果反應(yīng)出來呢？
一上來瞎嬉，我們可能回想蝎毡，那就排一步厚柳，展示一步唄。但是沐兵，排一步别垮，展示一步就等于是讓js引擎走一步，然后暫停js引擎扎谎，再讓渲染引擎走一步碳想，如此循環(huán)往復(fù)直到結(jié)束。但是js引擎開弓沒有回頭箭毁靶，我們還沒有一個方法胧奔，可以讓它先停下來歇一歇。
有的同學(xué)可能說预吆，用定時器葡盗，但是，往深處一想就會發(fā)現(xiàn)定時器是不行的啡浊，它有問題：
- js引擎單線程觅够，導(dǎo)致使用定時器的結(jié)果跟我們期望的不同。
- 作用域問題
如果使用定時器巷嚣，必然要大量使用喘先，因為每一步dom操作，都需要一個定時器廷粒，在設(shè)計過程解決上邊的問題窘拯，肯定一頭包。（我當(dāng)時仔細想了想坝茎，就放棄了涤姊，太亂了）
所以，我們要換一個思路
我們都知道嗤放，動畫其實就是一幀一幀的靜態(tài)畫面思喊，也就是一個個狀態(tài)的變換。那么我們其實可以在對純數(shù)組進行排序的過程中次酌，記錄下我們需要的所有幀恨课，然后等排序結(jié)束后，對我們收集到的所有幀岳服，進行從頭到尾的展示
假如我們的html是這樣
<div id="box">
<div class="item" style="height:54px">54</div>
·····
·····
</div>
用高度代表了數(shù)字
可以這樣設(shè)計
numArr = box盒子下剂公，所有item的innerHTML轉(zhuǎn)換成數(shù)字（Number()方法）
function sort(arr) {
var animationArr = [];// 這個數(shù)組用來記錄幀
// 下邊某個算法的具體過程，在排序的過程中吊宋，記錄幀
...
return animationArr // 將幀數(shù)組返回
}
sort(numArr);
那么幀數(shù)組中的數(shù)據(jù)要怎么設(shè)計呢纲辽？其實我們知道，排序算法都有每一趟，和每一趟的第一步拖吼，第二步鳞上，第三步，.......
而根據(jù)我們的具體動畫需要绿贞，可以做如下設(shè)計
// 最內(nèi)層的對象因块，只是一個例子橘原，是快速排序時候的每幀的可能狀態(tài)籍铁。
animationArr = [
[
{
currentArrStart = undefined,
currentArrEnd = undefined,
target = undefined,
selected = undefined,
checked = undefined,
removeSelected = undefined,
},
...
...
],
...
...
]
最外層數(shù)組的每一項，表示每一趟趾断；里層數(shù)組的每一項拒名，表示每一步的幀狀態(tài)對象，每種排序算法芋酌，最內(nèi)層的幀狀態(tài)對象的屬性可能是不同的增显，我們可以根據(jù)具體需要來設(shè)計。
我們拿到了幀數(shù)組脐帝，那么如何展現(xiàn)動畫呢同云？
很簡單，一個setInterval()堵腹，每次循環(huán)炸站，就展示一幀，而且疚顷，這樣設(shè)計的話旱易，我們還可以通過控制循環(huán)間隔時間，來實現(xiàn)加快速度腿堤，減慢速度的效果阀坏。
分析結(jié)束
接下來，我就拿快速排序為例子笆檀，來一步步展示忌堂，如何實現(xiàn)它。
以快速排序為例的具體實現(xiàn)過程
-
首先酗洒，簡單說下項目結(jié)構(gòu)
項目結(jié)構(gòu)圖
很簡單浸船，沒什么復(fù)雜的
html
我們有這樣的DOM結(jié)構(gòu)
<div id="box">
<div class="item" style="height:54px">54</div>
<div class="item" style="height:14px">14</div>
<div class="item" style="height:77px">77</div>
<div class="item" style="height:28px">28</div>
<div class="item" style="height:99px">99</div>
<div class="item" style="height:65px">65</div>
<div class="item" style="height:49px">49</div>
<div class="item" style="height:89px">89</div>
<div class="item" style="height:21px">21</div>
<div class="item" style="height:25px">25</div>
<div class="item" style="height:50px">50</div>
<div class="item" style="height:80px">80</div>
<div class="item" style="height:19px">19</div>
<div class="item" style="height:37px">37</div>
<div class="item" style="height:31px">31</div>
</div>
<div id="sortBtn">
<button id="quickSortBtn" data-method="quickSort">快速排序動畫</button>
</div>
- css
其實關(guān)鍵是下邊的四個.item--就是我們在展示動畫過程中要頻繁操作的類名了。
.item {
padding: 10px 5px;
background-color: gray;
color: #fff;
display: inline-block;
margin-right: 5px;
vertical-align: bottom;
transition: background-color .5s;
}
#box {
padding: 5px 0;
}
.item--current {
background-color: skyblue;
}
.item--checked {
background-color: green;
}
.item--selected {
background-color: red;
}
.item--target {
background-color: blue;
}
- 排序算法
對于每種算法寝蹈，其實我們都要實現(xiàn)兩個方法:
- 傳入純數(shù)字的數(shù)組李命，進行排序，傳出幀數(shù)組
- 這種排序算法對應(yīng)的dom操作方法
以快速排序為例箫老，快速排序的基本寫法在尾部封字，我們對他改進，保留幀。其實每一種算法都可以這樣做阔籽，大家可以自己試一試流妻。（算法的基本寫法都在尾部）。
function quickSort(arrDom) {
// 傳遞進來一個Dom類數(shù)組笆制，對其進行排序
var arr = [],
animationArr = []; // 這個數(shù)組中绅这，存儲每一次動畫的數(shù)據(jù)
for (let i = 0, len = arrDom.length; i < len; i++) {
arr.push(Number(arrDom[i].innerHTML));
}
sort(0, arr.length - 1);
return animationArr;
function sort(left, right) {
let i = left, //左游標 右游標
j = right,
animationArrStep = [],
stardard = arr[left];
animationArrStep.push({
currentArrStart: left,
currentArrEnd: right
});
animationArrStep.push({
target: left
});
if ((right - left) > 0) {
while (i < j) {
for (; i < j; j--) {
animationArrStep.push({
checked: j
});
if (arr[j] < stardard) {
animationArrStep.push({
target: i,
selected: j
});
animationArrStep.push({
removeSelected: i
});
arr[i++] = arr[j];
break;
}
}
for (; i < j; i++) {
animationArrStep.push({
checked: i
});
if (arr[i] > stardard) {
animationArrStep.push({
target: j,
selected: i
});
animationArrStep.push({
removeSelected: j
});
arr[j--] = arr[i];
break;
}
}
}
arr[i] = stardard;
animationArr.push(animationArrStep);
sort(left, i - 1);
sort(i + 1, right);
}
}
}
// 這里是快速排序?qū)?yīng)的dom操作方法，我們在方法形參處設(shè)計了幀狀態(tài)對象的具體內(nèi)容
function quickSortAnimationDom(arrDomBox, {
currentArrStart = undefined,
currentArrEnd = undefined,
// 表示本趟有關(guān)的項的開始和結(jié)尾
target = undefined,
selected = undefined,
checked = undefined,
removeSelected = undefined, // 用來在交換后在辆，移除selected狀態(tài)证薇。
}) {
// arrDom 是包裹柱狀圖的盒子，也就是#box
if (checked !== undefined) {
arrDomBox.children[checked].classList.add("item--checked");
} else if (target !== undefined) {
arrDomBox.children[target].classList.add("item--target");
if (selected !== undefined) {
arrDomBox.children[selected].classList.add("item--selected");
let a = arrDomBox.children[target].cloneNode(true),
b = arrDomBox.children[selected].cloneNode(true);
arrDomBox.replaceChild(b, arrDomBox.children[target]);
arrDomBox.replaceChild(a, arrDomBox.children[selected]);
}
} else if (removeSelected !== undefined) {
arrDomBox.children[removeSelected].classList.remove("item--selected");
} else if (currentArrStart !== undefined && currentArrEnd !== undefined) {
for (let i = currentArrStart; i <= currentArrEnd; i++) {
arrDomBox.children[i].classList.add("item--current");
}
}
}
關(guān)于dom算法匆篓，有一點需要說明浑度，
我們傳進來的arrDomBox，是因為鸦概，排序免不了進行dom的交換操作箩张，為了每次都確保我們獲取的是最新的item節(jié)點，而不是插入前的窗市，所以先慷，必須從父節(jié)點出發(fā)尋找。
關(guān)于這一點咨察，有不明白的同學(xué)论熙，可以留言，咱們再討論扎拣。
animation.js動畫相關(guān)
我們需要把它做成一個小模塊赴肚，避免過多的綁定到window上變量，同時二蓝，也避免定時器操作過程中誉券，取變量錯誤。
這個模塊刊愚，我做的比較簡單踊跟，沒有實現(xiàn)很多功能，比如
- 控制速度大小
- 自動生成數(shù)組
- 算法切換
等等吧鸥诽，但是都留有可控制的口子商玫。
比如，速度牡借，大家可以自己做一做拳昌，控制下speed變量就可以了
切換算法也很簡單，不多說了钠龙。
function SortAnimation() {
this.timer = 0;
this.arrDomBox = {};
this.animationArr = [];
this.speed = 500;
this.sortMethod = {};
this.currentMethod = '';
// sortMethod 的數(shù)據(jù)結(jié)構(gòu)為{method：數(shù)組排序并返回動畫數(shù)組的方法名, animationMethod: dom排序方法名}
}
SortAnimation.prototype = {
getData: function(arrDomBox, method) {
this.arrDomBox = arrDomBox;
this.currentMethod = method;
this.animationArr = this.sortMethod[method].method(arrDomBox.children);
},
ownedMethod: function(methodObj) {
this.sortMethod = methodObj;
},
startAnimation: function() {
var that = this;
// 為了保存下,this炬藤，用了閉包御铃，當(dāng)然還有別的處理辦法。
return function() {
if (that.animationArr.length === 0) {
// 清除DOM樣式
for (let i = 0, len = that.arrDomBox.children.length; i < len; i++) {
that.arrDomBox.children[i].classList.remove("item--target", "item--current", "item--selected", "item--checked");
}
// 動畫結(jié)束
clearTimeout(that.timer);
} else if (that.animationArr[0].length > 0) {
that.sortMethod[that.currentMethod].animationMethod(that.arrDomBox, that.animationArr[0][0]);
that.animationArr[0].shift();
} else {
// 清除DOM樣式
for (let i = 0, len = that.arrDomBox.children.length; i < len; i++) {
that.arrDomBox.children[i].classList.remove("item--target", "item--current", "item--selected", "item--checked");
}
// 進入下一趟排序的動畫
that.animationArr.shift();
}
};
}
}
window.sa = new SortAnimation();
大家也應(yīng)該看到了沈矿，其實寫的是有一定復(fù)用性的上真。根據(jù)我們寫的，最后就可以調(diào)用了
<script>
var sortBtn = document.querySelector("#sortBtn");
sa.ownedMethod({
quickSort: {
method: quickSort,
animationMethod: quickSortAnimationDom
}
})
sortBtn.addEventListener("click", function(event) {
var arrDomBox = document.querySelector("#box");
// 注意羹膳，一定要是父元素睡互，因為，在替換元素的過程中陵像，被替換元素不會消失就珠，如果在最開始直接引用子元素，那么蠢壹，將無法取到替換后的元素
sa.getData(arrDomBox, event.target.dataset.method);
sa.timer = setInterval(sa.startAnimation(), sa.speed);
});
</script>
大功告成Ｉのァ＞叛病图贸！
結(jié)語總結(jié)
其實挺有意思的，博主在這只是拋磚引玉冕广，希望大家有興趣可以動手試一試疏日。當(dāng)然，如果有朋友有任何疑問撒汉，請下邊留言告訴我沟优，能力范圍內(nèi)，我一定答復(fù)睬辐。
如有什么錯誤挠阁，請一定指正。謝謝了
排序算法的代碼
下邊的算法溯饵，我沒有對他們進行很完善的測試侵俗，只是簡單的試了幾個數(shù)組，如果大家發(fā)現(xiàn)問題丰刊，請留言聯(lián)系我隘谣，我會盡快改正。
- 冒泡排序
// 冒泡排序啄巧，共三個寻歧，后兩個為改進算法
function bubbleSort(arr) {
for (let i = 0, len = arr.length; i < len; i++) {
for (let j = 0; j < len - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
// 解構(gòu)賦值，交換變量值
}
}
}
return arr;
}
// 改進：記錄交換位置秩仆，提高速度
function bubbleSortPlus(arr) {
let i = arr.length;
while (i > 0) {
var position = 0;
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
// 解構(gòu)賦值码泛，交換變量值
position = j;
}
}
i = position; // 因為，只有position為0時候澄耍，才說明排好了噪珊。
}
return arr;
}
// 改進：雙冒泡
function bubbleSortDb(arr) {
var top = arr.length - 1,
bottom = 0,
j;
while (bottom < top) {
for (j = bottom; j < top; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
// 解構(gòu)賦值忘衍，交換變量值
}
}
top--;
for (; j > bottom; j--) {
if (arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
// 解構(gòu)賦值，交換變量值
}
}
bottom++;
}
return arr;
}
- 選擇排序
// 選擇排序
function selectSort(arr) {
var minIndex;
for (let i = 0, len = arr.length; i < len; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
- 插入排序
// 插入排序 卿城，后邊有二分優(yōu)化后的
function insertionSort(arr) {
for (let i = 1, len = arr.length; i < len; i++) {
let keyNum = arr[i],
j = i - 1;
while (j >= 0 && arr[j] > keyNum) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = keyNum;
}
return arr;
}
// 二分查找優(yōu)化 插入排序
function binaryInsertionSort(arr) {
for (let i = 1, len = arr.length; i < len; i++) {
let keyNum = arr[i],
left = 0,
right = i - 1;
// 此處枚钓，要考慮兩邊界時候，出現(xiàn)的問題瑟押，不能簡單的left < right搀捷，當(dāng)在右邊界時候，left需要再移動一位多望。
while (left <= right) {
let middle = Math.floor((left + right) / 2);
if (keyNum > arr[middle]) {
left = middle + 1;
} else {
right = middle - 1;
}
}
// 比left大的嫩舟，向右位移一位
for (let j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = keyNum;
}
return arr;
}
- 希爾排序
/ 希爾排序
function shellSort(arr) {
let len = arr.length,
gap = Math.ceil(Math.floor(len / 2) / 2) * 2 - 1;
for (; gap > 0; gap = gap - 2) {
for (let i = gap; i < len; i++) {
let keyNum = arr[i],
j = i - gap;
while (j >= 0 && arr[j] > keyNum) {
arr[j + gap] = arr[j];
j = j - gap;
}
arr[j + gap] = keyNum;
}
}
return arr;
}
- 歸并排序
// 歸并排序
function mergerSort(arr) {
let len = arr.length;
if (len < 2) {
return arr;
}
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merger(mergerSort(left), mergerSort(right));
}
function merger(left, right) {
var arr = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
arr.push(left.shift());
} else {
arr.push(right.shift());
}
}
while (left.length) {
arr.push(left.shift());
}
while (right.length) {
arr.push(right.shift());
}
return arr;
}
- 快速排序
// 快速排序
function quickSort(arr) {
sort(0, arr.length - 1);
return arr;
function sort(left, right) {
let i = left, //左游標 右游標
j = right,
stardard = arr[left];
if ((right - left) > 0) {
while (i < j) {
for (; i < j; j--) {
if (arr[j] < stardard) {
arr[i++] = arr[j];
break;
}
}
for (; i < j; i++) {
if (arr[i] > stardard) {
arr[j--] = arr[i];
break;
}
}
}
arr[i] = stardard;
sort(left, i - 1);
sort(i + 1, right);
}
}
}
- 堆排序
/ 堆排序
function heapSort(arr) {
function heapify(arr, i, unorderedHeapSize) {
let largest = i,
leftChild = 2 * i + 1,
rightChild = 2 * i + 2;
if (leftChild < unorderedHeapSize && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
if (rightChild < unorderedHeapSize && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, unorderedHeapSize);
}
}
function swap(arr, x, y) {
[arr[x], arr[y]] = [arr[y], arr[x]];
}
function buildMaxHeap(arr) {
for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
}
// 建堆
buildMaxHeap(arr);
// 堆排序
for (let i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, 0, i);
}
return arr;
}
