排序-插入排序-希尔排序

statement：本篇内容只是建立在我目前经验的基础之上，必然有不完善甚至是不正确的地方，请谨慎阅读，如果能指出错误与不足之处，更是不甚感激
PS1：代码部分将使用Java语言进行展示
PS2：本节排序算法基于顺序表排序

---

一、原理

• 希尔排序可以简单理解为进行多次的直接插入排序
• 直接插入排序在待排序序列元素数量较少，待排序序列基本有序的情况下，拥有极高的效率，接近O(n)
• 按照上述规则，如果将待排序序列先分成多个小块各自排序，然后在整个序列有序程度较高的情况下，在进行一次完整的直接插入排序，那么排序效率将会得到显著提高
• 将排序序列分段也需要一定的策略，单纯的按照普通分段方式（即前面几个分为一段，后面几个分为一段），无法做到能够使整个序列在一次排序过后整体有序，只能做到每个部分有序
• 故希尔排序使用的是增量分段的策略，即按照一定的增量分段，如按2分段，就是第1、3、5、7、9、...分为一段，使用增量分段策略分段冰排序后，整个待排序序列能够获得一个整体有序的状态

---

二、代码

• Java代码

/**
 * 本函数原理是简单插入排序，但是只对其中增量为increment的部分序列进行排序，主要用于希尔排序
 * @param sortArray 待排序序列
 * @param increment 增量
 */
private static void simpleInsertSortASCByIncrement(int[] sortArray , int increment) {
    for(int i = increment ; i < sortArray.length ; i++) {//前面increment个序列对于其各自的下一个序列来说都是有序的，所以不用管
        int j = i;
        int temp = sortArray[i];
        for(;j >= increment && temp < sortArray[j-increment]; j-=increment) {
            sortArray[j] = sortArray[j-increment];
        }
        sortArray[j] = temp;
    }
}
/**
 * 希尔排序，增量序列算法为dlta[k] = 2^(t-k) + 1 
 * @param sortArray
 */
public static void shellInsertASC(int[] sortArray) {
    //求得最大排序次数
    int t= (int)(Math.log10(sortArray.length - 1)/Math.log10(2)) ;
    //计算增量序列
    List<Integer> incrementList = new ArrayList<Integer>();
    int increment = 0;
    for(int i = 0 ; increment != 1 ; i++) {
        increment = (int) (Math.pow(2, t - i)) + 1;
        incrementList.add(increment);
    }
    //按增量序列进行按增量分段的直接插入排序
    for(int i = 0 ; i < incrementList.size() ; i++) {
        simpleInsertSortASCByIncrement(sortArray, incrementList.get(i));
        System.out.println(Arrays.toString(sortArray));
    }
    
}

---

三、时间复杂度

希尔排序的时间复杂度和增量序列有关，上述的代码中使用的增量序列算法是dlta[k] = 2^(t-k) + 1，t为执行的趟数。

---

参考文档：
[1] [数据结构C语言版 -- 清华大学出版社]