黑马程序员技术交流社区

标题: 最快的排序方法？各种排序方法适合的情境？ [打印本页]

---

作者: Kevin123    时间: 2012-12-2 23:19
标题: 最快的排序方法？各种排序方法适合的情境？


有没有绝对的最快的排序方法？各种排序方法适合的情境？
了解过希尔排序，有没有一种比较精简的java实现希尔排序的方式? 高手请赐教

---

作者: 丁桂松    时间: 2012-12-2 23:33
我建议初学者.不需要研究这么深.把知识点归纳一下.做个思维导图.主要是看重点.次重点.当重点 次重点大纲轮廓掌握的很清楚的.有余力了就去研究细枝末节.除非你是天才 否则你不可能面面俱到的.

---

作者: Kevin123    时间: 2012-12-4 18:17

丁桂松 发表于 2012-12-2 23:33
我建议初学者.不需要研究这么深.把知识点归纳一下.做个思维导图.主要是看重点.次重点.当重点 次重点大纲轮 ...

谢了，比较感兴趣

---

作者: 李百韬    时间: 2012-12-5 00:10

  时间复杂度




排序方法                 最好情况                最坏情况             平均情况              稳定性              空间复杂度

冒泡排序                   O(n)                      O(n2)                 O(n2)                    稳定

快速排序                   O(nlogn)               O(n2)                  O(nlogn)            不稳定

简单选择排序                                                                   O(n2)                  不稳定

堆排序                                                   O(nlogn)                                        不稳定

直接插入排序            O(n)                      O(n2)                O(n2)                    稳定

希尔排序                                                                          O(n1.3)               不稳定

归并排序                    O(nlogn)               O(nlogn)             O(nlogn)             稳定

基数排序                                                                          O(d(r+n))              稳定
（1）选择排序最好是 O(n2)
（2）快速排序在平均情况下复杂性为O(nlogn)，最坏情况 O(n2)，最好O(nlogn)
（3）堆排序和合并排序在最坏情况下复杂性为O(nlogn)。可见，合并排序和堆排序是比较排序算法中时间复杂度最优算法。

空间复杂度
空间性能是排序所需辅助空间大小

所有简单排序和堆排序都是0(1)
快速排序为0(logn)，要为递归程序执行过程栈所需的辅助空间


归并排序和基数排序所需辅助空间最多，为O(n)   

         

         常用的内部排序方法有：交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、基数排序（一关键字、多关键字）。

---

作者: 李百韬    时间: 2012-12-5 00:14
因为快慢还要取决于待排数据   所以给出平均和最大时间复杂度  
其实希尔排序只有在大数据的情况下才会明显优于插入排序
下面给出希尔排序的java实现
希望lz能采纳
while(arr.length/3>h){
　　h = h*3+1;
　　}
　　while(h>0){
　　for(i = h; i >0 ; i++){
　　temp = arr[i];
　　j =i;
　　while(j >h-1 && arr[j-h]>temp ){
　　arr[j] = arr[j-h];
　　j -=h;
　　}
　　arr[j] = temp;
　　}
　　h = (h-1)/3;
　　}

---

作者: 杨永胜    时间: 2012-12-5 01:09
Arrays里面的是什么排序？？

---

作者: 李百韬    时间: 2012-12-5 18:11

杨永胜 发表于 2012-12-5 01:09
Arrays里面的是什么排序？？

快排  良葛格的书中有写到

---

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

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