黑马程序员技术交流社区

标题: 关于希尔排序的问题? [打印本页]

作者: 林鹏    时间: 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) {

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

  7.             }
  8. }
复制代码


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




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