<!DOCTYPE html>
<html sort-visualize-app>
<head>
<meta charset="UTF-8" />
<title>javascript各种排序算法</title>
<meta name="Description" content="jsdo.it - share JavaScript, HTML5 and CSS -" />
<meta name="Keywords" content="JavaScript,HTML5,CSS" />
<meta name="viewport" content="width=device-width, user-scalable=no, initial-scale=1, maximum-scale=1" />
<style type="text/css">
body {
background: #333;
overflow: hidden;
}
.ui > div {
display: inline-block;
margin-bottom: 5px;
}
.ui input[type=radio] {
display: none;
}
.ui .button-set {
font-size: 0px;
margin: 5px 5px;
}
.ui .button {
display: inline-block;
background: #ddd;
padding: 6px 4px;
border-right: 1px solid #bbb;
font-size: 10px;
font-family: monospace;
}
.ui .button:hover {
background: #ccc;
}
.ui label:first-child .button {
border-radius: 5px 0px 0px 5px;
}
.ui label:last-child .button {
border-radius: 0px 5px 5px 0px;
border-right-width: 0px;
}
.ui label:only-child .button {
border-radius: 5px;
}
.ui input:checked + .button {
background: #666;
color: #fff;
}
.ui input[type=range] {
position: relative;
top: 7px;
}
</style>
<meta charset="UTF-8">
<title>Sort Visualize</title>
<link rel="stylesheet" href="/norahiko/oxly/css" type="text/css" charset="utf-8">
</head>
<body>
<div class="ui">
<div data-bind="foreach: algorithmList" class="button-set">
<label>
<input type="radio" data-bind="checkedValue: $data, checked: $root.algorithm">
<span data-bind="text: $data" class="button"></span> </label>
</div>
<div>
<input type="range" data-bind="
value: speed,
attr: { min: speedMin, max: speedMax }">
</div>
<div data-bind="foreach: sizeList" class="button-set">
<label>
<input type="radio" data-bind="checkedValue: $data, checked: $root.size">
<span data-bind="text: $data" class="button"></span> </label>
</div>
<div class="button-set">
<label> <span data-bind="click: restart" class="button">Restart</span> </label>
</div>
</div>
<div class="graph">
<canvas id="graph-canvas" width="450" height="380"></canvas>
</div>
<script src="http://ajax.aspnetcdn.com/ajax/knockout/knockout-3.0.0.js" type="text/javascript" charset="utf-8"></script>
<script src="/norahiko/oxly/js" type="text/javascript" charset="utf-8"></script>
<script type="text/javascript">
// https://github.com/norahiko/sort-visualize
var helper = {
range : function(min, max) {
var res = [];
for (var i = min; i < max; i++) {
res.push(i);
}
return res;
},
shuffle : function(ary) {
for (var i = ary.length - 1; 0 <= i; i--) {
var rnd = Math.random() * (i + 1) | 0;
helper.swap(ary, i, rnd);
}
},
swap : function(ary, a, b) {
if (a < 0 || b < 0 || ary.length <= a || ary.length <= b) {
throw new Error('IndexError ' + a + " - " + b);
}
var temp = ary[a];
ary[a] = ary[b];
ary[b] = temp;
},
insert : function(ary, from, to) {
while (from != to) {
if (from < to) {
helper.swap(ary, from, from + 1);
from += 1;
} else {
helper.swap(ary, from, from - 1);
from -= 1;
}
}
},
median3 : function(a, b, c) {
if (b <= a)
if (a <= c)
return a;
else if (c <= b)
return b;
else
return c;
else if (c <= a)
return a;
else if (c <= b)
return c;
else
return b;
},
getCanvas : function(id) {
var canvas = document.getElementById(id);
if (canvas === null || canvas.nodeName.toLowerCase() !== 'canvas') {
return document.createElement('canvas');
}
return canvas;
}
};
var graph = {};
(function() {
var canvas;
var ctx;
var width;
var height;
var bgColor = '#333';
var barColor = '#6cf';
var highlightColor = '#cf6';
graph.init = function(c) {
canvas = c;
ctx = canvas.getContext('2d');
width = canvas.offsetWidth;
height = canvas.offsetHeight;
};
graph.draw = function(highlightIndexes, values) {
ctx.fillStyle = bgColor;
ctx.fillRect(0, 0, width, height);
var idx1 = highlightIndexes[0];
var idx2 = highlightIndexes[1];
var size = values.length;
var barWidth = (width - size + 1) / size;
var barHeightUnit = height / size;
var x = 0;
var h = 0;
ctx.fillStyle = barColor;
for (var i = 0; i < values.length; i++) {
h = values[i] * barHeightUnit;
if (i === idx1 || i === idx2) {
ctx.fillStyle = highlightColor;
ctx.fillRect(x, height - h, barWidth, h);
ctx.fillStyle = barColor;
} else {
ctx.fillRect(x, height - h, barWidth, h);
}
x = x + barWidth + 1;
}
};
})();
function SortStep(type, indexes) {
// type = 'swap' | 'highlight' | 'insert'
this.type = type;
this.indexes = indexes;
}
SortStep.SWAP = 'swap';
SortStep.HIGHLIGHT = 'highlight';
SortStep.INSERT = 'insert';
SortStep.prototype.run = function(ary) {
if (this.type === SortStep.SWAP) {
helper.swap(ary, this.indexes[0], this.indexes[1]);
} else if (this.type === SortStep.INSERT) {
helper.insert(ary, this.indexes[0], this.indexes[1]);
this.indexes[0] = -1;
}
};
function SortAlgorithm(values) {
this.values = values;
this.size = values.length;
this.steps = [];
this.finished = false;
}
SortAlgorithm.prototype.sort = function(algorithm) {
this[algorithm]();
this.steps.reverse();
if (algorithm !== 'bogo') {
this.finished = true;
}
};
SortAlgorithm.prototype.addStep = function(type, indexes) {
this.steps.push(new SortStep(type, indexes));
};
SortAlgorithm.prototype.swap = function(a, b) {
helper.swap(this.values, a, b);
this.addStep(SortStep.SWAP, [a, b]);
};
SortAlgorithm.prototype.highlight = function(a, b) {
this.addStep(SortStep.HIGHLIGHT, [a, b]);
};
SortAlgorithm.prototype.insert = function(from, to) {
helper.insert(this.values, from, to);
this.addStep(SortStep.INSERT, [from, to]);
};
SortAlgorithm.prototype.bubble = function bubbleSort() {
for (var i = this.size - 1; 0 < i; i--) {
for (var k = 0; k < i; k++) {
if (this.values[k] > this.values[k + 1]) {
this.swap(k, k + 1);
} else {
this.highlight(k, k + 1);
}
}
}
};
SortAlgorithm.prototype.selection = function selectionSort() {
for (var i = 0; i < this.size - 1; i++) {
var min = i;
for (var k = i + 1; k < this.size; k++) {
this.highlight(min, k);
if (this.values[k] < this.values[min]) {
min = k;
}
}
this.swap(i, min);
}
};
SortAlgorithm.prototype.shaker = function shakerSort() {
var left = 0;
var right = this.size - 1;
var incr = 1;
var i = 0;
var next;
var lastSwapped = 0;
var count = 0;
while (left < right) {
next = i + incr;
if ((incr === 1 && this.values[i] > this.values[next]) || (incr === -1 && this.values[next] > this.values[i])) {
this.swap(i, next);
lastSwapped = i;
} else {
this.highlight(i, next);
}
if (next === right) {
i = right = lastSwapped;
incr = -incr;
} else if (next === left) {
i = left = lastSwapped;
incr = -incr;
} else {
i = next;
}
}
};
SortAlgorithm.prototype.insertion = function insertionSort() {
for (var i = 1; i < this.size; i++) {
for (var k = i; 0 < k; k--) {
if (this.values[k - 1] > this.values[k]) {
this.swap(k - 1, k);
} else {
this.highlight(k - 1, k);
break;
}
}
}
};
SortAlgorithm.prototype.shell = function shellSort() {
var gap = 1;
while (gap < this.size) {
gap = gap * 3 + 1;
}
while (1 < gap) {
gap = gap / 3 | 0;
for (var i = gap; i < this.size; i++) {
for (var k = i; 0 < k; k -= gap) {
if (this.values[k - gap] > this.values[k]) {
this.swap(k - gap, k);
} else {
this.highlight(k - gap, k);
break;
}
}
}
}
};
SortAlgorithm.prototype.merge = function mergeSort() {
this.mergeSortImpl(0, this.size - 1);
};
SortAlgorithm.prototype.mergeSortImpl = function(left, right) {
if (right <= left) {
return;
}
var middle = (left + right) / 2 | 0;
this.mergeSortImpl(left, middle);
this.mergeSortImpl(middle + 1, right);
var l = left;
var m = middle + 1;
while (l < m && m <= right) {
this.highlight(l, m);
if (this.values[l] >= this.values[m]) {
this.insert(m, l);
m++;
}
l++;
}
};
SortAlgorithm.prototype.quick = function quickSort() {
this.quickSortImpl(0, this.size - 1);
};
SortAlgorithm.prototype.quickSortImpl = function(left, right) {
var values = this.values;
var middle = (left + right) / 2 | 0;
var pivot = helper.median3(values[left], values[middle], values[right]);
var l = left;
var r = right;
while (true) {
while (values[l] < pivot) {
this.highlight(l, r);
l++;
}
while (pivot < values[r]) {
this.highlight(l, r);
r--;
}
if (r <= l) {
break;
}
this.swap(l, r);
l++;
r--;
}
if (left < l - 1) {
this.quickSortImpl(left, l - 1);
}
if (r + 1 < right) {
this.quickSortImpl(r + 1, right);
}
};
SortAlgorithm.prototype.heap = function heapSort() {
for (var i = 0; i < this.size; i++) {
this.swapUp(i);
}
for ( i = this.size - 1; 0 < i; i--) {
if (this.values[0] > this.values[i]) {
this.swap(0, i);
} else {
this.highlight(0, i);
}
this.swapDown(0, i);
}
};
SortAlgorithm.prototype.swapUp = function(cur) {
var parent;
while (cur !== 0) {
parent = (cur - 1) / 2 | 0;
if (this.values[parent] >= this.values[cur]) {
this.highlight(parent, cur);
break;
}
this.swap(parent, cur);
cur = parent;
}
};
SortAlgorithm.prototype.swapDown = function(cur, length) {
var values = this.values;
var child;
while (true) {
child = cur * 2 + 1;
if (values[child] < values[child + 1]) {
child += 1;
}
if (values[cur] >= values[child]) {
this.highlight(cur, child);
break;
}
if (length <= child) {
break;
}
this.swap(cur, child);
cur = child;
}
};
SortAlgorithm.prototype.bogo = function bogoSort() {
for (var i = 0; i < this.size; i++) {
var rnd = (Math.random() * (this.size - i) | 0) + i;
this.swap(i, rnd);
}
for ( i = 0; i < this.size - 1; i++) {
this.highlight(i, i + 1);
if (this.values[i] > this.values[i + 1]) {
return;
}
}
this.finished = true;
};
function ViewModel() {
this.algorithm = ko.observable('Bubble');
this.size = ko.observable(50);
this.speed = ko.observable(9);
this.sort = null;
this.nums = [];
this.algorithmList = ['Bubble', 'Selection', 'Shaker', 'Insertion', 'Shell', 'Merge', 'Heap', 'Quick', 'Bogo'];
this.sizeList = [5, 10, 50, 100, 150];
this.speedMin = 1;
// 2 seconds
this.speedMax = 22;
// 4 milliseconds
this.intervalId = -1;
graph.init(helper.getCanvas('graph-canvas'));
this.changed = ko.computed({
read : function() {
this.start(this.algorithm(), this.size());
},
owner : this,
deferEvaluation : true,
});
}
ViewModel.prototype.start = function(algorithm, size) {
var vm = this;
this.nums = helper.range(1, size + 1);
helper.shuffle(this.nums);
this.sort = new SortAlgorithm(this.nums.slice());
clearInterval(this.intervalId);
this.intervalId = setTimeout(animationFrame, 0);
function animationFrame() {
if (vm.sort.steps.length === 0) {
if (vm.sort.finished) {
graph.draw([-1, -1], vm.nums);
return;
} else {
vm.sort.sort(algorithm.toLowerCase());
console.log(vm.sort.steps.length);
}
}
var step = vm.sort.steps.pop();
step.run(vm.nums);
graph.draw(step.indexes, vm.nums);
vm.intervalId = setTimeout(animationFrame, vm.getIntervalTime());
}
};
ViewModel.prototype.restart = function() {
this.start(this.algorithm.peek(), this.size.peek());
};
ViewModel.prototype.getIntervalTime = function() {
var speed = parseInt(this.speed.peek(), 10);
return 2000 / speed / speed | 0;
};
if (document.documentElement.hasAttribute('sort-visualize-app')) {
document.addEventListener('DOMContentLoaded', main);
}
function main() {
var vm = window.vm = new ViewModel();
ko.applyBindings(vm);
vm.changed();
}
</script>
</body>
</html>
相关推荐
绝对是好东西 如果你刚好找这方面的资料要实现点击表头就产生排序，绝对实用,物超所值 轻量级JavaScript表格内容排序代码 对生产的html进行排序，不需要与数据库交互，速度性能好
冒泡排序可谓是最经典的排序算法了，它是基于比较的排序算法，时间复杂度为O(n^2)，其优点是实现简单，n较小时性能较好。 1）算法原理 相邻的数据进行两两比较，小数放在前面，大数放在后面，这样一趟下来，最小...
中各种算法的实现。 所有问题都有单元测试覆盖。 为什么是 JavaScript？ 它是我目前最强大的语言，考虑到 V8 取得的令人印象深刻的进步，我认为 Javascript 拥有美好的未来。 另外我有时有点懒惰，只想打字 :face_...
1.3条件比较字符串 1.4在字符串中查找子字符串 1.5从一个字符串提取子字符串 1.6检查一个存在的、非空的字符串 1.7将一个关键字字符串分解为单独的关键字 1.8插入特殊字符 1.9处理textarea的单个行 ...
我允许用户通过不同的提示和速度控制来可视化算法如何执行排序，同时还可以方便地计算每个算法进行的比较和交换次数，以此作为性能的客观比较。 我使用ReactJS，NPM和Bootstrap来帮助我开发此应用程序，这些应用...
乍一看，这似乎与Javascript的sort实现相同，但是当插入多个值时，它具有相当大的性能差异，如下面的基准测试所示。 如果要插入一个较大的排序列表中，但不一定要一次全部插入，那么与每次添加元素（甚至添加多个...
Javascript 高性能之递归，迭代，查表法详解 ...递归实现排序 /* 排序且合并数组 */ function myMerge(left, right) { // 保存最后结果的数组 var res = []; // 有一个数组结束了就结束排序，一
二进制堆基准多种语言的二进制堆排序实现的集合，主要用于比较语言之间的性能结果程序已在上执行，该程序在Windows 7 64位上使用Intel:registered:Core:trade_mark:i5-3470 CPU @ 3.20GHz。 您可以使用来运行代码。 ...
执行计划比较复杂的ＳＱＬ语句质量就不是很高 我们还可以结合时间统计【set statistics TIME ON..】一起使用,通过和时间统计结合使用可以更好地发挥执行计划的作用 有了执行计划和执行时间我们就很容易判断一条...
健壮性与高性能：Java通过垃圾回收机制确保内存的有效管理，同时也能通过JIT编译器优化来提升运行时性能。 标准库丰富：Java拥有庞大的类库，如Java SE（Java Standard Edition）包含基础API，用于开发通用应用程序...
Multiplex是JavaScript中.Net LINQ方法的一组数据结构和实现，可为JavaScript对象添加数据查询功能。 主要特点是： 完整的数据结构集： List -可以通过索引访问的对象的强类型列表。 Dictionary -键/值对的集合。...
3. 拖拽事件只要在排序模式激活下绑定，退出后/组件销毁后解绑，需要优化性能 Build Setup # install dependencies npm install # serve with hot reload at localhost:8080 npm run dev # build for production ...
20170307此目录下包含优先权的三种实现方式以及堆排序的源代码，你可以在看到我对优先所有权的解析，不过对于堆排序，可能是我实现的有问题，由于我一直对性能还尚不满意，所以还没有总结成博客，不过目前正在积极...
5 2.2 C#语言和Javascript脚本 6 2.2.1 C#语言 6 2.2.2 Javascript语言 6 2.3 IOCP框架简介 7 2.3.1 IOCP内部工作队列图 7 2.3.2 程序实现IOCP模型的基本步骤 8 2.3.3 使用IOCP模型和不使用IOCP模型通讯的对比 8 2.4...
组件内核借鉴虚拟Dom实现，元素排序移动借鉴React的Diff算法实现。使用简洁，组件轻量、性能高。 -- 功能清单 -- 头列固定 斑马纹 多级表头 排序 树形结构 单选 多选 开展动态行 体验 可直接访问 Usage 加载UI库 ...
它可以在任何 JavaScript Web 应用程序的前端或 NodeJS 应用程序中的服务器本身上实现，这当然提供了更高的性能。 该算法的计算量很大，需要时间来完成足够多的代以提供最佳解决方案，但结果是值得的。 要在前端...
业界提供了OAUTH的多种实现如PHP，JavaScript，Java，Ruby等各种语言开发包，大大节约了程序员的时间，因而OAUTH是简易的。目前互联网很多服务如Open API，很多大头公司如Google，Yahoo，Microsoft等都提供了OAUTH...
使用JavaScript实现隔行变色 使用jQuery选择器实现隔行变色 JavaScript代码检测页面元素 jQuery代码检测页面元素 使用jQuery基本选择器 使用jQuery层次选择器 使用jQuery基本过滤选择器 使用jQuery内容过滤...
合并排序大多数实现会产生稳定的排序，这意味着实现会保留排序后的输出中相等元素的输入顺序。 Mergesort是由John von Neumann于1945年发明的分而治之算法。插入排序插入排序是一种简单的排序算法，可以一次构建一个...
5.16.htm JavaScript实现阶乘函数 5.17.htm 全局变量和局部变量的区别 5.18.htm 变量实例 5.19.htm 在函数内部使用arguments 5.20.htm 创建并使用动态函数的例子 5.21....