间复杂性分析

排序算法在计算机科学中扮演着至关重要的角色对于数据的组织和搜索等任务有着深远的影响。

希尔排序是一种插入排序的改进版本通过引入增量的概念能够在某些情况下显著提高排序的效率。

希尔排序算法原理

Shell于1959年提出。

其核心思想是将待排序的记录按下标的一定增量分组对每组使用直接插入排序方法随着增量逐渐减小每组包含的记录越来越多直至增量为1时整个序列恰好被分成一个组排序完成。

2.1

对每个组使用直接插入排序算法进行排序。

然后取增量值为4将文件分成4个组

组1:

再次对每个组使用直接插入排序。

重复这个过程取增量值为2和1最终完成整个排序。

2.2

希尔排序的性能与所选取的分组长度序列密切相关。

最坏情况下的时间复杂度为

O(n^2)

O(n2)。

实际应用中取2.2作为递减因子效果更好。

当分组长度序列取形如

2^p3^q

{1,4,10,23,57,132,301,701,1750,...}具有此分组序列的希尔排序比插入排序和堆排序要快。

在小数组情况下比快速排序快但对于大数组则可能比快速排序慢。

此外希尔排序是不稳定的排序算法。

实验内容

对每组输入数据输出以下信息要求必须要有关于输出数据的明确的提示信息:

输出整个排序过程总的关键词比较次数和总的记录移动次数每发生一次记录插入输出整个文件一次输出增量为

7、5、3、1

//对各组做直接插入排序rR[i];ji;while(jd-1R[j-d]r){compare;R[j]R[j-d];j-d;}if(j!i){move;R[j]r;for(k0;kn;k){printf(%d

R[k]);}printf(\n);}

}printf(\n增量值为%d时的关键词比较次数是%d记录移动次数是%d\n\n,d,compare,move);dd-2;

//计算新的增量值,{7531}Comparecompare;Movemove;}printf(关键词的总比较次数是%d总的记录移动次数是%d\n,Compare,Move);

int

R[n]{27,32,33,21,57,96,64,87,14,43,15,62,99,11};int

R[n]{11,14,15,21,27,32,33,43,57,62,64,87,96,99};//int

R[n]{99,96,87,64,62,57,43,33,32,27,21,15,14,11};ShellSort(R);printf(最后结果);for(i0;in;i){printf(%d

,R[i]);}

R表示待排序的数组。

在函数内部通过不断缩小增量的方式对数据进行插入排序。

具体来说在每一轮循环结束后更新增量的值采用一定的方式递减。

这里选择减小2的增量序列

{7,

d并在每一轮循环中进行插入排序。

增量的选择是关键这里初始设置为7然后逐渐减小。

for

}在插入排序的过程中通过比较和移动元素确保分组内的元素是有序的。

输出结果

printf(\n增量值为%d时的关键词比较次数是%d记录移动次数是%d\n\n,

compare,

move);在每一轮排序结束后输出该轮排序的比较次数和记录移动次数从而了解算法在不同步长下的性能。

printf(关键词的总比较次数是%d总的记录移动次数是%d\n,

Compare,

Move);在整个排序完成后输出总的比较次数和记录移动次数提供了算法整体性能的信息。

主函数

R[n]{27,32,33,21,57,96,64,87,14,43,15,62,99,11};//

int

R[n]{11,14,15,21,27,32,33,43,57,62,64,87,96,99};int

R[n]{99,96,87,64,62,57,43,33,32,27,21,15,14,11};ShellSort(R);printf(最后结果);for(i0;in;i){printf(%d

,R[i]);}

希尔排序是一种高效的排序算法通过引入增量的方式能够在某些情况下显著提高插入排序的性能。

选择合适的分组长度序列对算法的实际效果有重要影响而已知的最佳序列

132

{1,4,10,23,57,132,301,701,1750,...}在实践中表现优异。

需要注意的是希尔排序是不稳定的排序算法。

在实际应用中根据数据规模和特性选择不同的排序算法是很重要的希尔排序在一些场景下可能比其他排序算法更适用。

希尔排序的性能对于分组长度序列的选择非常敏感因此在实际使用中需要根据具体情况进行调优。