Array.sort(customSortFunction:Function)隐藏的陷阱

发表评论 阅读评论

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
AS3中的Array.sort就是实现排序的工具,它有多种用法,不过使用自定义排序函数时需要注意。 为了更容易的理解下面问题,先弄明白一个排序算法相关的概念:稳定性。
稳定排序:假设在待排序的元素中,存在两个或两个以上的记录具有相同的关键字(或值),在用某种排序法排序后,若这些相同关键字(或值)的元素的相对次序仍然不变,则这种排序方法是稳定的。 而我们下面的代码跟稳定性无关的,因为不存在相同的元素。

通常我们会写以下“错误代码”:

var a:Array = [3.3,2.4,1.5,0];
a.sort(fun);
trace(a);
function fun(a:Number, b:Number):Number
{
    return a-b;
}

排序结果为:

0,2.4,1.5,3.3

我们再来看看另一种方式(注意对返回结果进行了取整操作):

var a:Array = [3.3,2.4,1.5,0];
a.sort(fun);
trace(a);
function fun(a:Number, b:Number):Number
{
    return int(a-b);
}

大家都知道Array.sort是冒泡排序,是根据前(<0)、后(>0)、当前(==0)这3种状态来排的。
但是这里的自定义排序函数的返回值会自动取整(int(returnValue))。 如果结果为(0,1), (-1,0) 注意为开区间,那么自动转换为整数后为0,进而不进行排序,然后运行结果将与我们想要的不一致。

其实第一种自定义排序函数并没有错,只是它只适用于要排序的值都是整数或者每两个值相差不小于1(可以为0)。 安全的排序函数为:

function fun(a:Number, b:Number):Number
{
    if(a>b) return 1;
    else if(a<b) return -1;
    return 0;
}

排序结果为:

0,1.5,2.4,3.3

其实这也算是Array.sort的一个bug了,我找文档没有提到说自定义排序函数返回值会自动取整。

  1. | |

    oaiy6e不知道为啥留言都要审核 哎

  2. | |

    @喜梦宝
    因为有垃圾评论,所以要审核的

  3. | |

    你的blog不错,我要把每篇blog文都保存下来,哈哈

  4. |

    不会有垃圾评论的吧,进来的都是技术人员,呵呵....
    你博客真不错,技术牛人,崇拜中...

  5. | |

    我也试过这种情况,是由于在排序时,读取到相同的对象引起的.如果加上if(a == b){print("xxx");}调试下就知道了.在.net的Array.Sort排序中会出现异常(不返回0).在mono的c#下会出现你这种情况.

  6. | |

    @godzza
    不是的,你没理解我描述的问题,我是说sort会对自定义排序函数的返回值取整,也就是说当两个值相差的绝对值小于1时,排序会出问题。

  1. 本文目前尚无任何 trackbacks 和 pingbacks.
回到顶部