算法可视化系列——排序算法——希尔排序

排序算法可视化系列——篇三“希尔排序”

 

希尔排序

 

基本思想分析：

在我的第一个排序算法可视化中，分析了插入排序，但是我们知道，对于数组尺

度比较大的，并且无序度很大，那么使用直接插入排序比较相邻的元素，然后进行排

序，这样做很麻烦。但是如果数组的无序度不是很大的话，那么插入排序就很好了，

比如说我们可以分析两种情况，一种最为糟糕的情况是使用插入排序时，每次都需要

交换，这样就达到了最坏的时间复杂度O(n^2)；另外一种是最理想的情况，既就是，

数组在排序之前就是有序的了，那么我们根本就不需要进行排序；所以为了避免大数

组且无序度很大的情况下插入排序的缺点，希尔改进了插入排序，将每次比较的不是

相邻元素，而是对于有等间隔索引的数组元素子列进行插入排序，然后减小间隔，再

对子列进行排序，直到间隔为1时就是对于整个数组的插入排序，但是经过前面对于

子列的插入排序，整个数组已经基本有序，所以会提高效率，而且希尔建议第一次选

取间隔时，选择数组长度的一半，然后每次减半，直到间隔为1，就是对整个数组进行

插入排序。（注意：选间隔时，最好选为奇数，不要选为偶数，因为加入第一次选4，

下一次变为一半2时，进行排序时，会重复上一次的元素，所以选奇数的话就不会出现

这种情况）

 

算法描述：

//假设是对最简单的整数类型数组进行排序

public static void AlgorithmShellSort(int[] a){

        首先得到数组的长度n

        然后进行循环直到间隔长度为1

        for(初始值从n的一半开始，每次循环变为上一次的一半){

               判断是否为偶数间隔，如果是，给间隔加一或是减一都可以

//对每个子列都进行排序

for(对于间隔进行循环，因为间隔为多大，就说明有几个子列){

for(从子列i的i + step初始位置开始，每次增加step直到小于数组长度){

记录此刻需要进行插入的元素及位置索引

while(进行位置移动)的判断{

移动元素将index位置元素移动到index + 1上

}

已经找到了合适位置，插入上面选择的元素

}

}

        }

}

 

从上面的算法描述中可以看出使用了那么多循环，但是事实证明希尔排序速度还是很

快的，如果按照上面说的每次选取间隔时，均选取为奇数，那么希尔排序的最坏情况

下时间复杂度为O(n^1.5)，整个时间复杂度在n~n^1.5之间。

 

算法Java的基本实现：

 

/**
* 希尔排序的基本实现
* 在整型数组上的基本实现
*
*/
public static void shellSort(int[] a){
  int n = a.length;
  /**
  * 间隔的选取，进行循环选取，直到step为1
  */
  for(int step = n/2; step > 0; step /= 2){
    /**
    * 将step改变为奇数
    */
    if(step % 2 == 0){
      step += 1;
    }
    /**
    * 对子列进行循环排序
    */
    for(int i = 0; i < step; i++){
      /**
      * 对子列进行插入排序
      */
      for(int j = i + step; j < a.length; j += step){
        int temp_data = a[j];
        int index = j - 1;
        while(index >= 0 && temp_data < a[index]){
          a[index + 1] = a[index];
          index--;
        }
        /**
        * 找到插入位置
        */
        a[index + 1] = temp_data;
      }
    }
  }
}

 

 上面是对希尔排序的基本实现，主要用来体会希尔排序的主要思想，下面是对希尔排序的动态演示......

 

一、 排序中......

 

 

 二、 子列插入排序......

 三、排好序。

 
以上就是对希尔排序的可视化演示，具体源代码附录如下，仅附录ShellSort部分：

 
 

评论

3 楼 wojiaolongyinong 2013-05-21  

消失的气泡 写道

博主，你在这个篇文章中贴的代码有问题的，我帮改了下！

public static void shellSort(int[] a){
	  int n = a.length;
	  /**
	  * 间隔的选取，进行循环选取，直到step为1
	  */
	  for(int step = n/2; step > 0; step /= 2){
	    /**
	    * 将step改变为奇数
	    */
	    if(step % 2 == 0){
	      step += 1;
	    }
	    System.out.println("=========="+step);
	    /**
	    * 对子列进行循环排序
	    */
	    for(int i = 0; i < step; i++){
	      /**
	      * 对子列进行插入排序
	      */
	      for(int j = i + step; j < a.length; j += step){
	        int temp_data = a[j];
	        int index = j - step;
	        while(index >= 0 && temp_data < a[index]){
	          a[index + step] = a[index];
	          index = index -step;
	        }
	        /**
	        * 找到插入位置
	        */
	        a[index + step] = temp_data;
	        for(int v =0;v<a.length;v++){
	        	System.out.print(a[v]+",");
	        }
	        System.out.println("");
	      }
	    }
	  }
	}

如果看这篇博客的朋友想更直观了解希尔排序，请点这个，这是个希尔排序的动画
[url]
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/shell.htm
[/url]

奥。。。。我发现了。。。。我的失误。。。。谢谢哈

2 楼 消失的气泡 2013-05-21  

博主，你在这个篇文章中贴的代码有问题的，我帮改了下！

public static void shellSort(int[] a){
	  int n = a.length;
	  /**
	  * 间隔的选取，进行循环选取，直到step为1
	  */
	  for(int step = n/2; step > 0; step /= 2){
	    /**
	    * 将step改变为奇数
	    */
	    if(step % 2 == 0){
	      step += 1;
	    }
	    System.out.println("=========="+step);
	    /**
	    * 对子列进行循环排序
	    */
	    for(int i = 0; i < step; i++){
	      /**
	      * 对子列进行插入排序
	      */
	      for(int j = i + step; j < a.length; j += step){
	        int temp_data = a[j];
	        int index = j - step;
	        while(index >= 0 && temp_data < a[index]){
	          a[index + step] = a[index];
	          index = index -step;
	        }
	        /**
	        * 找到插入位置
	        */
	        a[index + step] = temp_data;
	        for(int v =0;v<a.length;v++){
	        	System.out.print(a[v]+",");
	        }
	        System.out.println("");
	      }
	    }
	  }
	}

如果看这篇博客的朋友想更直观了解希尔排序，请点这个，这是个希尔排序的动画
[url]
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/shell.htm
[/url]

1 楼 kyolxs 2013-05-21