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[i];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是待排序元素的数量。这意味着当数据量较大时，插入排序的效率会显著下降，不适合处理大规模数据集‌。

‌不适用于部分有序的数据‌：虽然插入排序在数据部分有序的情况下表现较好，但如果数据已经接近排序状态，其他排序算法（如归并排序或快速排序）通常会更高效‌。

‌不稳定‌：插入排序是一种不稳定的排序算法，相同的元素在排序后可能会改变它们原有的顺序。这意味着如果输入数组中有重复的元素，排序后这些元素的相对顺序可能会发生变化‌。

‌不适合实时应用‌：由于插入排序的时间复杂度较高，它不适合需要快速响应的应用场景，如实时数据处理系统‌。