Java 代码实现:

1     @Test 2     public void ShellSort(){ 3          4         int[] array={9,8,7,6,5,4,3,2,1}; 5         int j,temp; 6          7         System.err.println(Arrays.toString(array)); 8         //gap为步长,每次取半 9         for(int gap=array.length/2;gap>0;gap/=2){10             for(int i=gap;i
     
      =gap && temp-array[j-gap]<0;j-=gap)14                     array[j]=array[j-gap];15                 array[j]=temp;16                 System.err.println(Arrays.toString(array));17             }18         }19     }
     

算法的时间复杂度最坏为O(nlog2 2n),最好为O(n log n)