主要思想：

基于插入排序，交換不相鄰的元素已對數(shù)組的局部進行排序，并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。思想是使數(shù)組中任意間隔為h的元素都是有序的，這樣的數(shù)組稱為h有序數(shù)組.

Java

public class Shell {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 5, 8, 9, 0, 7, 5, 1, 6, 8, 7, 15};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void sort(int[] array) {
        int n = array.length;
        int h = 1;
        while (h<n/3) h = 3*h +1;
        while (h >= 1) {
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && (array[j] < array[j - h]); j -= h) {
                    int temp = array[j];
                    array[j] = array[j - h];
                    array[j-h]= temp;
                }
            }
            h /=3;
        }
    }
}

C

void Shell() 
{ 
  for(int incr=3;incr<0;incr--)//增量遞減，以增量3，2，1為例 
{ 
       for(int L=0;L<(n-1)/incr;L++)//重復(fù)分成的每個子列表 
{ 
   for(int i=L+incr;i<n;i+=incr)//對每個子列表應(yīng)用插入排序 
   { 
      int temp=arr[i]; 
      int j=i-incr; 
      while(j>=0&&arr[j]>temp) 
      { 
          arr[j+incr]=arr[j]; 
          j-=incr; 
} 
arr[j+incr]=temp; 
} 
} 
} 
} 

最好情況時間：O(n)。

最壞情況時間：O(n^2)。

適用于排序小列表，改進了插入排序，減少了比較的次數(shù)。是不穩(wěn)定的排序，因為排序過程中元素可能會前后跳躍。