首页 > 其他分享 >希尔排序的详解

希尔排序的详解

时间:2024-07-28 11:25:21浏览次数:19  
标签:textcolor 插入排序 gap 希尔 详解 序列 排序

这里是目录:


插入排序 \texttt{\textcolor{#11D4B5}{\huge 插入排序}} 插入排序

在待排序的元素中,假设前k个元素已有序,现将第k+1个元素插入到前面已经排好的序列中,使得前k个元素有序。
按照此法对所有元素进行插入,直到整个序列有序。
但我们并不能确定待排元素中究竟哪一部分是有序的。
所以我们一开始只能认为第一个元素是有序的依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。

↑↑↑黑色圈住的数字表示要插入到前面序列的数字


希尔排序 \texttt{\textcolor{#11D4B5}{\huge 希尔排序}} 希尔排序

讲完插入排序,就该讲我们的重点了。
希尔排序是一种改进的插入排序算法,也被称为缩小增量排序。
它通过将待排序序列分割成多个子序列来进行排序,然后逐步缩小子序列的长度,最终使整个序列变为有序。

希尔排序的核心思想是将相距某个增量的元素组成一个子序列,对子序列进行插入排序。
然后逐步减小增量,重复上述过程,直到增量为1时,完成最后一次插入排序,使整个序列成为有序的。


希尔排序的优点 \texttt{\textcolor{#11D4B5}{\huge 希尔排序的优点}} 希尔排序的优点
  1. 效率较高:对于大规模数据集,希尔排序通常比简单插入排序更快,特别是在处理近乎有序的数据时,由于跳跃式的比较和交换,效率提升显著。

  2. 灵活性:希尔排序通过调整间隔序列来适应不同类型的数据分布,这使得它在某些情况下能获得更好的性能,尽管没有一种固定的间隔序列适合所有场景。

  3. 稳定性:虽然希尔排序本质上不是稳定的排序算法,但在某些实现版本中,如果对相等元素进行特殊处理,可以保持相对位置不变,表现为某种形式的稳定性。

  4. 易于理解:作为一种改进的插入排序,希尔排序的原理相对直观,容易学习和实现。

然而,希尔排序的主要缺点在于它的时间复杂度依赖于所选的间隔序列,不稳定性和最坏情况下的效率不高可能会限制它在一些高并发环境下的使用。
因此,在实际应用中需要权衡性能和代码实现复杂性。


时间复杂度 \texttt{\textcolor{#11D4B5}{\huge 时间复杂度}} 时间复杂度

希尔排序的时间复杂度取决于增量序列的选取, 一般最好情况下为O(nlogn),最坏情况下为O(n^2)。
希尔排序是 不稳定的排序算法 ,即可能改变相同元素的原始顺序。


希尔排序的思想 \texttt{\textcolor{#11D4B5}{\huge 希尔排序的思想}} 希尔排序的思想

希尔排序也被称为缩小增量排序。
其基本思想是将待排序的元素按照一定的间隔分组,对每组使用插入排序算法进行排序,
然后逐步缩小间隔,再进行排序,直至间隔为1时进行最后一次排序。(如图)

在希尔排序中,我们要引入gap(间隔):


当gap不为1时,我们可以把它看做为一个预排序,先把数组变得比较有序。
然后当 gap为1时 就是直接 插入排序了。
因为插入排序对比较有序的数组排列效率更高,所以希尔排序就为先预排序,再直接插入排序。

预排序 \texttt{\textcolor{#11D4B5}{\huge 预排序}} 预排序

我们先定义一个长度为5的逆序数组{5,4,3,2,1},再来假设gap为3。
知周所众 众所周知插入排序再排逆序的数组时,时间复杂度为最坏的情况。 所以我们才要进行预排序
在这里插入图片描述

经过预排序后数组,已经变得比较有序了,这对后面的直接插入排序是有好处的提高效率


Knuth增量序列 \texttt{\textcolor{#11D4B5}{\huge Knuth增量序列}} Knuth增量序列

Knuth增量序列是希尔排序中使用的一种增量序列,它可以保证gap最后一定为1,
它的计算方式为:
gap = 1, 3, 9, 27, …

其中gap的初始值为1,然后每次计算下一个增量值h时,都乘以3再加1,直到h大于等于数组长度的三分之一

Knuth增量序列的特点是在每次排序中能够更好地减少逆序对的数量,从而提高排序的效率。
该增量序列的选择是经验性的,并没有严格的数学证明,但在实践中已经被广泛接受,并被证实在大多数情况下都能够有效地改善希尔排序的性能


代码实现希尔排序 \texttt{\textcolor{#11D4B5}{\huge 代码实现希尔排序}} 代码实现希尔排序

下面是使用实现希尔排序的代码:

#include<iostream>
using namespace std;
const int N = 1e6+5;
int n,arr[N];
void shellSort() {
    int gap = 1;// 使用Knuth增量序列,gap = 1, 3, 9, 27, ...
    while (gap < n/3) gap = 3 * gap + 1;// 使用Knuth增量序列,保证gap最后为1
    while (gap >= 1) {// 逐步缩小增量直到1
        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++)
        for (int j = i; j >= gap && arr[j] < arr[j-gap]; j -= gap) swap(arr[j], arr[j-gap]);
        gap /= 3;// 缩小增量
    }
}
int main() {
	cin>> n;
	for(int i=0;i<n;i++) cin>> arr[i];
    shellSort();// 排序 
    // 输出 
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

该代码使用了Knuth增量序列,h的初始值为数组长度的一半,然后逐渐减小h的值。
在每次循环内部,对每个子序列使用插入排序算法进行排序。最后输出排序后的数组。


总的来说,希尔排序可以应用于各种排序问题,并且在大规模数据下具有较好的性能。

标签:textcolor,插入排序,gap,希尔,详解,序列,排序
From: https://blog.csdn.net/woaichegan/article/details/140706515

相关文章

  • 2024-07-27:用go语言,给定一个正整数数组,最开始可以对数组中的元素进行增加操作,每个元素
    2024-07-27:用go语言,给定一个正整数数组,最开始可以对数组中的元素进行增加操作,每个元素最多加1。然后从修改后的数组中选出一个或多个元素,使得这些元素排序后是连续的。要求找出最多可以选出的元素数量。输入:nums=[2,1,5,1,1]。输出:3。解释:我们将下标0和3处的元素增加1......
  • Python 实现行为驱动开发 (BDD) 自动化测试详解
    在当今的软件开发领域,行为驱动开发(BehaviorDrivenDevelopment,BDD)作为一种新兴的测试方法,逐渐受到越来越多开发者的关注和青睐。Python作为一门功能强大且易于使用的编程语言,在实现BDD方面也有着独特的优势。那么,如何利用Python实现BDD自动化测试呢?本文将为你详细解析。如何......
  • WGS84、GCJ02、BD09和CGCS2000地理坐标系详解
    一、WGS84WGS84(WorldGeodeticSystem1984)是全球定位系统(GPS)所使用的地理坐标系统和地球参考框架。它是由美国国防部开发的,广泛应用于导航、制图和地理信息系统(GIS)中。以下是一些关于WGS84坐标系统的重要资料:1.基本概念椭球参数:长半轴(a):6378137.0米扁率倒数(1/f):298.257......
  • Python 实现行为驱动开发 (BDD) 自动化测试详解
    ​ 在当今的软件开发领域,行为驱动开发(BehaviorDrivenDevelopment,BDD)作为一种新兴的测试方法,逐渐受到越来越多开发者的关注和青睐。Python作为一门功能强大且易于使用的编程语言,在实现BDD方面也有着独特的优势。那么,如何利用Python实现BDD自动化测试呢?本文将为你详细解析。如......
  • 构造中心损失----pytorch详解
    当输入数据X维度为[num_classes,feat_dim]时,参考链接:Centerloss-pytorch代码详解.对于输入数据X类型为[batch_size,seq_len,feat_dim],对参考链接代码进行调整,整个代码如下:classCenterLoss_seq(nn.Module):"""Centerloss.Reference:Wenetal.ADisc......
  • C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
    写在最前,一篇文章学会C语言指针顶级重要,学习C语言最重要的一部分-------指针第八章指针超详细讲解_指针变量_二维数组指针_指向字符串指针文章目录写在最前,一篇文章学会C语言指针第八章指针超详细讲解_指针变量_二维数组指针_指向字符串指针1.指针变量1.1指针变......
  • 排序算法--希尔排序
    希尔排序(ShellSort)是一种高效的排序算法,它是插入排序的一种改进版本(插入排序可以查看我的上一篇文章)。以下是关于希尔排序的详细讲解:基本思想希尔排序的基本思想是将原始数据集分割成若干个子序列,然后对每个子序列进行插入排序。这些子序列是由相隔一定“增量”的元素组......
  • 找出分区值(Lc2740)——排序
    给你一个 正 整数数组 nums 。将 nums 分成两个数组:nums1 和 nums2 ,并满足下述条件:数组 nums 中的每个元素都属于数组 nums1 或数组 nums2 。两个数组都 非空 。分区值 最小 。分区值的计算方法是 |max(nums1)-min(nums2)| 。其中,max(nums1) 表示......
  • c++ typedef 关键字详解
    在C++中,typedef关键字用于为已有的数据类型创建一个新的别名。这使得代码更加易读和维护,尤其是当使用复杂的类型定义时。typedef可以用来简化代码或使其更具描述性。基本语法typedefexisting_typenew_name;这里,existing_type是已有的类型,new_name是你为它创建......
  • Midjourney入门-局部重绘详解与具体操作
    局部重绘是Midjourney一个非常实用的功能。通过局部重绘你可以对Midjourney生成的图片进行二次修改,达到控图改图的效果。接下来我们讲下操作step1-图片生成先生成一组图片,并挑选一张step2-认识三种重绘功能在生成的图片底下有三个按钮:Vary(Subtle)-变化(微妙)通......