排序算法

natloc 2012-08-25

Arrays.java'ssortmethodusesquicksortforarraysofprimitivesandmergesortforarraysofobjects。

[经典排序算法][集锦]

http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html

补充:

排序算法——堆排序:

http://www.cnblogs.com/luchen927/archive/2012/03/08/2381446.html
引用
我们可以得知,处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最大堆,依次类推,最终得到排序的序列。

或者说,堆排序将所有的待排序数据分为两部分,无序区和有序区。无序区也就是前面的最大堆数据,有序区是每次将堆顶元素放到最后排列而成的序列。每一次堆排序过程都是有序区元素个数增加,无序区元素个数减少的过程。当无序区元素个数为1时,堆排序就完成了。

本质上讲,堆排序是一种选择排序,每次都选择堆中最大的元素进行排序。只不过堆排序选择元素的方法更为先进,时间复杂度更低,效率更高。

大O表示法:运行时间与数据项个数的关系。

冒泡排序:

比较次数和交换次数都为O(N2)

选择排序:

比较次数为O(N2),交换次数为O(N)

相关推荐