Javascript实现常见排序算法 -

jamie.wang

浏览: 348791 次
性别:
来自: 成都

最近访客更多访客>>

bobboy007

pearonly1a1a

天道有情战天下

taraapink1234

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

Javascript实现常见排序算法

博客分类：

算法

javascript algorithm 算法

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>