数据排序谁最快(javascript中的Array.prototype.sort PK 快速排序)

但是让我感到意外的是,下面有个网友回复说,javascript中的Array本身的sort方法才是最快的,比快速排序算法都快,当时看到了很是郁闷,因为当时花了好长时间在排序算法上,居然忘记了Array本身的sort方法
不过javascript中内置的sort方法真的比快速排序算法还快吗?
哈哈,测试一下不就知道了
先说一下我测试的环境
1,我的测试环境是IE6.0和firefox2.0
2,每种算法有很多种不同的实现方法,下面测试中我选择上面网友实现的快速排序算法,只是把内嵌函数搬到了外面
3,算法执行的速度与数据的类型、大小、数据量的多少都有关系,我这里只比较 小于 999999 的整数的排序,数据量分别定为500、2000、30000

关于sort方法:sort方法是Array的一个内置的方法:javascript权威指南 中是这样定义的:

The sort( ) method sorts the elements of array in place: no copy of the array is made. If sort( ) is called with no arguments, the elements of the array are arranged in alphabetical order (more precisely, the order determined by the character encoding). To do this, elements are first converted to strings, if necessary, so that they can be compared.
If you want to sort the array elements in some other order, you must supply a comparison function that compares two values and returns a number indicating their relative order. The comparison function should take two arguments, a and b, and should return one of the following:

sort方法可以接受一个function类型的参数来自定义自己的排序逻辑,当没有提供参数的时候,默认按照字符顺序排序,所以对整数排序需要提供一个function类型的参数,本测试的调用方式如下:

array.sort(function(a,b){return a-b})

当然如果要排序的整数位数相同,不提供参数返回的结果也是一样的,测试一下就知道:


代码如下:

<script>
alert( [3,4,5,11,1].sort())
alert([3,4,5,11,1].sort(function(a,b){return a-b}))
</script>

提示:可以先修改了再运行
得到的结果是 [1, 11, 3, 4, 5],显然不是我们要的结果
生成需要排序的数组,为了得到公正的结果我先随机生成用于排序的数组,每次比较中两种方法使用的数组都具有相同的元素,下面是生成随机数组的代码


代码如下:

function random(m,n){
//生成一个m、n之间的整数
var i=Math.random();
return Math.round((n-m)*i+m);
}

function getRandomArr(m,n,l){
//m:生成随即整数的最小值,n:生成随即整数的最大值,l:生成的数组的长度
var resultArr=[];
for(var i=0;i<l;i++){
resultArr.push(random(m,n))
}
return resultArr;
}

快速排序算法的实现,这个算法取自我看到的51js论坛上这个网友的实现,代码如下:


代码如下:

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;
}

Array.prototype.quickSort=function(){
doSort(this,0,this.length-1);
}

检查结果是否正确使用array.join()来判断, 性能测试代码如下:


代码如下:

function sortIntF(a,b){return a-b}
function pk(num){
//num: 用于排序的数组的元素个数
//生成用于排序的数组
var arr=getRandomArr(1,999999,num);
//当元素个数小于10000时,执行n次取平均值
var n=Math.ceil(10000/num);
//生成多个用于排序的数组的拷贝
var quickSortArrs=[];
var sortArrs=[];
for(var i=0;i<n;i++){
quickSortArrs.push(arr.slice(0));
sortArrs.push(arr.slice(0));
}
var t1=new Date();
for(var i=0;i<n;i++){
quickSortArrs[i].quickSort();
}
var t2=new Date();
for(var i=0;i<n;i++){
sortArrs[i].sort(sortIntF);
}
var t3=new Date();
alert("性能比较,对于"+num+"个元素的数组,平均每次排序花费时间如下:\n"
+"Array.prototype.sort:"+((t3-t2)/n)+"ms\n"
+"quickSort:"+((t2-t1)/n)+"ms\n"
);
alert("排序结果是否正确:"+(sortArrs[0].join()==quickSortArrs[0].join()));
}

直接调用pk函数就可以了,例如你要对300个元素的数组进行排序性能比较,调用pk(300) 就可以了

完整的测试代码如下:

function rand(m,n){
//生成一个m、n之间的整数
var i=Math.random();
return Math.round((n-m)*i+m);
}

