黑马程序员技术交流社区

标题: 请列举您了解的一些排序算法，并用Java语言实现一个效率较高的。 [打印本页]

作者: 萍水相逢 时间: 2014-7-31 15:19
标题: 请列举您了解的一些排序算法，并用Java语言实现一个效率较高的。
请问那一个排序算法效率最高啊？

作者: Wokno 时间: 2014-7-31 15:58
算法的使用还是要看具体的情况，各种算法都有其长处，当然也就有其弊端了，针对具体的情况具体分析哪一种算法合适，这就是效率最高的。。。。:)

作者: 王石 时间: 2014-7-31 21:15
我给人感觉是冒泡，和折半查找

作者: 阿温 时间: 2014-8-1 19:35
并归排序和快速排序,效率是常用算法中最高的

作者: 阿温 时间: 2014-8-1 19:38

以下的排序算法写的第一个O( ),括号中的次方数值越小,效率越高

稳定的
冒泡排序（bubble sort） — O(n^2）

鸡尾酒排序(Cocktail sort，双向的冒泡排序) — O(n^2）

插入排序（insertion sort）— O(n^2)

桶排序（bucket sort）— O(n); 需要 O(k) 额外空间

计数排序(counting sort) — O(n+k); 需要 O(n+k) 额外空间

合并排序（merge sort）— O(nlog n); 需要 O(n) 额外空间

原地合并排序— O(n^2)

二叉排序树排序（Binary tree sort） — O(nlog n)期望时间； O(n^2)最坏时间；需要 O(n) 额外空间

鸽巢排序(Pigeonhole sort) — O(n+k); 需要 O(k) 额外空间

基数排序（radix sort）— O(n·k); 需要 O(n) 额外空间

Gnome 排序— O(n^2)

图书馆排序— O(nlog n) with high probability，需要（1+ε)n额外空间

不稳定的
选择排序（selection sort）— O(n^2)

希尔排序（shell sort）— O(nlog n) 如果使用最佳的现在版本

组合排序— O(nlog n)

堆排序（heapsort）— O(nlog n)

平滑排序— O(nlog n)

快速排序（quicksort）— O(nlog n) 期望时间，O(n^2) 最坏情况；对于大的、乱数列表一般相信是最快的已知排序

Introsort— O(nlog n)

Patience sorting— O(nlog n+ k) 最坏情况时间，需要额外的 O(n+ k) 空间，也需要找到最长的递增子串行（longest increasing subsequence）

不实用的排序算法
Bogo排序— O(n× n!) 期望时间，无穷的最坏情况。

Stupid sort— O(n^3); 递归版本需要 O(n^2) 额外存储器

珠排序（Bead sort） — O(n) or O（√n)，但需要特别的硬件

Pancake sorting— O(n)，但需要特别的硬件

stooge sort——O（n^2.7）很漂亮但是很耗时

作者: 叼哥 时间: 2014-8-2 00:26
看回复长见识了

作者: chen010yu 时间: 2014-8-2 13:19
路过进来看看

作者: 萍水相逢 时间: 2014-8-4 18:26

阿温发表于 2014-8-1 19:38
以下的排序算法写的第一个O( ),括号中的次方数值越小,效率越高

稳定的

谢谢你的回复!你解释的很详细!

作者: 萍水相逢 时间: 2014-8-4 18:27

Wokno 发表于 2014-7-31 15:58
算法的使用还是要看具体的情况，各种算法都有其长处，当然也就有其弊端了，针对具体的情况具体分析哪一种算 ...

恩恩，说的挺合理的

作者: 孙小亚 时间: 2014-8-15 12:08
看回复学习

作者: 许愿じ☆VE杰 时间: 2014-8-20 17:11
看回复学习

作者: 杜工 时间: 2014-10-10 14:16
测试数据10000，排序的时间标明快速排序效率比较高。算法太多，最高的就不好说了。冒泡排序：120ms 选择排序：32ms 插入排序：20ms 快速排序：7ms

作者: wingtheu 时间: 2014-11-2 15:22
冒泡排序

作者: 完美是芬 时间: 2014-11-16 14:33
2楼列的算法好多啊，有些都没听过

作者: 袁阳1991 时间: 2014-12-5 13:40
快速排序吧效率就比较好

作者: 骑着会飞的猪 时间: 2014-12-6 15:24
好多算法呀，学习了！！

作者: 中国好熊猫 时间: 2014-12-7 22:11
传说中的位图排序，效率最高。。。前提呢是全是数字，而且不要重复

作者: Plus 时间: 2015-4-19 22:08
谢谢你的回复!你解释的很详细

作者: xxz 时间: 2015-5-26 13:08
个人觉得，还是快速排序算法效率较高

作者: xxz 时间: 2015-5-26 13:14
/** * 快速排序 */ private static void quickSort ( int[] array, int start, int end ) { if (start < end) { int key = array[start]; int i = start; for ( int j = start + 1; j < end + 1; j++ ) { if (key > array[j]) { int temp = array[j]; array[j] = array[i + 1]; array[i + 1] = temp; i++; } } array[start] = array[i]; array[i] = key; quickSort (array, start, i - 1); quickSort (array, i + 1, end); } }

作者: 怀英 时间: 2015-6-25 18:49

阿温发表于 2014-8-1 19:38
以下的排序算法写的第一个O( ),括号中的次方数值越小,效率越高

稳定的

这么多算法，长见识了

作者: asinzuo 时间: 2015-6-26 10:10
要不要知道那么多排序方法

作者: 不怕黑人 时间: 2015-7-11 12:50
来看2L 学习了！

作者: huanlong579 时间: 2016-3-2 16:19
长见识，很多都没听过，落伍了

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2