Skip to content

Instantly share code, notes, and snippets.

@GZShi

GZShi/index.html

Last active August 29, 2015 14:06
Show Gist options
  • Save GZShi/b00a076c7adf95ed22dc to your computer and use it in GitHub Desktop.
Save GZShi/b00a076c7adf95ed22dc to your computer and use it in GitHub Desktop.
Download ZIP
Sort Animation
Raw
index.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Sort Animation</title>
<script src="sort_animation.js"></script>
</head>
<body>
<style>
body {
font-family: sans-serif;
}
div#selection {
text-align: center;
margin: 20px auto;
}
select {
width: 160px;
}
div#play-ground {
width: 420px;
height: 420px;
border: 1px solid gray;
box-shadow: 0 0 5px gray;
margin: 30px auto;
position: relative;
}
div.stick {
width: 15px;
/*background: #666;*/
position: absolute;
-webkit-transition: 0.13s;
transition: 0.13s;
bottom: 0;
}
div#progress {
width: 500px;
height: 7px;
background: #eee;
margin: 30px auto;
position: relative;
}
div#progress div {
height: 100%;
/*box-shadow: 0 0 10px black;*/
background: gray;
}
.color-default {
background: #34495e;
-webkit-transition: 0.1;
transition: 0.1;
}
.color-true {
background: #e74f3f;
-webkit-transition: 0.1;
transition: 0.1;
}
.color-false {
background: #27ae60;
-webkit-transition: 0.1;
transition: 0.1;
}
</style>
<div id="selection">
<label for="select-sort">选择算法：</label>
<select name="sorts" id="select-sort">
<option value="bubble">冒泡排序</option>
<option value="quick">快速排序</option>
<option value="insertion">插入排序</option>
<option value="shell">希尔排序</option>
<option value="selection">选择排序</option>
<!-- <option value="shell">希尔排序</option> -->
</select>
<button id="btn-start">开始演示</button>
</div>
<div id="play-ground"></div>
<div id="progress">
<div id="progress-inner" style="width: 0"></div>
</div>
</body>
</html>
Raw
sort_animation.js
;(function () {
//
//
// 常量定义
//
var ARRAY_SIZE = 20;
var SWAP_INTERVAL = 320;
var COMPARE_INTERVAL = 320;
var MAX_HEIGHT = 500;
var PLAY_GROUND = 'play-ground';
//
//
// 工具
//
function UIDGenerator(begin) {
var id = begin || 0;
return function () {
return id++;
}
}
var getUID = UIDGenerator(0);
// 生成前导0数字串
function zeroPad(int, zeros) {
zeros = parseInt(zeros) || 3;
int = parseInt(int);
return ('0000000000' + int).substr(-1 * zeros);
}
// 兼容IE的forEach
function forEach(arr, method) {
for(var i = 0, len = arr.length; i < len; ++i) {
method(arr[i], i, arr);
}
return arr;
}
//
//
// DOM 节点相关操作
//
// 简化的节点查询
function getID(id) {
var ret = document.getElementById(id);
if(!ret) {
console.log('bad id query: ' + id);
debugger;
ret = {};
}
return ret;
}
// 设置节点的位置
function setPosStyle(dom, pos) {
pos = parseInt(pos) || 0;
var posPixel = pos*20 + 15;
dom.style.left = posPixel + 'px';
dom.setAttribute('data-pos', pos);
}
// 设置节点的高度（百分比 0~1）
function setHeightStyle(dom, percent) {
percent = parseFloat(percent) || 0;
var height = (100 * percent) + '%';
dom.style.height = height;
}
// 交换两个节点的位置
function swapDom(domAID, domBID, callback) {
var domA = getID('stick' + domAID);
var domB = getID('stick' + domBID);
// 第一步，交换位置
var posA = domA.getAttribute('data-pos');
var posB = domB.getAttribute('data-pos');
setPosStyle(domA, posB);
setPosStyle(domB, posA);
// 第二步，交换ID（即保持数组下标的顺序）
var tempID = domA.id;
domA.id = domB.id;
domB.id = tempID;
// 第三步，等待动画结束，回调
setTimeout(callback, SWAP_INTERVAL);
}
// 创建一个新的节点
function createDom(pos, value, maxValue) {
var div = document.createElement('div');
div.style.position = 'absolute';
div.style.bottom = '0px';
div.style.width = '10px';
div.style['transition'] = (SWAP_INTERVAL/1000) + 's';
div.classList.add('color-default');
div.id = 'stick' + getUID();
setPosStyle(div, pos);
setHeightStyle(div, value/maxValue);
return div;
}
// 在画布里面插入新的节点
function insertDom(dom) {
var playGround = document.getElementById(PLAY_GROUND);
playGround.appendChild(dom);
}
// 设置进度条进度
function setProgress(percent) {
percent = 100 * parseFloat(percent);
document.getElementById('progress-inner').style.width = percent + '%';
}
function setDomColor(seq, flag, callback) {
if(Array.isArray(seq) == false) {
seq = [seq];
}
for(var i = 0, len = seq.length; i < len; ++i) {
var dom = getID('stick' + seq[i]);
if(!dom) {
console.log('Bad seq:');
console.log(seq);
} else {
dom.classList.remove('color-default');
dom.classList.add(flag ? 'color-true' : 'color-false');
}
}
setTimeout(function () {
for(var i = 0, len = seq.length; i < len; ++i) {
var dom = getID('stick' + seq[i]);
if(!dom) {
console.log('Bad seq:');
console.log(seq);
} else {
dom.classList.add('color-default');
dom.classList.remove(flag ? 'color-true' : 'color-false');
}
}
callback();
}, COMPARE_INTERVAL);
}
// 流程控制
var Control = (function () {
function Control() {
this.frames = [];
this.currentFrame = 0;
this.destFrame = 0;
this.playFlag = 'pause';
this.direction = 1;
this.onStopCall = function() {};
}
Control.prototype = {
// 递归运行
run: function () {
var self = this;
function next() {
var total = self.frames.length;
// 如果达到指定的终点
if(self.direction > 0 && self.currentFrame > self.destFrame) {
self.onStopCall();
return;
} else if(self.direction < 0 && self.currentFrame < self.destFrame) {
self.onStopCall();
return;
}
if(self.currentFrame >= total || self.currentFrame < 0) {
return;
} else {
if(self.playFlag != 'run') {
// setTimeout(next, 50);
return ;
} else {
var current = self.currentFrame;
self.currentFrame += self.direction;
self.frames[current](next, self.currentFrame, total);
}
}
}
next();
},
// 添加帧
addFrame: function (frameWork) {
this.frames.push(frameWork);
return this;
},
pause: function () {
this.playFlag = 'pause';
return this
},
play: function () {
var self = this;
if(self.destFrame == self.currentFrame) {
self.destFrame = self.direction > 0 ? self.frames.length - 1 : 0;
}
setTimeout(function () {
var shouldPlay = false;
if(self.playFlag != 'run') {
shouldPlay = true;
}
self.playFlag = 'run';
if(shouldPlay) self.run();
}, 16);
return self;
},
onStop: function (onStopCall) {
var self = this;
self.onStopCall = function () {
onStopCall();
self.destFrame = self.direction > 0 ? self.frames.length - 1 : 0;
};
return self;
}
}
return Control;
})();
//
//
// 排序算法
//
var sort = {};
sort.bubble = function (arr, onCompare, onSwap) {
var begin = 0;
var end = arr.length;
for(var i = begin; i < end; ++i) {
for(var j = begin; j < end - i - 1; ++j) {
if(onCompare(arr, j, j+1)) {
onSwap(arr, j, j+1);
}
}
}
};
sort.quick = function (arr, onCompare, onSwap) {
function qsort(arr, left, right) {
var center = Math.floor((left + right) / 2);
var pivot = arr[center];
var i = left;
var j = right;
while(i < j) {
while( i < center && onCompare(arr, center, i) /*arr[i] <= arr[center]*/) {
++i;
}
if(i < center) {
// 动画帧
onSwap(arr, center, i);
// arr[center] = arr[i];
center = i;
}
while( j > center && onCompare(arr, j, center) /*arr[j] > arr[center]*/) {
--j;
}
if(j > center) {
// 动画帧
onSwap(arr, center, j);
// arr[center] = arr[j];
center = j;
}
}
arr[center] = pivot;
if(center - left > 1) qsort(arr, left, center - 1);
if(right - center > 1) qsort(arr, center + 1, right);
}
qsort(arr, 0, arr.length - 1);
};
sort.insertion = function (arr, onCompare, onSwap) {
var begin = 0;;
var end = arr.length;
for(var i = begin + 1; i < end; ++i) {
var j = i;
while(j > begin && onCompare(arr, j-1, j)) {
onSwap(arr, j, j-1);
j--;
}
}
};
sort.shell = function (arr, onCompare, onSwap) {
var begin = 0;
var end = arr.length;
var gap = Math.floor((end - begin) / 2);
while(gap >= 1) {
// 内部实际上是步长可变的插入排序
for(var i = begin + gap; i < end; ++i) {
var j = i;
while(j >= begin + gap && onCompare(arr, j - gap, j)) {
onSwap(arr, j, j -gap);
j -= gap;
}
}
gap = Math.floor(gap / 2);
}
};
sort.selection = function (arr, onCompare, onSwap) {
var minPos = 0;
var begin = 0;
var end = arr.length;
for(var i = 0; i < end; ++i) {
minPos = i;
for(var j = i + 1; j < end; ++j) {
if(onCompare(arr, minPos, j))
minPos = j;
}
if(minPos != i) {
onSwap(arr, minPos, i);
}
}
};
// 主函数
function main(method) {
getID('btn-start').disabled = true;
getID(PLAY_GROUND).innerHTML = '';
getUID = UIDGenerator(0);
var initArr;
// 初始化数组
var arr = [];
for(var i = 0; i < ARRAY_SIZE; ++i) arr.push(i+1);
// 打乱数组
arr = arr.sort(function () {
return Math.random() - 0.5;
});
arr = initArr || arr;
var insertControl = new Control();
forEach(arr, function (e, i, a) {
var dom = createDom(i, e, a.length);
insertControl.addFrame(function (next, current, total) {
insertDom(dom);
setTimeout(next, 100);
});
});
insertControl.play().onStop(function () {
// 开始排序
var sortControl = new Control();
sort[method](arr, function (a, i, j) {
if(i < 0 || j < 0) {
debugger;
}
var compareResult = a[i] > a[j];
sortControl.addFrame(function (next, now, total) {
setDomColor([i, j], compareResult, next);
});
return compareResult;
}, function (a, i, j) {
if(Array.isArray(a)) {
var temp = a[i];
a[i] = a[j];
a[j] = temp;
}
sortControl.addFrame(function (next, now, total) {
swapDom(i, j, next);
setProgress(now/total);
});
});
console.log(arr.join(', '));
sortControl.play().onStop(function () {
getID('btn-start').disabled = false;
});
});
}
window.onload = function () {
getID('btn-start').addEventListener('click', function (event) {
var sortMethod = getID('select-sort').value;
main(sortMethod);
}, false);
};
window.myScript = function (script) {
return eval(script);
};
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment