【排序】插入排序与希尔排序

一、插入排序（Insertion Sort）

　　插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

1.算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

2.动图演示

3.代码实现

public static void insertionSort(int[] arr){
    int len = arr.length;
    int preIndex,current;
    //从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的序列
    for (int i = 1; i < len; i++) {
        preIndex = i-1;//从已经排序的序列最右边的开始比较，找到比其小的数
        current = arr[i];//记录要插入的数据
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        //存在比其小的数，插入
        if (preIndex != i-1) {
            arr[preIndex + 1] = current;
        }
    }
}

4.算法分析

　　插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

二、希尔排序（Shell Sort）

　　1959年Shell发明，第一个突破O(n²)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序（递减增量排序算法）。

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

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

　　希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

1.算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2.动图演示

3.代码实现

版本一：

public static void shellSort(int[] arr){
    int len = arr.length;
    for (int gap=(int)Math.floor(len/2); gap > 0; gap=(int)Math.floor(gap / 2)) {
        //注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
        //分别使用插入排序
        for (int i = gap; i < len; i++) {
            int j = i;
            int current = arr[i];
            while (j - gap >= 0 && arr[j - gap] > current) {
                arr[j] = arr[j - gap];
                j = j - gap;
            }
            arr[j] = current;
        }
    }
}

版本二：

public static void shellSort2(int[] arr){
    int len = arr.length;
    int gap = 1;
    while (gap < len) {
        gap = gap * 3 + 1;
    }
    for ( ; gap > 0; gap=(int)Math.floor(gap / 3)) {
        for (int i = gap; i < len; i++) {
            int current = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > current) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = current;
        }
    }
}