(十三)排序算法-希尔排序

这篇具有很好参考价值的文章主要介绍了(十三)排序算法-希尔排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1 基本介绍

1.1 概述

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。希尔排序相比较与插入排序多加了一步就是确定步长。之前在插入排序的过程中,步长是固定的即为1,在希尔排序中的步长是不固定的,一开始步长是数组长度的一半,之后每次分组排序之后步长就再减半,直到步长到1为止,这时候排序就已经完成了。

插入排序的问题点:
插入排序的时候,我们会发现一个很不友好的事儿,如果已排序的分组元素为 {2,5,7,9,10},未排序的分组元素为{1,8},那么下一个待插入元素为1,我们需要拿着1从后往前,依次和10,9,7,5,2进行交换位置,才能完成真正的插入,每次交换只能和相邻的元素交换位置。那如果我们要提高效率,直观的想法就是一次交换,能把1放到更前面的位置,比如一次交换就能把1插到2和5之间,这样一次交换1就向前走了5个位置,可以减少交换的次数,这样的需求如何实现呢?

1.2 算法详解

希尔排序法基本思想:
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

基本步骤:
希尔排序的基本步骤,在此我们选择增量 gap= length/2,缩小增量继续以 gap = gap/2 的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2…1},称为增量序列。希尔排序的增量序列的选择与证明是个数学难题,我们选择的这个增量序列是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

静图分析:
(十三)排序算法-希尔排序
动画展示:
(十三)排序算法-希尔排序

2 代码实现

2.1 代码实现

2.1.1 希尔排序-交换法
/**
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};

        System.out.println("------------排序前------------");
        System.out.println(Arrays.toString(arr));

        shellSort2(arr);
        System.out.println("------------排序后------------");
        System.out.println(Arrays.toString(arr));
    }

    // 希尔排序-交换法
    public static void shellSort(int[] arr) {
        int temp = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }

}
2.1.1 希尔排序-插入法
/**
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};

        System.out.println("------------排序前------------");
        System.out.println(Arrays.toString(arr));

        shellSort(arr);
        System.out.println("------------排序后------------");
        System.out.println(Arrays.toString(arr));
    }

    // 希尔排序-插入法(推荐)
    public static void shellSort(int[] arr) {
        // 增量 gap,并逐步的缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 从第 gap 个元素,逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]){
                        // 移动
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    // 当退出 while 后,就给 temp 找到插入的位置
                    arr[j] = temp;
                }
            }

        }
    }

}

2.2 性能分析

时间复杂度

  • 最优时间复杂度:根据步长序列的不同而不同
  • 最坏时间复杂度:O(n^2)
  • 稳定性:不稳定

希尔排序不像其他时间复杂度为O(N log2N)的排序算法那么快,但是比选择排序和插入排序这种时间复杂度为O(N2)的排序算法还是要快得多,而且非常容易实现。它在最坏情况下的执行效率和在平均情况下的执行效率相比不会降低多少,而快速排序除非采取特殊措施,否则在最坏情况下的执行效率变得非常差。

迄今为止,还无法从理论上精准地分析希尔排序的效率,有各种各样基于试验的评估,估计它的时间级介于O(N^3/2)和 与 O(N^7/6)之间。
我们可以认为希尔排序的平均时间复杂度为o(n^1.3)。文章来源地址https://www.toymoban.com/news/detail-413274.html

到了这里,关于(十三)排序算法-希尔排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】排序——插入排序及希尔排序

    目录 前言 一、排序的概念及其应用 1.1排序的概念 1.2排序的应用 1.3常见的排序算法 二、插入排序的实现  基于插入排序的优化——希尔排序(缩小增量排序    ========================================================================= 个人主页 代码仓库 C语言专栏 初阶数据结构专栏 Linux专栏

    2024年02月07日
    浏览(48)
  • 排序算法——希尔排序图文详解

    注1:本篇是基于对直接插入排序法的拓展,如果对直接插入法不了解,建议先看看 直接插入排序 注2:本篇统一采用升序排序 希尔排序法又称缩小增量法。 希尔排序其实是直接插入排序的改进。 其 基本思想是 : 先选定一个整数gap,把待排序文件中所有记录分成数组,所有

    2024年02月07日
    浏览(39)
  • 排序算法之【希尔排序】

      📙 作者简介:  清水加冰,目前大二在读,正在学习C/C++、Python、操作系统、数据库等。 📘 相关专栏: C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正! ✨每一次努力

    2024年02月08日
    浏览(41)
  • 排序算法-插入/希尔排序

    直接插入排序是一种简单的插入排序法,其基本思想是: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。 当插入第i(i=1) 个元素时,前面的 array[0],array[1],…,array[i-1] 已经排好序,此时用

    2024年02月05日
    浏览(44)
  • 排序算法:希尔排序

            1959 年 7 月,美国辛辛那提大学的数学系博士 Donald Shell 在 《ACM 通讯》上发表了希尔排序算法,成为首批将时间复杂度降到 O(n²)以下的算法之一。虽然原始的希尔排序最坏时间复杂度仍然是 O(n²) ,但经过优化的希尔排序可以达到 O(n^1.3)甚至O(n^7/6)。       

    2024年02月11日
    浏览(40)
  • 【排序算法】希尔排序

    希尔排序是一种经典的排序算法,它通过多次插入排序的方式,以及逐步缩小增量的策略,实现对数据的高效排序,希尔排序法又称缩小增量法。 希尔排序的核心思想在于将待排序的数据分成若干组,对每一组数据进行插入排序。这样做的好处是,一方面可以减少数据的比较

    2024年04月13日
    浏览(32)
  • 排序算法-----希尔排序

    目录 前言 希尔排序(shell) 排序原理 大致思路 示例  代码实现(C语言) 算法分析 时间复杂度 空间复杂度 稳定性         前面我有一篇插入排序的详细的文章讲解(链接:排序算法-----插入排序(图文详解)_灰勒塔德的博客-CSDN博客)今天我们接着学习排序算法中的希尔

    2024年02月09日
    浏览(32)
  • 八大排序算法之插入排序+希尔排序

    目录 一.前言(总体简介) 关于插入排序  关于希尔排序: 二.插入排序 函数首部: 算法思路: 算法分析 插入排序代码实现: 插入排序算法的优化前奏:  三.希尔排序(缩小增量排序) 1.算法思想:  2.算法拆分解析  序列分组 分组预排序: 分组预排序的另一种实现方式: 希尔排序的实现

    2023年04月09日
    浏览(45)
  • 排序算法:插入排序(直接插入排序、希尔排序)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关排序算法的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 目录   前言: 1.排序

    2024年02月09日
    浏览(50)
  • 【排序算法】希尔排序详解!(源码+实现)

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 算法—排序篇 🌄 莫道桑榆晚,为霞尚满天! 什么是希尔排序?希尔排序是如何实现的?它的思想和由来又是什么? 本文将从多方面,精细的带你了解希尔排序,让你彻底掌握它! 希尔排序(Shell Sort)是一种排序算法,由美国计算机

    2024年02月05日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包