排序算法之6：希尔排序 ShellSort

维基百科解释：希尔排序

希尔排序：也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

算法实现

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已经排好的了（此时插入排序较快）。

public class ShellSort {
    public static void shellSort(int[] arr) {
        if (arr == null || arr.length == 0)
            return;
        int gapSize = arr.length / 2;
        while (gapSize >= 1) {
            shellInsert(arr, gapSize);
            SortTest.printlnArray(arr);
            gapSize /= 2;
        }
    }
    
    /**
     * 希尔排序的一趟插入
     *
     * @param arr 待排数组
     * @param gapSize   增量
     */
    public static void shellInsert(int[] arr, int gapSize) {
        System.out.println("");
        System.out.println("步长大小为：" + gapSize);
        
        for (int rightNumIndex = gapSize; rightNumIndex < arr.length; rightNumIndex++) {
            int leftNumIndex = rightNumIndex - gapSize;
            
            int rightNum = arr[rightNumIndex];    //记录要插入的数据  

            System.out.println("比较 ：" + " 索引 " + leftNumIndex + " : " + arr[leftNumIndex] + " vs " + "索引 " + rightNumIndex + " : " + arr[rightNumIndex]);
            
            while (leftNumIndex >= 0 && arr[leftNumIndex] > rightNum) {  //从后向前，找到比其小的数的位置   
                arr[leftNumIndex + gapSize] = arr[leftNumIndex];    //向后挪动  
                leftNumIndex = leftNumIndex - gapSize;
            }
            
            if (leftNumIndex != rightNumIndex - gapSize) {    //存在比其小的数 
                arr[leftNumIndex + gapSize] = rightNum;
            }
        }
    }
}

白话分析

简单总结就是：

1. 按照一定的步长把数字串起来分为几个区域，对每个区域内的数字进行插入排序（为了更好的理解各个区域，可以按照步长把数组进行几列显示，那么接下来的操作就是对每列数据进行插入排序了）
2. 重复步骤1，直至步长为1后，进行最后一次整体插入排序（此时大部分数字其实已经靠近最终位置了，所以此时进行的插入排序进行的交换操作较少）；