问一个排序算法效率问题
对一组正整数排序(该整数是某个对象的属性)
我在想到底是要自己实现呢还是直接用java的treemap+Comparator

treemap+Comparator的话就是实现一下排序的规则, 然后写个for循环,逐个把元素put到treemap里就够了. 每次put他都会自动排序成合适的组合
但是这个 100万个元素就是 实打实的100次for. 感觉效率很一般啊.

我如果自己写算法实现排序的话会不会更高效一点?
比如说sql里使用的 select * from table1 order by id desc 是不是就比java的treemap更高效一些呢?

我对排序不是太了解, 不过目测应该不算太难.  所以来咨询一下解决方案
------解决方案--------------------
100万个元素
把100万个元素一次性放到内存里，可以考虑一下是否有其他方案可用，只放部分。
------解决方案--------------------
放treemap？是按照属性对对象排序吗？是的话用comparator就可以，不用treemap。如果只是对整数排序，那楼主考虑的是如何存放的问题。如果放到数组中，用Arrays.sort方法就可以，一百万也是很快的。
------解决方案--------------------
算法的效率是指这个算法随着计算规模规模趋近于无穷大，这个算法的时间和规模的关系。而不是说在100万次时谁的效率高。100万次谁高？只要运行程序就知道。但100兆次呢？java api 里称treemap的算法效率是log(n)。几乎是再也不能更快了，你自己编写的话可以用空间来换时间，可以试着做到比它更快。
在工程实践中，mysql也不是真的占了100万行的内存，它只是取了其中的一列，建立index，在其上排序。
------解决方案--------------------
这里是oracle排序的算法效率，希望对你有帮助。http://www.itpub.net/forum.php?mod=viewthread&tid=1591352&highlight=
------解决方案--------------------

引用:

另外, 如果 treemap 内某个元素的排序变量值被修改了.
还需要我再次 for size次吗?

一般的单个元素再排序都是小于n的，treemap是log(n)

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

不知道treemap本身排序效率多少，但如果纯比较插入、查找等性能的话（没有排序），弱于HashMap
http://blog.hongtium.com/java-map-skiplist/
------解决方案--------------------
同5楼，本身排序效率就是插入效率即O(log n)，已经很高了


------解决方案--------------------
log(n) 应该是说的查找效率，而不是 tree 的建立效率。

4楼 +1

Arrays.sort(Object) 是用了 merge sort，小于某临界值的部分用 insertion sort
Arrays.sort(int[]) 用了 quick sort，因为 int 没有 stable 的问题，小于某临界值的部分也是用 insertion sort

这是最方便的，同时也很高效。

对于Object，我自己实现过quick sort，结果效率跟 Arrays.sort 里用的 merge sort 相差无几，而且还不是stable sort。
------解决方案--------------------
楼上写错了 Object -> Object[]


之前实现的 quick sort 在这里：
http://www.cnblogs.com/codejar/archive/2012/02/23/2365338.html
------解决方案--------------------

引用:

log(n) 应该是说的查找效率，而不是 tree 的建立效率。

4楼 +1

Arrays.sort(Object) 是用了 merge sort，小于某临界值的部分用 insertion sort
Arrays.sort(int[]) 用了 quick sort，因为 int 没有 stable 的问题，小于某临界值的部分也是用 insertion sor……

那建立效率就是
log1 + log2 + ... + logn