仔细看了下众多Arrays.sort的重载方法。
发现java在实现这些sort方法的时候,排序Object的时候都是用合并排序
排序primitive(int,float等原型数据)的时候用的是快速排序,为什么要
这样呢,不是说快速排序是最好的吗?为什么都不用快速排序排呢?

解决方案 »

  1.   

    object对象进行排序肯定是根据object对象的某个属性啊
      

  2.   

    快速排序和合并排序都可以对primitive和Object进行排序的好伐,
    不懂不要乱讲,误人子弟
      

  3.   


    同意:快速排序的时间复杂度最坏为n*(n-1)/2  最好为n*logn 
    合并排序的时间复杂度 nlgn 
      

  4.   

    一个因素是稳定,另一个因素是性能也能保证O(n*logn)
    个人理解,仅供参考.
      

  5.   

    LZ我想问你对object对象排序的时候是按照什么?人家说的哪不对,只不过没有答出你的问题罢了!
      

  6.   

    THE Java™ Programming Language, Fourth Edition
    sort Sorts an array into ascending order. The exact algorithm is not specified other than it must be stable for objects (that is, equal objects don't get reordered because of the sort). A good implementation would use a technique that is not worse than O(nlogn)
      

  7.   

    事实胜于雄辩,请默默关注本帖
    import java.util.Date;public class A implements Comparable { public int compareTo(Object arg0) {
    Date date = new Date();
    int second = date.getSeconds();
    if (second > 30) {
    return 1;
    } else if (second >= 0 && second <= 30) {
    return -1;
    }
    return 0;
    }
    }看看compareTo方法有没有调用啥你说的属性
      

  8.   

    SUN的The Java Tutorial也是强调两点: 
    The sort operation uses a slightly optimized merge sort algorithm that is fast and stable:    * Fast: It is guaranteed to run in n log(n) time and runs substantially faster on nearly sorted lists. Empirical tests showed it to be as fast as a highly optimized quicksort. A quicksort is generally considered to be faster than a merge sort but isn't stable and doesn't guarantee n log(n) performance.
        * Stable: It doesn't reorder equal elements. This is important if you sort the same list repeatedly on different attributes. If a user of a mail program sorts the inbox by mailing date and then sorts it by sender, the user naturally expects that the now-contiguous list of messages from a given sender will (still) be sorted by mailing date. This is guaranteed only if the second sort was stable. 归并排序既快速又稳定.
      

  9.   

    算法没有规定死,只要符合稳定性就可以了,时间复杂度不要超过O(nlogn).
      

  10.   

    呵呵,
    首先呢,虽然归并排序的时间复杂度是O(nlgN),但是它很难用于主存排序,主要问题在于合并两个排序的表
    需要线性附加内存,在整个算法中还要花费将数据复制到临时数组在复制回来的一些附加的操作。在java语言中
    ,当排序一般的对象时,元素的比较消耗时很多,但是移动元素就很快,所以呢,归并排序使用最少次数的比较
    因此,在java中归并排序是一般目的排序的最佳选择。

      

  11.   

    大家都提到了最坏情况,我觉得根本不是本帖讨论之根本所在,如下两数组:
    1.对象数组:new Integer(4),new Integer(3),new Integer(2),new Integer(1)
    2.原型数组:4,3,2,1对于最坏情况,难道上面两组数组的情况是不一样的?
      

  12.   

    很高兴看到你的回帖,Arrays类中的sort方法用来对对象数组排序,你的类必须得实现Comparable接口,其中的方法compareTo(object other)
    我想问的是你的参数arg0在这里干嘛的,人家为什么提供这个形参other,难道两个对象的比较都是通过创建个日期对象,得到当前的秒,看是不是
    大于30.这个比较有何意义?
      

  13.   

    ZangXt和hmsuccess说的挺在理的,我还有疑问想请二位一一解答
    先问个简单的,所谓的稳定性真的那么重要吗?对于性能上的损伤可不可以忽略?
    我总觉得不就是在排序诸如{12,12,12,12,12,12,12}的时候,不稳定的排序要比稳定的慢很多
    但是一般遇到如此神奇的数组是万分之一的可能,是不会影响到averageTime(n)的
      

  14.   

    参数一定要去用吗,main(String[] args)的args这个参数你每次都用的吗,
    如果你每次写程序都用args这个参数,你可以转行了,不送啊
      

  15.   

    Arrays类中的sort方法用来对对象数组排序,你的类不是必须实现Comparable接口
    还有public static <T> void sort(T[] a,Comparator<? super T> c)这么一个方法存在呢.
      

  16.   

    世界上没有包治百病的良药,当然在某些情况下我们也许得作出一些无奈的选择,对于java来说也是一样。
    main函数的args是用来干嘛的,compareTo(object other)这个other是干嘛的,难道你写程序天天都用args,比较的时候都不用other。争吵有意义吗,CSDN是你家嘛!
      

  17.   

    csdn不是我开的,但是此贴是我开的ok?
    你既然要我知道争吵没意义,那你先把该贴从头浏览一遍,谁先开的头,你有提出过任何对本帖有帮助的回答吗?
      

  18.   

    c++我没学过不知道,但是java中实现合并排序的话,是复制引用,比如把这个引用从数组a复制到数组b,貌似没有复制整个对象的需要
    而这个引用,只是一个数值类型的地址。不知道你同不同意在java中的Arrays.sort中,用合并排序还是快速排序,并不是根据你所说来做判断的?
      

  19.   

    ZangXt兄能不能给出这段英文的地址,我想亲眼看看,以后也可以直接看官方的解释了
      

  20.   

    http://zh.wikipedia.org/w/index.php?title=%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95&variant=zh-hans
      

  21.   

    http://java.sun.com/docs/books/tutorial/
    http://java.sun.com/docs/books/tutorial/collections/algorithms/index.html
      

  22.   

    堆排序我正好前几天看过,那我得打破砂锅问到底了,为什么Arrays.sort不用堆排序,而只用快速排序和合并排序呢
      

  23.   

    我很满意ZangXt和hmsuccess的回答
    接下来是本帖扩展问答
    大家可答也可不答,但是我还是会问就对了:)
      

  24.   

    你看过了堆排序,那你应该明白堆排序的比较次数至少是N(lgN)-O(N)
      

  25.   

    为啥我书上写Heap Sort的worstTime和averageTime都是O(n * log n)呢?
      

  26.   

    其实这个问题主要是考虑到算法的稳定性,总所周知,快排不稳定。如果用快速排序对object排序的话,无疑中间会有很懂不必要的Object的移动,而object类型都是些大数据,移动起来肯定是比较浪费时间,这可能就是为什么选择归并排序的原因吧。
      

  27.   

    应该是更适用与JVM运行吧 。
    毕竟是SUN自己的东西 怎么用效率高应该也应该是经过测试的。
    个人意见
      

  28.   

    好帖既然看见了舍不得不留名啊 ^^The sort operation uses a slightly optimized merge sort algorithm that is fast and stable: Fast: It is guaranteed to run in n log(n) time and runs substantially faster on nearly sorted lists. Empirical tests showed it to be as fast as a highly optimized quicksort. A quicksort is generally considered to be faster than a merge sort but isn't stable and doesn't guarantee n log(n) performance. Stable: It doesn't reorder equal elements. This is important if you sort the same list repeatedly on different attributes. If a user of a mail program sorts the inbox by mailing date and then sorts it by sender, the user naturally expects that the now-contiguous list of messages from a given sender will (still) be sorted by mailing date. This is guaranteed only if the second sort was stable. 
      

  29.   

    kokobox 是他推荐的
    楼主,给俺分吧。哈哈
      

  30.   

         不懂Java。感觉在C++快排是最好的排序算法。
      

  31.   


    没错,CSDN不是你开的,此帖是你开的,不过你开贴是开来干什么的,如果是开来求助的,那没人有义务要帮助你请问如果你不从待排序的对象里获取任何信息,那你的排序还有什么意义呢,字面上的问题没有必要深究,也不想深入讨论这个问题,大家能意会就行了,只是不喜欢你的语气
      

  32.   

    java