C++中常用的十大排序方法之4——希尔排序

           发展路上不孤单😊😊😊😊😊😊
【😊///盘算机爱好者😊///一连分享所学😊///如有须要接待收藏转发///😊】
本日分享关于C++中常用的排序方法之4——希尔排序的干系内容！

关于【C++中常用的排序方法之4——希尔排序】

   目次：
  

• 一、希尔排序的界说
  
• 二、希尔排序的发展汗青
  
• 三、希尔排序的的排序过程
  
• 四、希尔排序的根本原理
  
• 五、希尔排序的的特点
  
• 六、希尔排序的的优点
  
• 七、希尔排序的的缺点
  

  希尔排序（Shell Sort）

一、希尔排序的界说

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序黑白稳固排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记载按下标的肯定增量分组，对每组利用直接插入排序算法排序；随着增量渐渐淘汰，每组包罗的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便停止。

  
二、希尔排序的发展汗青

希尔排序按其筹划者希尔（Donald Shell）的名字定名，该算法由希尔在 1959 年所发表的论文“A high-speed sorting procedure” 中所形貌。
希尔排序是基于插入排序的以下两点性子而提出改进方法的： 

 1、插入排序在对险些已经排好序的数据操纵时，服从高，即可以到达线性排序的服从。
2、但插入排序一样平常来说是低效的，由于插入排序每次只能将数据移动一位。
1961年，IBM 公司的女步调员 Marlene Metzner Norton（玛琳·梅茨纳·诺顿）初次利用 FORTRAN 语言编程实现了希尔排序算法。在其步调中利用了一种浅易有用的方法设置希尔排序所需的增量序列：第一个增量取待排序记载个数的一半，然后逐次减半，末了一个增量为 1。该算法厥后被称为 Shell-Metzner 算法 ，Metzner 本人在2003年的一封电子邮件中说道：“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”
三、希尔排序的排序过程

1、缩小增量

希尔排序属于插入类排序,是将整个有序序列分割成多少小的子序列分别举行插入排序。
排序过程：先取一个正整数d1数组元素放一组，组内举行直接插入排序；然后取d2
三趟结果
04 13 27 38 49 49 55 65 76 97

2、Shell排序

Shell排序的算法实现:
1． 不设监督哨的算法形貌
void ShellPass(SeqList R，int d)
{//希尔排序中的一趟排序，d为当前增量
for(i=d+1;i
if(R[ i ].key
R[0]=R;j=i-d； //R[0]只是暂存单元，不是哨兵
do {//查找R的插入位置
R[j+d]=R[j]； //后移记载
j=j-d； //查找前一记载
}while(j＞0&&R[0].key
R[j+d]=R[0]； //插入R到准确的位置上
} //endif
该方法实质上是一种分组插入方法
比力相隔较远间隔（称为增量）的数，使得数移动时能跨过多个元素，则举行一次比力就大概消除多个元素互换。D.L.shell于1959年在以他名字定名的排序算法中实现了这一头脑。算法先将要排序的一组数按某个增量d分成多少组，每组中记载的下标相差d.对每组中全部元素举行排序，然后再用一个较小的增量对它举行分组，在每组中再举行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
一样平常的初次取序列的一半为增量，以后每次减半，直到增量为1。
给定实例的shell排序的排序过程
假设待排序文件有10个记载，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：
5，2，1

四、‌希尔排序的根本原理‌

希尔排序是基于插入排序的一种改进算法。它将整个待排序的记载序列分割成多少子序列，分别举行直接插入排序。然后渐渐减小隔断，再次举行插入排序，直到整个序列变为有序。希尔排序通太过组插入的方式，每次比力相距较远的元素，从而淘汰了逆序对的数量，进步了排序服从。
五、希尔排序的特点

希尔排序‌是一种高效的排序算法，由美国盘算机科学家Donald Shell于1959年提出。它是插入排序的一种改进版本，通太过组插入排序和缩小增量的方式，大幅度淘汰了逆序对的数量，从而进步了排序服从。以下是希尔排序的重要特点：
 ‌分组插入排序‌：希尔排序将数组分成多少个子序列，每个子序列通过插入排序举行排序。由于子序列的长度较短，插入排序的时间复杂度较低，从而进步了排序服从‌。
‌缩小增量‌：希尔排序通过渐渐缩小增量（通常采取二分法递减增量），将数组分成更小的子序列举行排序。增量终极减小到1时，整个数组举行一次插入排序‌。
‌大幅度淘汰逆序对‌：由于希尔排序是通过隔断分组举行插入排序的，每次排序都会将相距较远的元素举行比力和互换，从而大幅度淘汰了逆序对的数量。逆序对的数量是衡量一个排序算法服从的紧张指标，逆序对越少，排序服从越高‌。
‌非稳固性‌：希尔排序是一种非稳固的排序算法。在排序过程中，雷同巨细的元素大概会发生互换，导致原来相对序次的改变。只管云云，希尔排序在现实应用中并不影响排序结果的准确性‌。
‌实用场景‌：希尔排序实用于大部分环境，尤实在用于部分有序的数据集。当数据集靠近有序时，希尔排序的服从非常高‌。 

六、希尔排序的优点


‌希尔排序的优点重要包罗以下几个方面‌：‌
‌淘汰比力次数‌：希尔排序通太过组插入的方式举行排序，每次比力相距较远的元素，从而大幅度淘汰了逆序对的数量，进步了排序服从。
‌高效处理处罚大数据量‌：希尔排序在处理处罚大量数据时表现精彩，当时间复杂度通常为O(n^1.3)，而且空间复杂度为O(1)，这意味着它须要的额外空间非常小。
‌简单易实现‌：希尔排序的实现相对简单，易于明确和编写代码。
‌实用于大规模数据‌：希尔排序特别恰当处理处罚大规模数据，由于它通太过组和渐渐减小增量来排序，克制了直接对整个数据集举行排序的时间和空间复杂度过高的标题。
七、希尔排序的缺点

‌非稳固性‌：希尔排序是一种非稳固的排序算法，大概会改变雷同元素的相对序次。
‌性能受增量序列影响‌：增量序列的选择对希尔排序的性能有很大影响。如果增量序列选择不当，大概会导致时间复杂度退化为O(n^2)以致更差。
‌时间复杂度不确定‌：希尔排序的时间复杂度并不固定，通常以为是O(n^1.3)，但最坏环境下大概会更差。
七、插入排序的缺点

‌插入排序的重要缺点包罗以下几个方面‌：
‌时间复杂度较高‌：插入排序的时间复杂度在最坏的环境下是O(n^2)，此中n是待排序元素的数量。这意味着当数据量较大时，插入排序的服从会明显降落，不恰当处理处罚大规模数据集‌。
‌不实用于部分有序的数据‌：固然插入排序在数据部分有序的环境下表现较好，但如果数据已经靠近排序状态，其他排序算法（如归并排序或快速排序）通常会更高效‌。
‌不稳固‌：插入排序是一种不稳固的排序算法，雷同的元素在排序后大概会改变它们原有的序次。这意味着如果输入数组中有重复的元素，排序后这些元素的相对序次大概会发生厘革‌。
‌不恰当实时应用‌：由于插入排序的时间复杂度较高，它不恰当须要快速相应的应用场景，如实时数据处理处罚体系‌。