七大排序之希尔排序

简介: 希尔排序是插入排序的一种,又称为缩小增量法。其思想就是先选定一个整数 gap ,把待排序数组中间隔为 gap 的数分为一组,并对每一组内的数进行插入排序。然后,取,重复上述分组排序工作。当 gap = 1时,所有数在同一组内排好序。

时间复杂度: ~

空间复杂度

稳定性:不稳定

1、基本思想

   希尔排序是插入排序的一种,又称为缩小增量法。其思想就是先选定一个整数 gap ,把待排序数组中间隔为 gap 的数分为一组,并对每一组内的数进行插入排序。然后,取,重复上述分组排序工作。当 gap = 1时,所有数在同一组内排好序。

2、代码讲解和实现

希尔排序实现可以分为两步:

       1:分组

       2:组内排序

① 分组

       我们首先要给 gap 取值,通常 会把数组的长度先赋值给 gap,然后以gap为步长进行分组排序。接着 gap除以2,再进行上述操作。


       最后 我们一定要把数组作为一个整体再进行排序,因为每次分组就肯能落下几个数,所以最后gap 一定要赋值为1。

② 组内排序

       组内排序跟插入排序大致相同,在插入排序中外循环是从 1下标开始进行插入,而在希尔排序中 gap 是不断变化的,所以外循环要从 gap 为下标开始,每次++,争取把每个组都遍历到。


       内循环 j 从 i - gap 开始,每次减去 gap,这样一组内的元素都趋于有序了。

 //组内插入排序
    private static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for(; j >= 0; j -= gap){
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    //分组
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);//把数组作为一个整体进行排序

3、特性总结

1.希尔排序是对直接插入排序的优化。

2.当gap > 1 时都是预排序,目的是让数组更接近有序。当 gap == 1 时,数组已经接近有序,这样就会很快。这样整体而言,可以达到优化的效果。

3.希尔排序的时间复杂度不好算,因为gap的取值方法很多,导致很难去计算,因此在很多书中给出的希尔排序时间复杂度都不固定。我们可以暂时按照~来算。

  4.希尔排序不是稳定的排序。

相关文章
|
5月前
|
搜索推荐 测试技术
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
|
6月前
|
存储 搜索推荐
【七大排序】堆排序详解
【七大排序】堆排序详解
89 3
|
6月前
|
机器学习/深度学习 搜索推荐
【七大排序】最基础的排序——冒泡排序
【七大排序】最基础的排序——冒泡排序
38 4
|
7月前
|
算法 搜索推荐
【六大排序详解】中篇 :选择排序 与 堆排序
选择排序可以用扑克牌理解,眼睛看一遍所有牌,选择最小的放在最左边。然后略过刚才排完的那张,继续进行至扑克牌有序。这样一次一次的挑选,思路很顺畅。总结为: 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。
53 6
|
7月前
|
搜索推荐 测试技术
【六大排序详解】开篇 :插入排序 与 希尔排序
排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 排序存在稳定性,稳定性是评估排序的重要标准。
48 1
|
7月前
|
算法
【六大排序详解】终篇 :冒泡排序 与 快速排序
冒泡排序如同泡泡上升一样,逐个逐个向上冒,一个接一个的冒上去。两两比较,较大者(较小者)向后挪动。全部遍历一遍即可完成排序
47 2
|
7月前
|
搜索推荐 算法
【十大排序】带你深入了解归并排序
【十大排序】带你深入了解归并排序
|
机器学习/深度学习 搜索推荐 算法
八大排序(四)--------直接插入排序
八大排序(四)--------直接插入排序
51 0
|
算法 搜索推荐
八大排序--------(五)堆排序
八大排序--------(五)堆排序
34 0
|
机器学习/深度学习 搜索推荐
八大排序(三)--------简单选择排序
八大排序(三)--------简单选择排序
47 0