仔细看了下众多Arrays.sort的重载方法。
发现java在实现这些sort方法的时候,排序Object的时候都是用合并排序
排序primitive(int,float等原型数据)的时候用的是快速排序,为什么要
这样呢,不是说快速排序是最好的吗?为什么都不用快速排序排呢?
发现java在实现这些sort方法的时候,排序Object的时候都是用合并排序
排序primitive(int,float等原型数据)的时候用的是快速排序,为什么要
这样呢,不是说快速排序是最好的吗?为什么都不用快速排序排呢?
不懂不要乱讲,误人子弟
同意:快速排序的时间复杂度最坏为n*(n-1)/2 最好为n*logn
合并排序的时间复杂度 nlgn
个人理解,仅供参考.
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)
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方法有没有调用啥你说的属性
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. 归并排序既快速又稳定.
首先呢,虽然归并排序的时间复杂度是O(nlgN),但是它很难用于主存排序,主要问题在于合并两个排序的表
需要线性附加内存,在整个算法中还要花费将数据复制到临时数组在复制回来的一些附加的操作。在java语言中
,当排序一般的对象时,元素的比较消耗时很多,但是移动元素就很快,所以呢,归并排序使用最少次数的比较
因此,在java中归并排序是一般目的排序的最佳选择。
1.对象数组:new Integer(4),new Integer(3),new Integer(2),new Integer(1)
2.原型数组:4,3,2,1对于最坏情况,难道上面两组数组的情况是不一样的?
我想问的是你的参数arg0在这里干嘛的,人家为什么提供这个形参other,难道两个对象的比较都是通过创建个日期对象,得到当前的秒,看是不是
大于30.这个比较有何意义?
先问个简单的,所谓的稳定性真的那么重要吗?对于性能上的损伤可不可以忽略?
我总觉得不就是在排序诸如{12,12,12,12,12,12,12}的时候,不稳定的排序要比稳定的慢很多
但是一般遇到如此神奇的数组是万分之一的可能,是不会影响到averageTime(n)的
如果你每次写程序都用args这个参数,你可以转行了,不送啊
还有public static <T> void sort(T[] a,Comparator<? super T> c)这么一个方法存在呢.
main函数的args是用来干嘛的,compareTo(object other)这个other是干嘛的,难道你写程序天天都用args,比较的时候都不用other。争吵有意义吗,CSDN是你家嘛!
你既然要我知道争吵没意义,那你先把该贴从头浏览一遍,谁先开的头,你有提出过任何对本帖有帮助的回答吗?
而这个引用,只是一个数值类型的地址。不知道你同不同意在java中的Arrays.sort中,用合并排序还是快速排序,并不是根据你所说来做判断的?
http://java.sun.com/docs/books/tutorial/collections/algorithms/index.html
接下来是本帖扩展问答
大家可答也可不答,但是我还是会问就对了:)
毕竟是SUN自己的东西 怎么用效率高应该也应该是经过测试的。
个人意见
楼主,给俺分吧。哈哈
没错,CSDN不是你开的,此帖是你开的,不过你开贴是开来干什么的,如果是开来求助的,那没人有义务要帮助你请问如果你不从待排序的对象里获取任何信息,那你的排序还有什么意义呢,字面上的问题没有必要深究,也不想深入讨论这个问题,大家能意会就行了,只是不喜欢你的语气