希尔排序算法

java实现希尔排序算法

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

给定实例的shell排序的排序过程
假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：
5，2，1

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。

时间复杂度：O(n^(1.3—2))

java代码实现：

//希尔排序
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[80000000];
        for (int i = 0; i < 80000000; i++) {
            int random = (int) (Math.random() * 100);
            arr[i] = random;
        }

        Date date = new Date(System.currentTimeMillis());
        System.out.println(date);
//        shellSort(arr);
        shellSort2(arr);
        date = new Date(System.currentTimeMillis());
        System.out.println(date);

    }


    public static int[] shellSort(int[] arr) {
        int temp = 0;
        //插入时 采用交换法
        for (int l = arr.length / 2; l > 0; l /= 2) {
            //遍历各组中所有的元素，（共有 l 组，每组有数个元素）。 l 为步长
            for (int i = l; i < arr.length; ++i) {
                for (int j = i; j - l >= 0; j -= l) {
                    //如果当前的元素大于 加上步长后的那个元素的话就 交换位置
                    if (arr[j] < arr[j - l]) {
                        temp = arr[j];
                        arr[j] = arr[j - l];
                        arr[j - l] = temp;
                    }
                }
            }
        }
        return arr;
    }


    //插入时 采用移动法(速度比较快 )
    public static int[] shellSort2(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {

            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
        return arr;
    }
}

执行时间展示：
随机排序80000000个随机生成的数耗时12s