算法(六)希尔排序

希尔排序是插入排序的一种，是直接插入排序的更高效的改进版。希尔排序是记录增量来进行分组，再对分组内部进行直接插入排序，随着增量的不断减小，直到增量减小到1时，即每个分组中的数据量为1，此时排序结束。

基本步骤

设待排序的数组为a[0...n-1]

1. 一般开始取增量数d=n/2。从a[0]~a[d-1]将数组中数据之间的间隔为增量数d的倍数归为相同组。
2. 依次对每组中的数据进行直接插入排序，使其有序。
3. 再增量数d=d/2，重复上面的步骤，直到d=1为止。

例如取d=10为例：

23, 4, 6, 34, 35, 47, 546, 32, 6,10

取d=5,以后依次区d的一半

23, 4, 6, 34, 35, 47, 546, 32, 6,10
23 ————— 47
—–4 —————–546
———6 ——————— 32
————34 ——————— 6
—————— 35 —————– 10
第一趟结果：
23, 4, 6, 6, 10, 47, 546, 32, 34, 35

d=2

23—6—10— 546—–34
—–4–6— 47—— 32— 35
第二趟结果：
6, 4, 10, 6, 23, 32, 34, 35, 546, 47

d=1

6, 4, 10, 6, 23, 32, 34, 35, 546, 47
第三趟结果：
4, 6, 6, 10, 23, 32, 34, 35, 47, 546

序列有序，此时排序结束。

实现

按照上面的分析步骤，可以发现主要是对d的值进行控制，所以实现代码如下

public static void shellSort(int[] arr) {
        int temp;
        //增量值
        int d = arr.length / 2;
        while (true) {
            for (int i = 0; i < d; i++) {//分成若干组进行排序
                for (int j = i; j + d < arr.length; j += d) {
                    for (int k = j + d; k - d >= 0; k -= d) {//使用直接插入排序
                        if (arr[k] < arr[k - d]) {
                            temp = arr[k];
                            arr[k] = arr[k - d];
                            arr[k - d] = temp;
                        } else {
                            break;
                        }
                    }
                }
            }
            if (d == 1) break;
            d = d / 2;
        }
    }

总结

快速排序是不稳定排序，虽然对每组的排序是使用直接插入排序，在分组中是稳定的，但由于会进行分组，数组所在组会发生变化，所以并不能保证它整体是稳定排序。至于d的取值也没有绝对，也可以根据情况取值与变化。

转载请指明出处 idisfkj博客：https://idisfkj.github.io