本教程介绍了如何用Java编写Shell排序程序。 Shell排序也是像Bubble排序，Selection排序这样的就地排序算法，但是比这些算法要快。

Shell排序算法

Shell排序基于插入排序，它在此基础上进行了改进以提高排序效率。在插入排序中，如果小元素在右侧更远，则需要移动很多元素才能将其移到左侧的适当位置。

在Shell中，排序插入按一定间隔对元素进行排序。一旦对这些元素进行排序，间隔就会减小，并且以新的间隔对元素进行排序，一旦对这些元素进行排序，间隔就会进一步减小，依此类推。重复此过程，直到元素之间的间隔为1. 这时，将相邻元素进行比较，并且外壳排序在该迭代中有效地变为插入排序。

到那时，时间间隔变成1，并且比较相邻元素，因为在时间间隔中完成了递增排序，因此数组已经"几乎已排序"，这意味着不需要将元素移到最末端。请注意，对于几乎排序的元素，插入排序的复杂度为O(N)而不是O(N2)。

shell排序步长

在shell排序中，我们从间隔间隔开始，并且该间隔不断减小，直到间隔变为1. 最常见的计算shell排序间隔序列的方法称为Knuth间隔序列。使用以下表达式生成Knuth间隔序列的值

间隔=(间隔* 3)+1;

其中interval的初始值为1.
为了缩短间隔，请使用以下公式，该公式与上述公式相反：

间隔=(间隔– 1)/ 3;

Shell排序Java程序

public class ShellSort {
  public static void main(String[] args) {
    int[] arr = {10, 52, 23, 32, 3, 56, 87, 12, 37, 91, 34, 78};
    System.out.println("Input array- " + Arrays.toString(arr));
    int[] sortedArray = shellSort(arr);
    System.out.println("Sorted array after shell sort- " + Arrays.toString(sortedArray));
  }
	
  private static int[] shellSort(int[] arr){
    int interval = 1;
    int temp;
    // interval calculation using Knuth's interval sequence
    while(interval <= arr.length/3){
      interval = (interval * 3) + 1;
    }
    while(interval > 0){    
      for(int i = interval; i < arr.length; i++){
        temp = arr[i];
        int j;                
        for(j = i; j > interval - 1 && arr[j-interval] >= temp; j=j-interval){
          arr[j] = arr[j - interval];                    
        }
        arr[j] = temp;
      }
      // reduce interval 
      interval = (interval - 1)/3;
    }
    return arr;
  }
}

输出：

Input array- [10, 52, 23, 32, 3, 56, 87, 12, 37, 91, 34, 78]
Sorted array after shell sort- [3, 10, 12, 23, 32, 34, 37, 52, 56, 78, 87, 91]

shell排序时间和空间复杂度

shell排序的平均时间复杂度被认为是O(N3 / 2)。

Shell排序是一种就地排序算法，因此不需要辅助空间。因此，shell排序的空间复杂度为O(1)。