移动应用网站开发,中国建设银行个人网站注册,强生公司网站,ppt模板免费下载完整版免费简约成长路上不孤单#x1f60a;#x1f60a;#x1f60a;#x1f60a;#x1f60a;#x1f60a;
【#x1f60a;///计算机爱好者#x1f60a;///持续分享所学#x1f60a;///如有需要欢迎收藏转发///#x1f60a;】
今日分享关于C中常用的排序方法之4——希尔排序的相… 成长路上不孤单
【///计算机爱好者///持续分享所学///如有需要欢迎收藏转发///】
今日分享关于C中常用的排序方法之4——希尔排序的相关内容 关于【C中常用的排序方法之4——希尔排序】 目录 一、希尔排序的定义二、希尔排序的发展历史三、希尔排序的的排序过程四、希尔排序的基本原理五、希尔排序的的特点六、希尔排序的的优点七、希尔排序的的缺点 希尔排序Shell Sort
一、希尔排序的定义
希尔排序(Shells 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 Rint d)
{//希尔排序中的一趟排序d为当前增量
for(id1;i
if(R[ i ].key
R[0]R[i];ji-d //R[0]只是暂存单元不是哨兵
do {//查找R的插入位置
R[jd]R[j] //后移记录
jj-d //查找前一记录
}while(j0R[0].key
R[jd]R[0] //插入R到正确的位置上
} //endif
该方法实质上是一种分组插入方法
比较相隔较远距离称为增量的数使得数移动时能跨过多个元素则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组每组中记录的下标相差d.对每组中全部元素进行排序然后再用一个较小的增量对它进行分组在每组中再进行排序。当增量减到1时整个要排序的数被分成一组排序完成。
一般的初次取序列的一半为增量以后每次减半直到增量为1。
给定实例的shell排序的排序过程
假设待排序文件有10个记录其关键字分别是
49386597761327495504。
增量序列的取值依次为
521 四、希尔排序的基本原理
希尔排序是基于插入排序的一种改进算法。它将整个待排序的记录序列分割成若干子序列分别进行直接插入排序。然后逐渐减小间隔再次进行插入排序直到整个序列变为有序。希尔排序通过分组插入的方式每次比较相距较远的元素从而减少了逆序对的数量提高了排序效率。
五、希尔排序的特点
希尔排序是一种高效的排序算法由美国计算机科学家Donald Shell于1959年提出。它是插入排序的一种改进版本通过分组插入排序和缩小增量的方式大幅度减少了逆序对的数量从而提高了排序效率。以下是希尔排序的主要特点 分组插入排序希尔排序将数组分成若干个子序列每个子序列通过插入排序进行排序。由于子序列的长度较短插入排序的时间复杂度较低从而提高了排序效率。
缩小增量希尔排序通过逐步缩小增量通常采用二分法递减增量将数组分成更小的子序列进行排序。增量最终减小到1时整个数组进行一次插入排序。
大幅度减少逆序对由于希尔排序是通过间隔分组进行插入排序的每次排序都会将相距较远的元素进行比较和交换从而大幅度减少了逆序对的数量。逆序对的数量是衡量一个排序算法效率的重要指标逆序对越少排序效率越高。
非稳定性希尔排序是一种非稳定的排序算法。在排序过程中相同大小的元素可能会发生交换导致原来相对顺序的改变。尽管如此希尔排序在实际应用中并不影响排序结果的正确性。
适用场景希尔排序适用于大部分情况尤其适用于部分有序的数据集。当数据集接近有序时希尔排序的效率非常高。 六、希尔排序的优点 希尔排序的优点主要包括以下几个方面
减少比较次数希尔排序通过分组插入的方式进行排序每次比较相距较远的元素从而大幅度减少了逆序对的数量提高了排序效率。
高效处理大数据量希尔排序在处理大量数据时表现出色其时间复杂度通常为O(n^1.3)并且空间复杂度为O(1)这意味着它需要的额外空间非常小。
简单易实现希尔排序的实现相对简单易于理解和编写代码。
适用于大规模数据希尔排序特别适合处理大规模数据因为它通过分组和逐步减小增量来排序避免了直接对整个数据集进行排序的时间和空间复杂度过高的问题。
七、希尔排序的缺点
非稳定性希尔排序是一种非稳定的排序算法可能会改变相同元素的相对顺序。
性能受增量序列影响增量序列的选择对希尔排序的性能有很大影响。如果增量序列选择不当可能会导致时间复杂度退化为O(n^2)甚至更差。
时间复杂度不确定希尔排序的时间复杂度并不固定通常认为是O(n^1.3)但最坏情况下可能会更差。
七、插入排序的缺点
插入排序的主要缺点包括以下几个方面
时间复杂度较高插入排序的时间复杂度在最坏的情况下是O(n^2)其中n是待排序元素的数量。这意味着当数据量较大时插入排序的效率会显著下降不适合处理大规模数据集。
不适用于部分有序的数据虽然插入排序在数据部分有序的情况下表现较好但如果数据已经接近排序状态其他排序算法如归并排序或快速排序通常会更高效。
不稳定插入排序是一种不稳定的排序算法相同的元素在排序后可能会改变它们原有的顺序。这意味着如果输入数组中有重复的元素排序后这些元素的相对顺序可能会发生变化。
不适合实时应用由于插入排序的时间复杂度较高它不适合需要快速响应的应用场景如实时数据处理系统。
