排序系列【比较排序系列之】shell排序

标签: shell排序  希尔排序

上篇我们对直接插入排序有了一定的了解,并且明确知道插入排序最佳排序算法则是O(n),且适合短序列的排序情况,本篇我们讲述的shell排序则有效的利用了插入排序的这两个性质。
shell排序的眼光:不同于直接插入排序的相邻记录之间的比较,而是着眼于那些不相邻的记录进行比较和移动,待比较到最后,当间距减少为1时,也就是整个序列接近于一个正序的状态,然后再对整个序列进行插入排序。
本篇我们采用数组长度n=8,增量每次除以2递减的方式来选择增量,即增量序列为(2^2,2^1,2^0),图示如下:
d=4
d=2
d=1

根据所写代码来走行走一遍的话,简单流程如下:array[] 以下用A[]表示:

d value i value j value 比较A[]
d=4 i=4 j=4 A[4]和A[0]
i=5 j=5 A[5]和A[1]
i=6 j=6 A[6]和A[2]
i=7 j=7 A[7]和A[3]
d=2 i=2 j=2 A[2]和A[0]
i=3 j=3 A[3]和A[1]
i=4 j=4 A[4]和A[2]
i=5 j=6 A[5]和A[3]
i=6 j=6 A[6]和A[4]
i=7 j=7 A[7]和A[5]
d=1 i=1 j=1 A[1]和A[0]
i=2 j=2,j=1 A[2]和A[1],A[1]和A[0]
….
i=7 j=7,j=6,j=5,j..j=1 A[7]和A[6],A[6]和A[5]…A[1]和A[0]

最后实现的简单代码:

 public static void main(String[] args) {
         //定义的数组
        int[] array = {16, 11, 14, 13, 4, 33, 22, 11};
        ShellSort2 shellSort = new ShellSort2();
        shellSort.shellSort(array);
        System.out.println(Arrays.toString(array));
    }

    void shellSort(int[] array) {
        int delta;
        int n = array.length;
        //间隔-增量每次除以2递减的方式来选择增量,也就是4,2,1
        for (delta = n / 2; delta > 0; delta /= 2) {
            int tempRecord = 0;
            for (int i = delta; i < array.length; i++) {
                tempRecord = array[i];
                int j = i;
                while (j > delta - 1 && tempRecord < array[j - delta]) {
                    array[j] = array[j - delta];
                    j -= delta;
                }
                array[j] = tempRecord;
            }
        }
    }

至于shell的时间复杂度这里则不变多说,因为负责度和增量的设置息息相关。下篇我们则介绍直接插入排序和shell排序运行时间的比较。

原文链接:加载失败,请重新获取