为了加快速度改进了插入排序,交换中间有间隔的元素对数组的局部进行排序,然后分开用插入排序将局部有序的数组进行数组排序,将间隔为h的数组编织在一起组成一个数组,称为h有序数组
数组中任意间隔为h的数值,都有序排列
对于任何以1为结尾的h序列,我们都能将数组排序
基本就是从大间隔到小间隔,不断的缩小间隔,然后进行相关的排序工作
|
public class ShellSort {
public static void sort(Comparable[] a) {//进行排序的方法 int N = a.length;//得到所的个数 int h = 1;//初始化希尔值 while (h<N/3) h = h*3 +1;//保证不超过的情况获取最合适的希尔值,1,4,13 while(h>1){ for (int i = h; i < N; i++) {//一层遍历由N开始 for (int j = i; j >0 && less(a[j], a[j-h]); j-=h) { //查找数组前面的希尔值,然后判断是否需要交换 exch(a, j, j-h); } } h =h/3;//然后进行更深的排序,h更小; } } public static boolean less(Comparable a,Comparable a2) {//对元素进行比较 return a.compareTo(a2) < 0; } private static void exch(Comparable[] a,int i,int j) {//进行交换 Object n =a[i]; a[i] = a[j]; a[j] = (Comparable<Object>) n; } private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { System.out.println(a[i]+” “); }//进行输出 } public static boolean isSorted(Comparable[] a) {//测试是否排序 for (int i = 1; i < a.length; i++) { if (less(a[i],a[i-1])) { return false; } } return true; } } |
对于希尔排序,分为3份是最为合理的分法,然后我们逐步的缩小
对于越大的数组,性能更好