05.希尔排序

希尔排序

1.基本思想
2.排序过程
3.代码实现
4.如何优化
5.复杂度
6.使用场景

1.基本思想

在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

2.排序过程

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

3.代码实现

如下所示

public static void HeerSort(int[] a) {
    int d = a.length / 2;
    while (true) {
        for (int i = 0; i < d; i++) {
            for (int j = i; j + d < a.length; j += d) {
                int temp;
                if (a[j] > a[j + d]) {
                    temp = a[j];
                    a[j] = a[j + d];
                    a[j + d] = temp;
                }
            }
        }
        if (d == 1) {
            break;
        }
        d--;
    }

    for(int i=0;i<a.length;i++){
        System.out.println("yc1-----" +a[i]);
    }
}

4.算法步骤

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