一、排序思想

       希尔排序(Shell’s Sort)是插入排序的一种，是直接插入排序算法的一种更高版本的改进版本。

1. 把记录按步长gap分组，对每组记录采用直接插入排序方法进行排序；
2. 随着步长逐渐减小，所分成的组包含的记录越来越多；
   当步长值减小到1时，整个数据合成一组，构成一组有序记录，完成排序；

二、图解

三、代码实现

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * 希尔排序演示
     
    
   

    

     

    
    

     

       * @author ksh
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      public class ShellSort {
     
    
   

    

     

    
    

     
    public static void main(String[] args) {
     
    
   

    

     

    
    

     
        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
     
    
   

    

     

    
    

     

              shellSort(arr);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        for (int i : arr) {
     
    
   

    

     

    
    

     

                  System.out.print(i + "\t");
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    private static void shellSort(int[] arr) {
     
    
   

    

     

    
    

     
        //step:步长
     
    
   

    

     

    
    

     
        for (int step = arr.length / 2; step > 0; step /= 2) {
     
    
   

    

     

    
    

     
            //对一个步长区间进行比较 [step,arr.length)
     
    
   

    

     

    
    

     
            for (int i = step; i < arr.length; i++) {
     
    
   

    

     

    
    

     
                int value = arr[i];
     
    
   

    

     

    
    

     
                int j;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
                //对步长区间中具体的元素进行比较
     
    
   

    

     

    
    

     
                for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
     
    
   

    

     

    
    

     
                    //j为左区间的取值，j+step为右区间与左区间的对应值。
     
    
   

    

     

    
    

     

                          arr[j + step] = arr[j]; 
     
    
   

    

     

    
    

     

                      }
     
    
   

    

     

    
    

     
                //此时step为一个负数，[j + step]为左区间上的初始交换值
     
    
   

    

     

    
    

     

                      arr[j + step] = value;  
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: kangshihang.blog.csdn.net，作者：康世行，版权归原作者所有，如需转载，请联系作者。

原文链接：kangshihang.blog.csdn.net/article/details/116857696