希尔排序 | Juchia

图示

原理

Code

1 确定间隔大小 gap = 元素个数/2
2 从索引0开始，每隔 gap 个元素分成一组
3 每一组元素使用插入排序进行排序(但不是一组一组进行，而是交替进行)
4 全部组排完序后，gap = gap/2
5 重复步骤2和3和4，直到 gap=1时，即每隔1个元素为一组，即全部元素为一组，这时就是普通插入排序

实现

java

public static void _希尔排序(Comparable[] a) {
        int n = a.length;
        int gap = a.length/2;

        while(gap >= 1){// 控制分组间隔

            for (int i=gap; i<n; i++){ //轮流提取各个分组第一个没有排序的元素

                Comparable _提取的元素 = a[i];

                //_提取元素依次和自己组前面已经排好序的元素比较
                for(int j=i-gap; j>=0; j=j-gap){ //控制各个分组内比较和挪动
                    if (_是否小于(_提取的元素,a[j])){//提取的元素比被比较元素小,
                        _交换(a,j,j+gap);//被比较的元素往后挪
                    }else{
                        break;
                    }
                }

            }
            gap = gap/2;
        }
    }

性能

Code

推导略

O(n*logn)

稳定性

不稳定

其他

Code

一 gap增量的计算算法有很多种, 不同的算法影响排序的性能, 以下是一些算法

1 最简单的希尔增量算法 初始 gap = 元素个数/2，然后每轮完成后，gap = gap/2
  Shell增量序列的最坏时间复杂度为 O(n^2); 平均时间复杂度未知

2 Hibbard增量算法 gap = 2^轮数 - 1 其中轮数从1开始
  Hibbard 增量序列的最坏时间复杂度为 O(n^(3/2))；平均时间复杂度约为 O(n^(5/4))
  
3 Sedgewick增量算法 9*4^轮数 - 9*2^轮数 + 1 或 4^轮数 - 3*2^轮数 + 1, 取两者的较大的那个值
  Sedgewick 增量序列的最坏时间复杂度为 O(n^(4/3))；平均时间复杂度约为 O(n^(7/6))

二 为什么要先分组,再对每一组进行插入排序?
	因为插入排序，提取的元素一直和左边已经排好序的元素比较，一旦比较到比它小的元素后就不用往前比了，直接将提取元素插入到比它小的元素后。分组后元素的个数变少了，插入排序的效率变高。每组完成插入排序后该组的小的元素往左挪，大的元素往右挪，虽然各组排序好后整体元素没有排好序，但是已经相对有序了，即较小的元素一般在左边，较大的元素在右边。当 gap=1时，整体元素使用插入排序，这时插入排序效率很高，每个提取的元素不用一直往前比较很多次，只需要比较很少的次数即可。
	
三 希尔排序的本质
	本质是插入排序的优化