`
jamie.wang
  • 浏览: 351154 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

Javascript实现常见排序算法

阅读更多

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 中常见排序算法详解.pdf

    JavaScript 中常见排序算法详解

    JavaScript中常见排序算法详解共19页.pdf.zip

    总的来说,"JavaScript中常见排序算法详解共19页.pdf.zip"这份资料会详细解析上述排序算法的实现过程、优缺点以及适用场景,对于提升JavaScript编程技能具有极大的价值。无论是初学者还是有经验的开发者,都应该深入...

    JavaScript中常见排序算法详解共19页.pdf.z

    在阅读“JavaScript中常见排序算法详解共19页.pdf”这份文档时,不仅要注意理解每种算法的原理,还要尝试动手实现,通过实践加深理解,并通过性能测试来比较不同算法的优劣。在学习过程中,还可以结合实际问题,如大...

    JavaScript实现表格排序

    总结起来,JavaScript实现表格排序涉及到对HTML表格数据的处理、排序算法的实现以及用户交互的设计。通过对数字、日期和汉字的排序处理,我们可以创建出功能完善的交互式表格,极大地提高了数据管理的效率。

    冒泡排序算法及其JavaScript实现详解.pdf

    本资源详细介绍了JavaScript中的冒泡排序算法,包括其基本原理、具体步骤和优化方法。通过一个具体的代码示例,展示了如何使用JavaScript实现冒泡排序,并解释了代码的关键部分。此外,还讨论了冒泡排序的时间复杂度...

    JavaScript-使用javascript开发的排序算法-sorting.zip

    在这个"JavaScript-使用javascript开发的排序算法-sorting.zip"压缩包中,很可能是包含了各种常见的排序算法实现,比如冒泡排序、插入排序、选择排序、快速排序、归并排序以及堆排序等。 1. **冒泡排序**:冒泡排序...

    javascript排序算法实现

    排序算法是计算机科学的基础,JavaScript中的排序算法实现可以帮助我们更高效地处理数组数据。本篇文章将详细探讨JavaScript中几种常见的排序算法及其实现。 1. **冒泡排序**: 冒泡排序是最基础的排序算法之一,...

    常见排序算法JS版

    本篇将深入探讨几种常见的排序算法,并以JavaScript实现为例,帮助你理解和掌握这些算法。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序算法之一,它通过不断地交换相邻的错误顺序元素来逐步排序数组。每一...

    基于javascript实现的一些常用算法

    1. **排序算法**:排序算法是计算机科学的基础,JavaScript中的常见排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。例如,冒泡排序是一种简单的排序方法,通过不断交换相邻的逆序元素来达到排序的...

    常见排序算法js版本

    标题"常见排序算法js版本"意味着我们将讨论如何用JavaScript实现常见的排序算法,这些算法可能包括但不限于: 1. **冒泡排序(Bubble Sort)**:通过不断交换相邻的不正确顺序元素来完成排序。时间复杂度为O(n^2),...

    通过实例解析JavaScript常用排序算法

    本文将深入探讨四种常见的排序算法:冒泡排序、快速排序、选择排序以及插入排序,并通过实例代码进行详细解析。 1. **冒泡排序**: 冒泡排序是最直观的排序算法之一,它通过重复遍历待排序的列表,比较每对相邻...

    基于javascript实现插入排序,希尔排序,简单选择排序,冒泡排序,快速排序

    本篇内容将深入探讨如何使用JavaScript语言实现五种常见的排序算法:插入排序、希尔排序、简单选择排序、冒泡排序和快速排序。 首先,插入排序的基本思想是将数组分为已排序和未排序两部分,然后逐渐将未排序部分的...

    常见排序算法pdf文档

    这篇文档主要介绍了十一种常见的排序算法,包括它们的原理、示例分析以及JavaScript语言的实现。以下是这些排序算法的详细说明: 1. **冒泡排序**(Bubble Sort):通过不断比较相邻元素并交换,使得小元素逐渐“浮...

    排序算法的实现与分析js

    此外,JavaScript中的排序算法实现还可以利用函数式编程范式来提高代码的可读性和可维护性。例如,可以使用高阶函数来抽象排序逻辑,或者采用回调函数来定义排序规则,从而使得排序函数更加通用和灵活。 总结而言,...

    javascript实现表格排序

    JavaScript 实现表格排序是网页开发中的常见需求...总结来说,JavaScript 实现表格排序涉及到了事件处理、数据排序算法、DOM 操作以及用户体验设计等多个方面。掌握这些技术可以帮助我们构建更加高效、易用的网页应用。

    javascript中可能用得到的全部的排序算法

    本文将深入探讨十多种常见的排序算法,包括它们的基本思想、优缺点以及在JavaScript中的实现。 首先,让我们从最基础的冒泡排序开始。 **冒泡排序**是一种简单的排序方法,它通过重复遍历数组,比较相邻元素并交换...

    常见排序算法总结,基于 JavaScript 实现.zip

    对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同...

    通过HTML、原生JS和CSS3动画,使用ES6语法演示常见排序算法(如选择排序、气泡排序、插入排序、合并排序等)的执行过程.z

    本项目通过结合HTML、原生JavaScript(JS)以及CSS3的动画效果,运用ES6语法,演示了数种常见排序算法的执行过程,帮助用户可视化理解排序算法的工作原理。 项目中演示的排序算法包括但不限于选择排序、冒泡排序、...

Global site tag (gtag.js) - Google Analytics