您现在的位置是:首页 > 正文

算法基础篇-07-排序-希尔排序(Shell Sort)

2024-02-01 06:36:29阅读 3

1. 希尔排序简介

  • 希尔排序(Shell Sort) 是一种分组插入排序算法,是基于插入排序算法演进而来;
  • 首先取一个整数d1=n/2, 将元素分为d1个组,每组相邻元素之间距离d1,在各组内进行直接插入排序;
  • 取第二个整数d2=d1/2,重复上述分组排序过程,直到di=1,即所有元素在同一组内进行直接插入排序;
  • 希尔排序每趟并不使某些元素有序,而是使整体数据越来越接近有序;最后一趟排序使得所有数据有序;

2. 原理图如下

  • 初始列表如下:
    在这里插入图片描述
  • 初始列表如图,n=9,n/2整除是4,所以d=4,所以列表会拆成四组,第一组是538,第二组是71,第三组是42,第四组是68,每一组进行排序
    在这里插入图片描述
  • 上面四组排完序之后如下所示,然后重组
    在这里插入图片描述
  • 接下来是d2=d1/2, 也就是4/2=2,将它分为2组
    在这里插入图片描述
  • 然后每组进行依次插入排序,然后重组
    在这里插入图片描述
  • 接下来是d=1,直接进行插入排序
    在这里插入图片描述
    排序就完成了;

3. 代码演示

由于 希尔排序是基于插入排序演进而来,因此只需要在插入排序的基础上,稍作修改;

回滚一下,这个是插入排序代码:
在这里插入图片描述
基于插入排序,调整代码如下

public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 6, 3, 1, 2, 9, 8};
        System.out.println("arr = " + Arrays.toString(arr));
        handShellSort(arr);
        System.out.println("arr = " + Arrays.toString(arr));
    }

    /**
     * 希尔排序
     *
     * @param arr 列表
     */
    public static void handShellSort(int[] arr) {
        int d = arr.length / 2;
        while (d >= 1) {
            shellSortGrep(arr, d);
            d = d / 2;
        }
    }

     /**
     * 希尔排序 间隔排序
     * <p>
     * 其实就是将插入排序里面初始默认值1改成grep
     *
     * @param arr  列表
     * @param gap 时间间隔Grep
     */
    public static void shellSortGrep(int[] arr, int gap) {
        //i 表示 摸到的牌的下标
        for (int i = gap; i < arr.length; i++) {
            //将摸到的牌暂存
            int tmp = arr[i];
            //j 表示手里的牌的下标
            int j = i - gap;
            //如果牌的下标小于0或者 手机的牌小于摸到的牌,就暂停循环
            while (j >= 0 && arr[j] > tmp) {
                //如果手里的牌大于摸到的牌,手里的牌往右边移动
                int temp = arr[j + gap];
                arr[j + gap] = arr[j];
                arr[j] = temp;
                j -= gap;
            }
        }
    }
}

4. 希尔排序时间复杂度

  • 希尔排序的时间复杂度讨论比较复杂,并且和选取的gap序列有关,当gap除以2的时候,他的速度还是比nb三人组里面最慢的堆排序,还要更慢;

网站文章

  • [极客大挑战 2020]Roamphp1-Welcome 请求方式不对

    [极客大挑战 2020]Roamphp1-Welcome 请求方式不对

    进入后我没仔细看,发现网页无法正常运行,以为没网了,后面仔细一看报错的状态是405百度安全验证原来是请求方式有问题,便抓包改一下请求方式<?phperror_reporting(0);if ($_SE...

    2024-02-01 06:36:23
  • java操作hdfs报错java.io.IOException Failed to replace a bad datanode on the existing pipeline due to no ...

    java操作hdfs报错java.io.IOException Failed to replace a bad datanode on the existing pipeline due to no ...

    错误原因:   执行追加的文件中有3个datanode,备份数量设置的是3。在写操作时,它会在pipeline中写3个机器。默认replace-datanode-on-failure.policy是DEFAULT,如果系统中的datanode大于等于3,它会找另外一个datanode来拷贝。目前机器只有3台,因此只要一台datanode出问题,就一直无法写入成功。 解决方法:   ...

    2024-02-01 06:35:54
  • 计算机二级基础知识简单汇总

    计算机二级相关知识,必考,看看你学会了没

    2024-02-01 06:35:48
  • 对Numpy库ndarray对象(矩阵)中的数据元素的访问、选取操作示例

    对Numpy库ndarray对象(矩阵)中的数据元素的访问、选取操作示例

    为了说明这个问题,选初始化一个矩阵B,其尺寸为两行四列三通道。 代码如下: # !/usr/bin/env python # -*- coding: utf-8 -*- import numpy as np B = np.array([[[11, 12, 13, 14], [15, 16, 17, 18]], [[19, 20, 21, 22], [23, 24, 25, 26]], [[2

    2024-02-01 06:35:43
  • GPT带我学-设计模式-模板模式

    GPT带我学-设计模式-模板模式

    GPT教我学习模板模式

    2024-02-01 06:00:20
  • 2019研究生学费估计参考

    2019研究生学费估计参考

    2019研究生学费估计 研究生考试的时间点: 预报名时间 为2018年9月24日至9月27日,每天9:00—22:00 网上报名时间 为2018年10月10日至10月31日,每天9:00-22:00 登录“中国研究生招生信息网”(http://yz.chsi.com.cn或http

    2024-02-01 06:00:12
  • jqgrid单元格合并

    jqgrid单元格合并

    jqgrid是动态加载数据的,所以我们得动态的给每个需要合并的单元格设定id

    2024-02-01 06:00:05
  • 数据库进阶——什么是事务

    数据库进阶——什么是事务

    事务 事务(Transaction)是由一系列对系统中数据进行访问与更新的操作所组成的一个程序执行逻辑单元。 事务的语法 事务的特性 事务并发问题 事务隔离级别 不同隔离级别的锁的情况 隐式提交 1、...

    2024-02-01 05:59:35
  • 共生·敏捷·进化,第二届全球DSO大会强势来袭!

    共生·敏捷·进化。12月1日,DSO 2022将于北京正式开幕。

    2024-02-01 05:59:28
  • 简单C语言的词法分析器(Java实现)

    简单C语言的词法分析器(Java实现)

    一、C语言子集的单词符号及内置码单词符号种别编号助记符内置码while1whilenullif2ifnullelse3elsenullswitch4switchnullcase5casenull标识符6idid的实际内容常数7numnmu的实际内容+8+null-9-nu...

    2024-02-01 05:59:18