function getRandomArr(m,n,l){
//m:生成随即整数的最小值,n:生成随即整数的最大值,l:生成的数组的长度
var resultArr=[];
for(var i=0;itemp);
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 doSort(a,s,e)
{
if(s

[Ctrl+A 全选 注:如需引入外部Js需刷新才能执行]

测试结果
第一次 第一次 第一次(ms)
500个元素: ie6.0: sort: 38.3 39.05 39.05
quickSort: 8.6 8.6 9.4
ff2.0: sort: 3.1 3.15 3.9
quickSort: 4.7 4.7 3.15

2000个元素: ie6.0: sort: 200 203.2 203
quickSort: 40.6 43.6 43.8
ff2.0: sort: 18.8 18.6 18.8
quickSort: 18.6 15.6 15.6

30000个元素: ie6.0: sort: 10360 9765 9203
quickSort: 843 813 891
ff2.0: sort: 422 422 406
quickSort: 328 297 407
从结果中可以看到,
在ie6.0中快速排序算法比Array对象的sort方法快多了,对于元素比较少的,快速排序的速度基本上是sort方法的5倍左右,对于30000个元素快速排序是sort方法速度的十几倍
在ff2.0中两种排序算法速度基本上差不多,快速排序算法稍微快一点,这也说明ff2.0中Array对象的sort还是比较高效的,说不定就是用的快速排序,因为它跟快速排序算法的数据很接近
说明:上面的测试只代表我本机上的测试结果,也许在你机器上结果会有很大的区别,希望大家也帮忙测试一下

(0)

相关推荐

  • 快速排序 php与javascript的不同之处

    1. PHP 复制代码 代码如下: <?php $unsorted = array(2,4,5,63,4,5,63,2,4,43); function quicksort($array) { if (count($array) == 0) return array(); $pivot = $array[0]; $left = $right = array(); for ($i = 1; $i < count($array); $i++) { if ($array[$i] < $pivot

  • JS排序之快速排序详解

    本文为大家分享了JS快速排序的具体代码,供大家参考,具体内容如下 说明 时间复杂度指的是一个算法执行所耗费的时间 空间复杂度指运行完一个程序所需内存的大小 稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面 不稳定指,如果a=b,a在b的前面,排序后可能会交换位置 --JS快速排序-- 原理 从数组中选定一个基数,然后把数组中的每一项与此基数做比较,小的放入一个新数组,大的放入另外一个新数组.然后再采用这样的方法操作新数组.直到所有子集只剩下一个元素,排序完成. 时间复杂度,空间复杂度,稳

  • js快速排序的实现代码

    但是有不少的书本讲得并不是很清楚,而且不同的教材的实现方式也不尽相同,我这里将最简单的快速排序的思路写出来供大家参考. 希望不管是使用什么语言都能从这个简单的代码里很方便的掌握快排思路与编写方式 复制代码 代码如下: function quick_sort(list, start, end) {        if (start < end) {          var pivotpos = partition(list, start, end);   //找出快排的基数          q

  • js对象数组按属性快速排序

    按所推荐的程序在IE下跑了下,的确,排序耗时很小. 复制代码 代码如下: <script> /* * 洗牌 */ function getRandomPlayCard(m){ var array1=new Array(m); for(var i=0;i<m;i++){ var rnd=Math.floor(Math.random()*(i+0.99999)) array1[i]=array1[rnd]; array1[rnd]=i; } return array1; }; /* * 快速

  • JavaScript实现快速排序(自已编写)

    简述: 用到javascript的排序一组数字,js没有直接的数字比较的函数可以调用,所以自己写了一个快速排序 知识点: 1. 正则表达式提取正负数字的string 2. str 转数字 放回列表 3. js的对象Sort类的声明及定义 4. Sort类构造函数.成员函数定义方式(prototype) 5. 快速排序算法 代码: 复制代码 代码如下: <!DOCTYPE html> <meta http-equiv="Content-Type" content=&qu

  • JS实现随机化快速排序的实例代码

    算法的平均时间复杂度为O(nlogn).但是当输入是已经排序的数组或几乎排好序的输入,时间复杂度却为O(n^2).为解决这一问题并保证平均时间复杂度为O(nlogn)的方法是引入预处理步骤,它惟一的目的是改变元素的顺序使之随机排序.这种预处理步骤可在O(n)时间内运行.能够起到同样作用的另一种简单方法是在算法中引入一个随机元素,这可以通过随机地选择拆分元素的主元来实现.随机选择主元的结果放宽了关于输入元素的所有排列的可能性相同的步骤.引入这一步来修正原先的快速排序,可得到下面所示的随机化快速排序

  • JS实现冒泡排序,插入排序和快速排序并排序输出

    在一次面试中被问到了此问题,但是真是懵了,没能回答上来,后来通过JS整理了一下,在结合html代码做了一个文本框,把输入的内容从文本框排序输出,再次不做叙述了,下面通过一段代码给大家展示下: 以下是代码: index.html <!DOCTYPE html> <html> <head> <title>Sorting</title> <link rel="stylesheet" type="text/css&qu

  • javascript 快速排序函数代码

    核心代码: 复制代码 代码如下: function quickSort(arr){ //如果数组只有一个数,就直接返回: if(arr.length<1){ return arr; } //找到中间的那个数的索引值:如果是浮点数,就向下取整 var centerIndex = Math.floor(arr.length/2); //根据这个中间的数的索引值,找到这个数的值: var centerNum = arr.splice(centerIndex,1); //存放左边的数 var arrLe

  • JavaScript快速排序

    function quickSort() { function doSort(a,s,e) { if(stemp); if(s>e)break; var tem=a[s]; a[s]=a[e]; a[e]=tem; } a[st]=a[e]; a[e]=temp; return e; } doSort(this,0,this.length-1); return this; } Array.prototype.quickSort=quickSort; alert(new Array(5,2,4,6

  • 数据排序谁最快(javascript中的Array.prototype.sort PK 快速排序)

    但是让我感到意外的是,下面有个网友回复说,javascript中的Array本身的sort方法才是最快的,比快速排序算法都快,当时看到了很是郁闷,因为当时花了好长时间在排序算法上,居然忘记了Array本身的sort方法 不过javascript中内置的sort方法真的比快速排序算法还快吗? 哈哈,测试一下不就知道了 先说一下我测试的环境 1,我的测试环境是IE6.0和firefox2.0 2,每种算法有很多种不同的实现方法,下面测试中我选择上面网友实现的快速排序算法,只是把内嵌函数搬到了外面 3

  • JavaScript中的Array 对象(数组对象)

     1.创建Array对象方法: --->var arr = [1,2,3];//简单的定义方法 此时可以知道 arr[0] == 1; arr[1] == 2; arr[2] == 3; --->new Array(); var arr = new Array();//定义一个没有任何内容的数组对象,然后以下面的方式为其赋值 arr[0] = "arr0"; arr[1] = "arr1"; arr[2] = "arr2"; ---&

  • javascript 中关于array的常用方法详解

    javascript 中关于array的常用方法 最近总结了一些关于array中的常用方法, 其中大部分的方法来自于<JavaScript框架设计>这本书, 如果有更好的方法,或者有关于string的别的常用的方法,希望大家不吝赐教. 第一部分 数组去重,总结了一些数组去重的方法,代码如下: /** * 去重操作,有序状态 * @param target * @returns {Array} */ function unique(target) { let result = []; loop:

  • javascript学习笔记(九)javascript中的原型(prototype)及原型链的继承方式

    在使用面向对象编程时,对象间的继承关系自然少不了!而原型正是实现javascript继承的很重要的一种方法! 我们首先来看以下代码: 复制代码 代码如下: function person(name, age) { this.name = name; this.age = age; } person.prototype.getInfo = function() { alert("My name is "+this.name+", and I have "+this.a

  • javascript 中__proto__和prototype详解

    __proto__是内部原型,prototype是构造器原型(构造器其实就是函数) 构造器的原型(prototype)是一个对象 那什么是构造器呢? 要想创建一个对象,首先要有一个对象构造器,就像php里面一样,要想创建一个对象,首先要有一个类 构造器的实质就是一个函数,下面的问题是:如何通过这个构造器来创建一个对象呢? 答案: new 构造器构造的是对象. 一.所有构造器/函数的__proto__都指向Function.prototype,它是一个空函数(Empty function) 复制代

  • JavaScript中利用Array和Object实现Map的方法

    本文实例讲述了JavaScript中利用Array和Object实现Map的方法.分享给大家供大家参考.具体如下: 昨天突然看到以前别人用JavaScript实现的Map感觉很不错,但是发现有个别方法有问题,顺便完善了下,添加了 remove .indexOf .values.clear等方法. /** * @author blune68 * @version 0.1, 07/27/12 * */ function Map(){ this.keys = new Array(); this.dat

  • JavaScript中利用Array filter() 方法压缩稀疏数组

    什么是稀疏数组 数组元素的索引不一定要连续的,它们之间可以有空缺.每个javaScript数组都有一个length属性.针对非稀疏数组,该属性就是数组元素的个数:针对稀疏数组,length比所有元素的个数要大. Array filter() 方法会跳过稀疏数组中缺少的元素,它的返回数组总是稠密的. (1)压缩稀疏数组的空缺: var dense = sparse.filter( function(currentValue) { return true; } ); (2)压缩稀疏数组的空缺,并且删

  • js使用Array.prototype.sort()对数组对象排序的方法

    本文实例讲述了js使用Array.prototype.sort()对数组对象排序的方法.分享给大家供大家参考.具体分析如下: 在讲对数组对象进行排序时,我们先来简单的了解一下Array.prototype.sort().sort方法接受一个参数--Function,function会提供两个参数,分别是两个进行比较的元素,如果元素是String类型则通过Unicode code进行比较,如果是Number类型则比较值的大小.如果比较的函数中返回1则两个元素交换位置,0和-1不交换位置.先看一个例

  • JavaScript中数组Array.sort()排序方法详解

    JavaScript中数组的sort()方法主要用于对数组的元素进行排序.其中,sort()方法有一个可选参数.但是,此参数必须是函数. 数组在调用sort()方法时,如果没有传参将按字母顺序(字符编码顺序)对数组中的元素进行排序,如果想按照其他标准进行排序,就需要进行传一个参数且为函数,该函数要比较两个值,并且会返回一个用于说明这两个值的相对顺序的数字. 1.对数字数组进行由小到大的顺序进行排序. 代码: var arr = [22,12,3,43,56,47,4]; arr.sort();

  • JavaScript中的Array对象使用说明

    说它是一个动态数组,是因为动态的添加数据: 复制代码 代码如下: var myarr = new Array(); myarr[0] = 1; myarr[1] = 2; myarr[2] = 3; myarr[3] = 23; myarr[4] = 11; 使用for进行遍历: 说它是一个字典对象,是因为他可以以键值的形式进行访问: 复制代码 代码如下: var dictionary = new Array(); dictionary["谢龙宝"] = "xielongba

随机推荐