V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
CoooolChan
V2EX  ›  JavaScript

最近在学习JS,数组里有个方法sort()用来排序的,然后它可以有一个比较函数作为参数,我对于如何调用这个比较函数很困惑,书上只是简单说通过返回-1,0,1来确定升降排序,那内部的机制是什么样的,它用的什么排序方法

  •  
  •   CoooolChan · 2013-07-10 22:30:54 +08:00 · 5877 次点击
    这是一个创建于 4145 天前的主题,其中的信息可能已经有所发展或是发生改变。
    11 条回复    1970-01-01 08:00:00 +08:00
    sNullp
        1
    sNullp  
       2013-07-10 22:50:47 +08:00
    我猜是快排
    timonwong
        2
    timonwong  
       2013-07-10 23:17:56 +08:00
    排序算法跟实现有关。v8对于小数组用了简单的排序算法,是稳定排序。其它数组用的quicksort
    Firefox早期用quicksort, 现在用mergesort
    CoooolChan
        3
    CoooolChan  
    OP
       2013-07-10 23:41:37 +08:00
    @timonwong 你屌爆了
    Golevka
        4
    Golevka  
       2013-07-11 08:57:58 +08:00
    基于比较的排序算法不都是这样的么? 只要任意给两个元素a,b, 你能确定a>b还是a<b; 并且对于a<b, b<c, 总有a<c, 你就能用基于比较的排序算法对序列进行排序
    maxiujun
        5
    maxiujun  
       2013-07-11 10:09:34 +08:00
    v8的实现里面对length<=22的使用的是插入排序(稳定), 对于大于22的使用的是快速排序(非稳定),
    可以参考: http://v8.googlecode.com/svn/trunk/src/array.js
    hooluupog
        6
    hooluupog  
       2013-07-11 10:39:28 +08:00
    我见过的一般是改进的快排,里面对递归的深度会有判断,当出现或即将出现快排最坏的情况时(O(n^2)),会转为堆排序。python和Go以及c++ stl有源码可以参考。
    timonwong
        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
    hooluupog
        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
    sivacohan
        9
    sivacohan  
       2013-07-11 13:35:23 +08:00
    js的sort是错误。那个是基于字符串的比较

    1 11 111 2 20 21

    你可以尝试比较一下这个。
    otakustay
        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.

    标准就规定了要把数组中每个转成字符串再比较,因此无论如何这不能算是“错误”,从来没有人说数字组成的数组排序一定要按数字大小来吧?
    guchengf
        11
    guchengf  
       2013-07-12 07:12:02 +08:00
    @sivacohan 正解,如果需要比较数值大小,还得有个比大小函数作为参数
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1272 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 18:11 · PVG 02:11 · LAX 10:11 · JFK 13:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.