十大排序算法——希尔排序

主要思想：

基于插入排序，交换不相邻的元素已对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。思想是使数组中任意间隔为h的元素都是有序的，这样的数组称为h有序数组.

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++)//重复分成的每个子列表 
{ 
   for(int i=L+incr;i<n;i+=incr)//对每个子列表应用插入排序 
   { 
      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)。

适用于排序小列表，改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。