希尔排序详细解说

古城微笑少年丶 2022-10-27 15:59 167阅读 0赞

## 思路分析 ##

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

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

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

## 图解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]

## 代码实现 ##

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)

**稳定性：**  
不稳定排序

[Link 1]: https://blog.csdn.net/qq_45136189/article/details/113577387
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]: /images/20221024/73994c25fea7469eb5eab43dc951e075.png