2020-03-18

Algorithm Shell Sort

Shell Sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shell Sort is to allow exchange of far items. In shell Sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element is sorted.

前言

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

希尔排序

希尔排序思想：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序解析：

希尔排序动图：

希尔排序代码：

/**
 * @Auther: Arsenal
 * @Date: 2020-03-17 23:10
 * @Description: 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        // int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        // System.out.println("原始的数组:" + Arrays.toString(arr));
        // shellSortGression(arr);
        // System.out.println("排序后数组:" + Arrays.toString(arr));

        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        long start = System.currentTimeMillis();
        //shellSortExchange(arr);// 交换法：7817 毫秒
        shellSortGression(arr); // 移位法：23 毫秒
        long end = System.currentTimeMillis();
        System.out.println("80000个数字排序所用时间:" + (end - start));
    }

    /**
     * 希尔排序移位法
     * 效率高
     * @param arr 需排序数组
     */
    public static void shellSortGression(int[] arr) {

        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移位
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //当退出while后，就给temp找到插入位置
                    arr[j] = temp;
                }
            }
        }
    }

    /**
     * 希尔排序交换法
     * 效率低
     * @param arr 需排序数组
     */
    public static void shellSortExchange(int[] arr) {
        int temp = 0;

        // int total = 0;
        //gap 为步长
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //如果当前原始大于下标加上步长的那个原始则进行交换
                //交换法效率低
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }

            //System.out.println("第" + (++total) + "次排序后的数组:");
            //System.out.println(Arrays.toString(arr));
        }
    }
}

延伸

ShellSort
希尔排序 shell sort
理解希尔排序的排序过程
 韩顺平数据结构和算法
 五分钟学会一个高难度算法：希尔排序

Article Title:Algorithm Shell Sort

Article Author:Funing Ma

Release Time:2020-03-18 18:18:18

Last Update:2020-03-30 10:13:17

Original Link:https://mafuning.github.io/2020/03/18/2020-03-18-Algorithm-Shell-Sort/

License Agreement: "CC-BY-SA-4.0"