日常算法——希尔排序

希尔排序

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因 DL．Shell 于 1959 年提出而得名。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
如图：

代码实现

package Suanfa;

/**
 * Created by hushangjie on 2017/11/8.
*/
public class ShellSort {
    public static void sort(int[] arr) {
        int temp;
        for (int k = arr.length / 2; k > 0; k /= 2) {
            for (int i = k; i < arr.length; i++) {
                for (int j = i; j >= k; j -= k ){
                    if (arr[j - k] > arr[j]) {
                        temp = arr[j-k];
                        arr[j-k] = arr[j];
                        arr[j] = temp;
                    }
                }

            }

        }
    }

    public static void main(String[] args) {
        int[] a = {23, 22, 1, 4, 555, 90};
        sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

特点

希尔排序使用了一种增量的方式去改进插入排序，所以希尔排序会比插入排序快一些，但是希尔排序是不稳定算法，时间复杂度为 O(n^1.3)。