黑马程序员技术交流社区

标题: 关于希尔排序的问题？ [打印本页]
作者: 林鹏    时间: 2014-7-7 19:00
标题: 关于希尔排序的问题？
本帖最后由 林鹏 于 2014-7-8 09:47 编辑

在看毕老师的视频时，老师提到希尔排序是最快的排序算法，但我在网上看的是希尔排序没有快速排序算法快，请各位高手深入浅出的分析下希尔排序算法，以及JAVA代码的具体实现？
作者: cat73    时间: 2014-7-7 23:48
没接触过希尔排序
下面是以前自己写的快速排序
希望能帮到你
  1.         /**
  2.          * 快速排序的接口函数,让调用者只需要传递数组进来即可
  3.          * @param num 要被排序的数组
  4.          */
  5.         private static void quickSort(int[] num){
  6.                 if(num.length < 2)
  7.                         return;
  8.                 quickSort(num, 0, num.length - 1);
  9.         }
  10.         
  11.         /**
  12.          * 快速排序的算法核心 本算法缺点为数据量过大时可能出现栈溢出
  13.          * 且实际效率严重依赖于传递进来的数据
  14.          * @param num 要被排序的数组
  15.          * @param a 本轮排序的范围
  16.          * @param b 本轮排序的范围
  17.          */
  18.         private static void quickSort(int[] num, int a, int b){
  19.                 int i, j, x, temp;
  20.                 i = a;
  21.                 j = b;
  22.                 x = num[(i + j) / 2];
  23.                 do{
  24.                         while(num[i] < x && i < b)
  25.                                 i++;
  26.                         while(num[j] > x && j > a)
  27.                                 j--;
  28.                         if(i <= j){
  29.                                 temp = num[i];
  30.                                 num[i] = num[j];
  31.                                 num[j] = temp;
  32.                                 i++;
  33.                                 j--;
  34.                         }
  35.                 }while(i <= j);
  36.                 if(a < j)
  37.                         quickSort(num, a, j);
  38.                 if(b > i)
  39.                         quickSort(num, i, b);
  40.         }
复制代码
作者: fantacyleo    时间: 2014-7-8 01:39
算法的快慢取决于很多因素，不给出具体的前提说谁快谁慢是没有意义的。比如说，快速排序在最坏情况下（数组完全倒序，比如8 7 6 5 4 3 2 1）时，速度和冒泡排序一样慢。即便数据排列是随机的，如果数据量不大（比如不到500），快速排序的优势也不十分明显。再比如，如果有无限的内存空间，那么计数排序是最快的，数组从头到尾走一遍就把顺序确定好了。通常说快速排序比冒泡、选择、希尔排序快，是指在合理的内存空间约束下，初始数据随机排列，数据量很大的情况下，完成快速排序所需要的操作步数远小于冒泡、选择、希尔排序。

当然，希尔排序也是一种非常不错的排序方法，通常情况下比冒泡、选择快得多，对中等规模的数据，排序时间还是可接受的。而且，希尔排序的波动小，也就是说，它在最好、最坏和平均情况下的表现相差不大。实现代码也挺简单。思路是这样的：
起始数组：3 1 10 6 4 5 8 12 9 2 11

首先选定一个数k（可以任意，当然也有专门研究如何最优选择这个数），通过比较和交换，让数组成为【k-有序】。所谓k-有序，是指从数组的任意一个元素出发，选取每隔k个元素形成的子数组都是有序的。比如说从4开始每隔5个元素选出来的子数组4 2不是升序，因此原数组不是5-有序的。假定我们就从数组长度的一半k=5开始，通过比较和交换，可以把原数组变为5-有序：3 1 10 6 2 5 8 12 9 4 11

接下来，减小k，比如k=k/2=2，重复上面的过程，将数组变为2-有序。最后一趟，k=1，数组变为1-有序，排序就完成了。

代码如下：
  1. public static void(int[] arr) {

  3.     for(int k = arr.length / 2; k >= 1; k /= 2)
  4.         // 里面两层循环是插入排序，让数组变为k-有序
  5.         for(int i = k; i < arr.length; i++)
  6.             for(int j = i; j >= k arr.length && a[j] < a[j - k]; j -= k) {
  7.                     swap(arr, i, j)

  9.             }
  10. }
复制代码

作者: 林鹏    时间: 2014-7-8 09:12
不明觉厉，辛苦两位了
作者: 钟翠翠    时间: 2014-7-8 09:34
学习了，赞一个！！



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