Javascript写了几个常见排序算法,算是回忆一下基本的算法,工作中用的很少了,都习惯类用现成的类库。
quick_sort2是网上实现的版本,我的quick_sort是看优酷的视频写的,老外还蛮有意思的,跳舞来解释算法。有兴趣的同学可以看看下面的视频:舞动的排序算法
我写的快速排序用递归的,用firefox,100万能排,但用其他浏览器就栈溢出了,不知道怎么能改进下。
js内置的排序算法效率果然很高。
后来又用一个画图的js库,画了一个算法性能比较的图,由图可以看出简单的排序算法在2000个元素的排序也非常快,快速排序只是在较多数量时优势才会显示出来。
Chrome运行的截图:
所有算法
后三种算法
源码
sort.js
function gen_random_numbers(numbers, count) {
for ( var i = 0; i < count; ++i) {
numbers[i] = Math.round(Math.random() * 10000);
}
}
function insert_sort(numbers) {
var count = numbers.length;
for ( var i = 0; i < count; ++i) {
for ( var j = i; j < count; ++j) {
if (numbers[i] > numbers[j]) {
swap(numbers, i, j);
}
}
}
}
function bubble_sort(numbers) {
var count = numbers.length;
for ( var i = 0; i < count; ++i) {
for ( var j = 0; j < count - 1; ++j) {
if (numbers[j] > numbers[j + 1]) {
swap(numbers, j, j + 1);
}
}
}
}
function select_sort(numbers) {
var count = numbers.length;
for ( var i = 0; i < count; ++i) {
var minIndex = i;
for ( var j = i + 1; j < count; ++j) {
if (numbers[minIndex] > numbers[j]) {
minIndex = j;
}
}
swap(numbers, minIndex, i);
}
}
function doSort(a, s, e) {
if (s < e) {
var pos = partition(a, s, e);
doSort(a, s, pos - 1);
doSort(a, pos + 1, e);
}
}
function partition(a, st, en) {
var s = st;
var e = en + 1;
var temp = a[s];
while (1) {
while (a[++s] < temp)
;
while (a[--e] > temp)
;
if (s > e)
break;
var tem = a[s];
a[s] = a[e];
a[e] = tem;
}
a[st] = a[e];
a[e] = temp;
return e;
}
function quick_sort2(numbers) {
doSort(numbers, 0, numbers.length - 1);
}
function quick_sort(numbers) {
do_quick_sort(numbers, 0, numbers.length);
}
function do_quick_sort(numbers, l, r) {
var p = l;
var i = r - 1;
while (i != p) {
while (numbers[p] <= numbers[i] && i > p)
i--;
if (i > p) {
swap(numbers, p, i);
var t = p;
p = i;
i = t;
}
while (numbers[p] >= numbers[i] && i < p)
i++;
if (i < p) {
swap(numbers, p, i);
var t = p;
p = i;
i = t;
}
}
if (p - l > 1) {
do_quick_sort(numbers, l, p);
}
if (r - p > 1) {
do_quick_sort(numbers, p + 1, r);
}
}
function check(numbers) {
var count = numbers.length;
for ( var i = 0; i < count - 1; ++i) {
for ( var j = i + 1; j < count; ++j) {
if (numbers[i] > numbers[j]) {
alert("error at" + i);
return;
}
}
}
}
function swap(numbers, i, j) {
var tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
function main() {
var count = 20;
var numbers = [];
gen_random_numbers(numbers, count);
document.write('initail random array: <br />');
document.write(numbers.toString());
var begin = new Date();
insert_sort(numbers);
bubble_sort(numbers);
select_sort(numbers);
quick_sort2(numbers);
check(numbers);
var end = new Date();
document.write('<br />');
document.write('sorted array: <br />');
document.write(numbers.toString());
var execSec = (end.getTime() - begin.getTime()) / 1000;
document.write("use time: " + execSec + "secs");
}
sort.htm
<html>
<head>
<!--[if lt IE 9]><script language="javascript" type="text/javascript" src="excanvas.js"></script><![endif]-->
<script language="javascript" type="text/javascript" src="/js/jquery/jquery.min.js"></script>
<script language="javascript" type="text/javascript" src="/js/jqplot/jquery.jqplot.min.js"></script>
<script language="javascript" type="text/javascript" src="/js/jqplot/plugins/jqplot.highlighter.min.js"></script>
<link rel="stylesheet" type="text/css" href="/css/jquery.jqplot.css" />
<script language="javascript" type="text/javascript" src="/js/alg/sort.js"></script>
</head>
<body>
<div id="chartdiv" style="height:600px;width:400px; "></div>
<script language="javascript" type="text/javascript">
$(document).ready(function() {
var numbers = [];
var MAX_EXEC_COUNT = 1;
var counts = [100, 300, 500, 800, 1000, 2000, 3000, 5000, 10000, 20000];
var sortAlgs = [insert_sort, bubble_sort, select_sort, quick_sort, quick_sort2, -1];
var statData = [];
var j = 0;
for (var i = 0; i < sortAlgs.length; ++i) {
statData[i] = [];
for (var j = 0; j < counts.length; ++j) {
numbers = [];
gen_random_numbers(numbers, counts[j]);
var sum = 0;
for (var k = 0; k < MAX_EXEC_COUNT; ++k) {
if (-1 == sortAlgs[i]) {
var begin = new Date();
numbers.sort();
sum += new Date().getTime() - begin.getTime();
} else {
var begin = new Date();
sortAlgs[i].call(window, numbers);
sum += new Date().getTime() - begin.getTime();
}
}
statData[i].push([counts[j], sum / MAX_EXEC_COUNT]);
}
}
$.jqplot('chartdiv', statData,
{title:'Sort Algorithm Comparation',
axes : {
xaxis : {
min : 0,
tickOptions:{
formatString:'#%d'
}
},
yaxis:{
min:0,
tickOptions:{
formatString:'%dms'
}
}
},
series : [
{label : 'insert_sort'},
{label : 'bubble_sort'},
{label : 'select_sort'},
{label : 'quick_sort'},
{label : 'quick_sort2'},
{label : 'array.sort'},
],
legend : {show : true, location : 'nw'},
highlighter: {
show: true,
sizeAdjust: 7.5
}
});
});
</script>
</body>
</html>
- 大小: 42.2 KB
- 大小: 36.9 KB
分享到:
相关推荐
JavaScript 中常见排序算法详解
JavaScript中常见排序算法详解共19页.pdf.zip
JavaScript中常见排序算法详解共19页.pdf.zip
常见排序算法(JS版)
本文实例讲述了基于JavaScript实现的插入排序算法。分享给大家供大家参考,具体如下: 根据排序过程中使用的存储器不同,可以将排序方法分为两大类:内部排序和外部排序。 内部排序是指待排序记录存放在计算机随机...
对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同...
用JavaScript实现的常见排序算法和数据结构的交互式概述。 还包括其他一些算法挑战,类似于编程采访中提出的挑战。 这旨在帮助您在准备面试时掌握计算机科学的基础知识,算法和解决问题的技能! 这仅作为参考/评论-...
用JavaScript实现的常见排序算法:冒泡排序,选择排序,插入排序,谢尔排序,快速排序(递归),快速排序(堆栈),归并排序,堆排序。
十大经典排序算法 (1)多种编程语言,JavaScript,python,go,php等语言。 (2)排序算法可以分为内部排序...常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序
笔耕不缀,持续学习 网站 2021 2020 2019 vdom 原理解析与简单实现 ...JavaScript 实现常见排序算法 JavaScript 实现常用设计模式 其他笔记 bash 脚本编程 python 学习笔记 Too young, too simple. Sometimes, naive.
因为javascript array 之sort 经过脚本引擎优化,性能往往比自己写的好。
JavaScript实现的常见排序算法有:冒泡排序,选择排序,插入排序,谢尔排序,快速排序(递归),快速排序(堆栈),归并排序,堆排序。今天我们来详细分析下快速排序算法
JavaScript中几种常见排序算法小结,学习js的朋友可以参考下,下面对多种方法进行了简单的小结。
我决定为一些常见的排序算法实现一个可视化工具,同时还学习Web应用程序编程。 我允许用户通过不同的提示和速度控制来可视化算法如何执行排序,同时还可以方便地计算每个算法进行的比较和交换次数,以此作为性能的...
9-1 排序链表-原理讲解 9-2 排序链表-代码实操 9-3 环形链表-原理讲解 9-4 环形链表-代码实操第10章 数据结构之“矩阵”矩阵虽不常见,若见既是霹雳。看似和数组无异,操作起来如同嚼蜡。别怕,同样是数组API、递归...
开发中,遇到数组排序的需求很频繁,这篇文章会介绍几个常见排序思路。 一、希尔排序(性能最好) 如果要从大到小排列,则 while(arr[n] > arr[n – interval] && n > 0) 。 // 希尔排序算法 function xier(arr){ ...
不同的排序算法,执行效率有着天壤之别,本脚本用JavaScript演示了各种常见的排序算法,包括:冒泡排序、选择排序、插入排序、谢尔排序、快速排序(递归)、快速排序(堆栈)、归并排序、堆排序