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

主要思想：基于插入排序，交换不相邻的元素已对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。思想是使数组中任意间隔为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= 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; } } }

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=0&&arr[j]>temp) { arr[j+incr]=arr[j]; j-=incr; } arr[j+incr]=temp; } } } }

最好情况时间：O(n)。最坏情况时间：O(n^2)。