希尔排序

基本概念

希尔排序是一种基于插入排序的快速排序算法，希尔排序的时间复杂度和其增量序列有关系，并无确定值。希尔排序的空间复杂度是O(1),即属于就地排序，希尔排序属于不稳定的排序。

算法思想

将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的步长的子序列，对各个子序列进行插入排序；然后再选择一个更小的步长，再将数组分割为多个子序列进行排序……最后选择步长为1，即使用直接插入排序，使最终数组成为有序。

算法描述

我们用一个例子来描述希尔排序的过程：

给出一无序数组：5, 3, 6, 2, 1, 7, 9, 8, 0, 4

取步长为5，将数组划分为5个子数组。为使读者明白，在这里采用[下标]-值的形式表示：

第一个子数组：[0]-5 , [5]-7

第二个子数组：[1]-3 , [6]-9

第三个子数组：[2]-6 , [7]-8

第四个子数组：[3]-2 , [8]-0

第五个子数组：[4]-1 , [9]-4

对这五个数组分别进行插入排序，排序后的结果：

[0]-5 , [5]-7

[1]-3 , [6]-9

[2]-6 , [7]-8

[3]-0 , [8]-2

[4]-1 , [9]-4

合并起来就是： 5，3，6，0，1，7，9，8，2，4

第二次取步长为5-1=4，可划分为四个子数组：

第一个子数组：[0]-5 , [4]-1 , [8]-2

第二个子数组：[1]-3 , [5]-7 , [9]-4

第三个子数组：[2]-6 , [6]-9

第四个子数组：[3]-0 , [7]-8

再次对每个子数组进行插入排序，排序结果：

[0]-1 , [4]-2 , [8]-5

[1]-3 , [5]-4 , [9]-7

[2]-6 , [6]-9

[3]-0 , [7]-8

合并后为：1，3，6，0，2，4，9，8，5，7

依次类推

第三次取步长为3，排序后为：0 ，2 ，4， 1， 3 ，5， 7 ，8 ，6 ，9 

第四次取步长为2，排序后为：0 ，1 ，3 ，2， 4 ，5 ，6， 8， 7， 9 

第五次取步长为1，排序后为：0 ，1 ，2， 3 ，4 ，5 ，6 ，7 ，8 ，9

算法实现

package test;
/**
 * Title:ShellSort
 * Description:希尔排序
 * @author LeslieTian
 * @date   2018-9-29 下午5:06:59
 * @version 1.0
 */
public class ShellSort {
    public  static void shellSort(int[] arr){
     int h = arr.length/2;//初始步长取排序数组长度的一半
     if(h==0){
      return;
     }
     while(h>=1){
      for(int i = h; i < arr.length;i++){
       for(int j = i; j >= h && arr[j] < arr[j-h];j -= h){
        swap(arr,j,j-h);
       }
      }
      System.out.print("步长为" +h+ ": ");//输出一次循环后的数组
      for(int word : arr){
       System.out.print(word + " ");
      }
      System.out.println("\n");
      h -= 1;
     }//while
    }//method-shellSort
    
    public static void swap(int arr[],int x,int y){
     int temp;
     temp = arr[x];
     arr[x] = arr[y];
     arr[y] = temp;
    }
 
 public static void main(String[] args) {
       int arr[]= {5,3,6,2,1,7,9,8,0,4} ;
       shellSort(arr);
 }
}

运行结果：

步长为5: 5 3 6 0 1 7 9 8 2 4 

步长为4: 1 3 6 0 2 4 9 8 5 7 

步长为3: 0 2 4 1 3 5 7 8 6 9 

步长为2: 0 1 3 2 4 5 6 8 7 9 

步长为1: 0 1 2 3 4 5 6 7 8 9