详解排序算法–插入排序和冒泡排序,希尔排序

基本希尔排序,步长为贰

public class ShellSort {

    public static <T extends Comparable<? super T>> void sort(T[] arr) {
        for (int len = arr.length, step = len / 2; step >= 1; step /= 2) {
            for (int i = step; i < len; i++) {
                T temp = arr[i];
                int j = i - step;
                for (;j >= 0 && arr[j].compareTo(temp) > 0; j -= step) {
                    arr[j + step] = arr[j];
                }
                arr[j + step] = temp;
            }
        }
    }

    public static void swap(Object arr[], int i, int j) {
        if (i != j) {
            Object temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    private static void printArr(Object[] arr) {
        for (Object o : arr) {
            System.out.print(o);
            System.out.print("\t");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
        printArr(arr);//3   5   1   7   2   9   8   0   4   6
        sort(arr);
        printArr(arr);//0   1   2   3   4   5   6   7   8   9
    }
}

 

希尔排序

希尔排序的缘由是根据插入排序的。
读者若不通晓插入排序,能够参见作者的详解排序算法–插入排序和冒泡排序.

希尔排序是依附插入排序的以下两点性质而建议革新情势的:

  • 插入排序在对差不多已经排好序的多寡操作时,功效高,即能够完毕线性排序的效率
  • 但插入排序一般的话是船到江心补漏迟的,因为插入排序每回只好将数据移动一个人

希尔排序利用了插入排序的简约,同不时候又幸免了插入排序每一趟交流只好消除3个逆序对的欠缺。所以Hill排序一般不是换来相邻成分,而是跳跃1段距离交换。

希尔排序,步长为 【一, 四, 1三, 40, 12一, 36四, 十93, …】

public class ShellSort {

    public static <T extends Comparable<? super T>> void sort2(T[] arr) {
        for (int len = arr.length, step = len / 2; step >= 1; step /= 2) {
            for (int i = step; i < len; i++) {
                T temp = arr[i];
                int j = i - step;
                for (; j >= 0 && arr[j].compareTo(temp) > 0; j -= step) {
                    arr[j + step] = arr[j];
                }
                arr[j + step] = temp;
            }
        }
    }

    public static <T extends Comparable<? super T>> void sort(T[] arr) {
        int len = arr.length;
        int step = 1;
        while (step < len / 3) {
            step = step * 3 + 1;
        }
        for (; step >= 1; step /= 3) {
            for (int i = step; i < len; i++) {
                T temp = arr[i];
                int j = i - step;
                for (; j >= 0 && arr[j].compareTo(temp) > 0; j -= step) {
                    arr[j + step] = arr[j];
                }
                arr[j + step] = temp;
            }
        }
    }


    public static void swap(Object arr[], int i, int j) {
        if (i != j) {
            Object temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    private static void printArr(Object[] arr) {
        for (Object o : arr) {
            System.out.print(o);
            System.out.print("\t");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
        printArr(arr);//3   5   1   7   2   9   8   0   4   6
        sort(arr);
        printArr(arr);//0   1   2   3   4   5   6   7   8   9
    }
}

  

算法思想

Hill排序通过将比较的万事要素分为多少个区域来进步插入排序的属性。那样能够让三个要素得以叁次性地朝最后地方前进一大步。然后算法再取更小的宽窄实行排序,算法的最后一步正是屡见不鲜的插入排序,不过到了那步,需排序的数据大致是已排好的了(此时插入排序较快)。

宽度种类

升幅的选取是希尔排序的机要片段。只要最后上涨的幅度为一其余步长体系都得以干活。算法最初叶以一定的增进率进行排序。然后会三番八遍以自然幅度实行排序,最后算法以大幅为一拓展排序。当步长为一时,算法变为插入排序,那就确定保证了数码一定会被排序。

可能Hill排序最紧要的地点在于当用非常小增长幅度排序后,从前用的极大开间还是是雷打不动的。例如,就算三个数列以大幅五进展了排序然后再以步长三进展排序,那么该数列不仅是以小幅度三有序,而且是以大幅度伍有序。如若不是这么,那么算法在迭代进度中会打乱在此在此之前的次第,那就不会以那样短的大运完毕排序了。

图片 1

Paste_Image.png

  • 最优时间复杂度
    O(n)

  • 不稳定

希尔排序动态图

图片 2

Sorting_shellsort_anim.gif

Java代码:

package cc;

public class ShellSort {

    public static void shellsort(int[] a) {

        int n = a.length;

        int j;
        for(int d=n/2;d>0;d/=2) {/* 希尔增量序列 */
            /* 插入排序 */
            for(int p=d;p<n;p++) {
                int temp = a[p];
                for(j=p;j>=d && a[j-1] > temp;j=j-d)
                    a[j] = a[j-d];
                a[j] = temp;
            }
        }

    }
}

相关文章