<!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实现冒泡排序的关键在于两层循环结构，外层控制遍历次数，内层用于比较和交换。 2. 插入排序（Insertion ...
JavaScript 实现表格排序是网页开发中的常见需求，尤其在数据展示和管理中起到关键作用。在本项目"tiger-auntion-TableSort-测试交流版"中，我们看到一个简洁易用的表格排序功能。下面将详细讲解如何使用 JavaScript...
本教程将深入探讨如何使用JavaScript来实现排序二叉树。 一、基础知识 在开始之前，我们需要了解二叉树的基本概念。二叉树是由节点组成的，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的遍历...
在`jsSortCode.htm`文件中，你可以找到这些排序算法的具体JavaScript代码实现，通过阅读和实践这些代码，有助于深入理解和掌握每种排序算法的工作原理和性能特点。在实际开发中，结合算法的理论知识和实践经验，能够...
JavaScript表格排序大全是一个涵盖多种JS表格排序实现方法的资源集合，旨在帮助开发者快速实现动态、交互式的表格数据排序功能。在网页开发中，表格是一种常用的数据展示方式，而JavaScript能够为表格提供强大的交互...
在JavaScript中，对表格进行排序是一项常见的需求，特别是在构建交互式网页时。...在实际项目中，可以进一步优化这个算法，比如引入快速排序或归并排序，以提高大规模数据的排序性能，或者处理复杂的数据类型。
通过双层循环比较数组中的元素，并在需要的情况下交换它们的位置，从而实现排序。最后，排序完成的数组被返回。 选择排序在JavaScript中的实现则稍微复杂一些，因为它需要两层循环来完成。外层循环用于确定未排序...
总结以上知识点，我们可以看到使用JavaScript实现表格排序不仅涉及到算法的实现，还需要考虑与用户交互、性能优化、兼容性处理以及代码组织等多个方面。一个高效的、用户友好的排序功能能够显著提升网站或应用的用户...
在本主题中，我们将深入探讨如何利用jQuery和JavaScript实现拖拽排序功能，适用于列表、菜单和表格等元素。 一、拖拽排序基础概念 拖拽排序是一种用户交互设计，允许用户通过鼠标拖动来改变元素的顺序。这种功能在...
通过学习这份文档，我们可以深入理解自定义排序函数的工作原理，以及如何根据具体需求调整和优化排序逻辑，从而在实际项目中提高性能。 总结来说，JavaScript字符串排序涉及的关键知识点包括： 1. `Array.prototype...
首先，我们需要了解JavaScript中的数组方法，如`sort()`，这是实现排序的基础。`sort()`方法可以接受一个比较函数作为参数，根据这个函数返回值的正负决定元素的排列顺序。例如，我们可以定义一个比较函数来比较两个...
在这个"JavaScript-使用javascript开发的排序算法-sorting.zip"压缩包中，很可能是包含了各种常见的排序算法实现，比如冒泡排序、插入排序、选择排序、快速排序、归并排序以及堆排序等。 1. **冒泡排序**：冒泡排序...
在这个主题中，"易语言调用js实现各种排序速度对比源码"，我们关注的是如何在易语言中利用JavaScript（JS）引擎进行跨语言交互，以及比较不同排序算法的性能。 首先，易语言提供了与外部脚本语言交互的能力，包括...
本文将深入探讨如何使用JavaScript实现表格数据的排序功能。 首先，我们需要理解HTML表格的基本结构。一个HTML表格由`<table>`元素定义，其中包含`<tr>`（行）元素和`<td>`（单元格）元素。如果需要对表头进行排序...
在本文中，我们将深入探讨JavaScript实现表格排序的原理、方法以及相关的技术细节。 首先，我们要明白表格（Table）是HTML中用于展示结构化数据的重要元素，而JavaScript作为客户端脚本语言，可以对DOM（Document ...
总的来说，JavaScript中的`sort()`方法和`localeCompare()`函数是实现表格排序的关键工具，但需要配合自定义的比较函数和数据转换策略，以适应不同类型的表格数据。理解这些概念并正确应用它们，可以帮助我们构建出...
- 为了实现排序，可以遍历容器内的所有元素，比较它们与被拖动元素的相对位置，将被拖动元素插入到合适的位置，从而实现排序。 - 可以使用数组的`splice()`方法来实现元素的插入和删除，保持DOM结构与数据数组的...
在JavaScript中，我们可以通过内置的`Array.prototype.sort()`方法对数组进行排序，但默认的排序规则可能并不符合我们的需求，因此掌握各种排序算法有助于我们定制更高效的排序逻辑。 1. 冒泡排序（Bubble Sort）：...
这个功能强大的JavaScript库，被称为"sorttable"，能够帮助开发者轻松实现表格数据的排序，同时提供了自定义排序规则的能力，大大增强了用户体验。 首先，我们要理解sorttable的核心概念。在JavaScript中，排序通常...
下面我们将详细探讨如何用JavaScript实现这一功能。 首先，我们需要在HTML中创建一个表格，每个表头（thead）单元格（th）都应具有一个唯一的ID或者类名，以便后续JavaScript代码能够准确找到并绑定事件处理函数。...