希尔排序详细解说

思路分析

希尔排序的主要实现逻辑还是基于插入排序的，插入排序的过程在上一篇文章中讲过啦，如果有兴趣的老铁可以查看以下文章：插入排序详细解说

了解了插入排序后，希尔排序就可以迎刃而解了

可以将整个数组分为gap组，这里的gap=array.length/2，然后进行插入排序，再将gap/2，再次进行插入排序，直到gap=1的时候，就可以得到最终的已排序数组

图解

代码实现

代码语言：javascript复制

public static void shellsertSort(int[] array){
        int gap = array.length/2;
        while (gap > 1){
            insertGap(array,gap);
            gap = gap / 2;
        }
        insertGap(array,gap);
    }

    private static void insertGap(int[] array, int gap) {
        for (int bound = gap; bound < array.length; bound  ){
            int v = array[bound];
            int cur = bound - gap;//已排好序列的最后一个元素
            for (; cur >= 0; cur -= gap){
                //循环和前面已排好序的元素一次比较
                if (array[cur] < v){
                    array[cur   gap] = array[cur];
                }else {
                    break;
                }
            }
            array[cur   gap] = v;
        }
    }

两个特性（和插入排序一样）

1.数据量少的时候，速度快

2.数据接近有序的时候，速度快

性能分析

时间复杂度：

最好：O(N) {数据有序}

平均：O(N^1.3)

最坏：O(N^2) {比较难构造}

空间复杂度：

O(1)

稳定性：

不稳定排序

排序 性能分析

0 人点赞