Shell排序是基于比较的基于比较的排序算法。
它是插入排序的泛化。
它是由唐纳德shell 发明的。

它允许对距离的元素进行排序。
在插入排序的情况下，在仅相邻的元件之间但在shell 体中发生比较，避免将相邻元素进行比较直到最后步骤。
shell排序的最后一步最终插入排序。

简而言之，它通过远处的比较和交换元件改善了插入排序。

shell sort使用可以称为增量序列的序列。
Shell Sort使多次通过阵列和使用插入排序的平等大小的数组的排序数。

Java程序实现shell排序：

package org.igi.theitroad;
 
import java.util.Arrays;
 
public class ShellSortMain {
 public static void main(String[] args) {
 int[] array = { 22, 53, 33, 12, 75, 65, 887, 125, 37, 977 };
 System.out.println("Before Sorting : ");
 System.out.println(Arrays.toString(array));
 System.out.println("===================");
 System.out.println("After Sorting : ");
 array = shellsort(array);
 System.out.println(Arrays.toString(array));
 }
 
 private static int[] shellsort(int[] array) {
 
 //first part uses the Knuth's interval sequence
 int h = 1;
 while (h <= array.length/3) {
 h = 3 * h + 1; //h is equal to highest sequence of h<=length/3
 //(1,4,13,40...)
 }
 
 //next part
 while (h > 0) { //for array of length 10, h=4
 
 //This step is similar to insertion sort below
 for (int i = 0; i < array.length; i++) {
 
 int temp = array[i];
 int j;
 
 for (j = i; j > h - 1 && array[j - h] >= temp; j = j - h) {
 array[j] = array[j - h];
 }
 array[j] = temp;
 }
 h = (h - 1)/3;
 }
 return array;
 }
 
}

运行上面的程序时，我们将得到以下输出：

Before Sorting : 
[22, 53, 33, 12, 75, 65, 887, 125, 37, 977]
===================
After Sorting : 
[12, 22, 33, 37, 53, 65, 75, 125, 887, 977]

时间复杂性：最佳情况：O(n)平均情况：取决于差距 ，最坏情况：O(nlog2n)