高效排序算法-希尔排序

原理

希尔排序也属于插入类排序算法。希尔排序通过缩小增量，将待排元素划分为若干个子序列，分别对每个子序列按照直接插入排序算法进行排序。当增量为1时，待排序元素构成一个子序列，对该序列排序完毕后希尔排序结束。·

为了减少数据的移动次数，在初始序列较大时取较大的步长，通常取序列长度的一半，此时只有两个元素比较，交换一次；之后步长依次减半直至步长为1，即为插入排序，由于此时序列已接近有序，故插入元素时数据移动的次数会相对较少，效率得到了提高。

/**
 * shell排序
 * @param a
 * @return
 */
public static int[] shellSort(int[] a){
    int N = a.length;
    int h = 1;
    // 增量序列
    while(h < N/3){
        // h = 1,4,13,40,……
        h = h*3 + 1; 
    }

    while(h>=1){
        for (int i = h; i < N; i++) {
            // 进行插入排序，诺a[j]比a[j-h]小，则向前挪动h
            for (int j = i; j >= h && a[j-h]>a[j]; j -= h) {
                exc(a, j, j-h);
            }
        }
        h /= 3;
    }
    return a;
}

希尔排序的理念和梳排序的理念有点类似。在梳排序中，我们比较距离相差为step的两个元素来完成交换。在希尔排序中，我们的做法也是类似。我们在数组中每隔h取出数组中的元素，然后进行插入排序。当h=1时，则就是前面所写的插入排序了。

实例

流程图

时间复杂度：通常认为是O(N3/2) ，未验证　　稳定性：不稳定