1
sNullp 2013-07-10 22:50:47 +08:00
我猜是快排
|
2
timonwong 2013-07-10 23:17:56 +08:00
排序算法跟实现有关。v8对于小数组用了简单的排序算法,是稳定排序。其它数组用的quicksort
Firefox早期用quicksort, 现在用mergesort |
3
CoooolChan OP @timonwong 你屌爆了
|
4
Golevka 2013-07-11 08:57:58 +08:00
基于比较的排序算法不都是这样的么? 只要任意给两个元素a,b, 你能确定a>b还是a<b; 并且对于a<b, b<c, 总有a<c, 你就能用基于比较的排序算法对序列进行排序
|
5
maxiujun 2013-07-11 10:09:34 +08:00
v8的实现里面对length<=22的使用的是插入排序(稳定), 对于大于22的使用的是快速排序(非稳定),
可以参考: http://v8.googlecode.com/svn/trunk/src/array.js |
6
hooluupog 2013-07-11 10:39:28 +08:00
我见过的一般是改进的快排,里面对递归的深度会有判断,当出现或即将出现快排最坏的情况时(O(n^2)),会转为堆排序。python和Go以及c++ stl有源码可以参考。
|
7
timonwong 2013-07-11 10:49:51 +08:00
@hooluupog
那种叫introsort吧,C++ STL上的 sort() 一般都是这种实现,稳定的 stable_sort() 还是用的 mergesort, 不过由于是实现相关的,不知道什么时候会变。 python 现在用 timsort (java现在也是,稳定排序,mergesort的一种) go/pkg/sort就是很明显的quicksort |
8
hooluupog 2013-07-11 12:32:08 +08:00 1
@timonwong Go 1.0是quicksort,1.1已经不是了,快排+堆排+插入 混合成的。http://golang.org/src/pkg/sort/sort.go
|
9
sivacohan 2013-07-11 13:35:23 +08:00
js的sort是错误。那个是基于字符串的比较
1 11 111 2 20 21 你可以尝试比较一下这个。 |
10
otakustay 2013-07-11 23:39:30 +08:00
@sivacohan ECMA262 V5关于sort的默认实现的原文在这里:
When the SortCompare abstract operation is called with two arguments j and k, the following steps are taken: Let jString be ToString(j). Let kString be ToString(k). Let hasj be the result of calling the [[HasProperty]] internal method of obj with argument jString. Let hask be the result of calling the [[HasProperty]] internal method of obj with argument kString. If hasj and hask are both false, then return +0. If hasj is false, then return 1. If hask is false, then return –1. Let x be the result of calling the [[Get]] internal method of obj with argument jString. Let y be the result of calling the [[Get]] internal method of obj with argument kString. If x and y are both undefined, return +0. If x is undefined, return 1. If y is undefined, return −1. If the argument comparefn is not undefined, then If IsCallable(comparefn) is false, throw a TypeError exception. Return the result of calling the [[Call]] internal method of comparefn passing undefined as the this value and with arguments x and y. Let xString be ToString(x). Let yString be ToString(y). If xString < yString, return −1. If xString > yString, return 1. Return +0. 标准就规定了要把数组中每个转成字符串再比较,因此无论如何这不能算是“错误”,从来没有人说数字组成的数组排序一定要按数字大小来吧? |