目录
希尔排序原理
希尔排序的API设计
希尔排序的代码实现
希尔排序是插入排序的一种，又称"缩小增量排序”，是插入排序算法的一种更高效的改进版本。
希尔排序原理
1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组。
2.对分好组的每一组数据完成插入排序。
3.减小增长量，最小减为1，重复第二步操作。
希尔排序的API设计
希尔排序的代码实现
public class Shell { //对数组a中的元素进行排序 public static void sort(Comparable[] a){ int N=a.length; //确定增长量h的最大值 int h=1; while(h<N/2){ h=2*h+1; } //当增长量h小于1，排序结束 while(h>=1){ //找到待插入的元素 for(int i=h;i<N;i++){ //a[i]就是待插入的元素 //把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中 for(int j=i;j>=h;j-=h){ //a[j]就是待插入的元素，依次和a[j-h],a[j-2h],a[j-3h]进行比较，如果a[j]小， // 那么交换位置，如果不小于，a[j]大，则插入完成 if(greater(a[j-h],a[j])){ exchange(a,j,j-h); }else{ break; } } } h/=2; } } //比较v元素是否大于w元素 private static boolean greater(Comparable v,Comparable w){ return v.compareTo(w)>0; } //数组元素i和j交换位置 private static void exchange(Comparable[] a,int i,int j){ Comparable t=a[i]; a[i]=a[j]; a[j]=t; } } class Test{ public static void main(String[] args) { Integer[] a={9,1,2,5,7,4,8,6,3,5}; Shell.sort(a); System.out.println(Arrays.toString(a)); } }
测试结果：
由于增量h没有固定的值，希尔排序的时间复杂度较为复杂，但在处理大批量数据时，希尔排序的性能高于插入排序！
第二种写法
public class ShellSort { private static void shellSort(int[] arr) { int gap = arr.length / 2; int temp; while (gap >= 1) { for (int i = gap; i < arr.length; i++) { temp = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > temp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = temp; } gap = gap / 2; } } public static void main(String[] args) { int[] arr = {1,28,3,21,11,7,6,18}; shellSort(arr); System.out.println(Arrays.toString(arr)); } }
