工业和信息化部网站备案管理系统,信誉好的大良网站建设,做一个个人网页多少钱,网站建设四端一体文章目录 前言一、希尔排序的演示图例二、希尔排序#xff1a;插入排序的优化版本☆三、核心算法思路四、算法思路步骤#xff08;一#xff09;预排序 gap1#xff08;二#xff09;gap1 插入排序 完成排序收尾 五、码源详解#xff08;1#xff09;ShellSort1 ——… 文章目录 前言一、希尔排序的演示图例二、希尔排序插入排序的优化版本☆三、核心算法思路四、算法思路步骤一预排序 gap1二gap1 插入排序 完成排序收尾 五、码源详解1ShellSort1 —— gap组 轮完一组再接下一组2ShellSort2 —— 多组并排 【关于gap幅度的选择】六、效率分析1时间复杂度 ON^ 1.3和ON*logN是一个量级的可能ON^ 1.3会略差于ON*logN稳定性不稳定 前言
前面我们学习了直接插入排序我们可知道一个特点当插排接近有序时会非常的高效 。因此希尔研究出的希尔排序令插排前面的数据更接近有序就更高效。效率远超预期。 一、希尔排序的演示图例 二、希尔排序插入排序的优化版本
希尔排序Shell Sort是一种排序算法由美国计算机科学家Donald Shell于1959年提出。希尔排序是插入排序的一种改进版本Shell从插入排序中感悟到了插入排序只要保持 要调整待插入的数据的前面的数据越有序排序的效率就越高旨在减少插入排序的交换操作和比较次数从而提高排序效率。这个算法的名字是以发明者的名字命名的虽然它也被称为 “递减增量排序” 。 ☆三、核心算法思路
希尔排序法 又称 缩小增量法 。
基本思路 先选定一个整数 gap间距把待排序文件中所有记录分成gap个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后取gapgap/2 或 gapgap/31 ( 增量逐渐递减 )重复上述分组和排序的工作。当gap到达1时所有记录在统一组内排好序插入排序。
旨在通过 将间距为gap的数据之间的插入排序 将大的数据通过 间距gap的插入排序 更快的甩到后面去小的数据甩到前面来 使待排序的序列在gap增量递减到1之前 [也就是在真正的插入排序之前] 使数据更接近有序让最后一次gap1时的插入排序实现高效排序。 四、算法思路步骤
一预排序 gap1
分组排间距为 gap 的数据都分为一组 共有 gap 组gap的间隔中就是分好的组数间距为 gap 的数据都分为一组每组数据进行单趟间距为gap的插入排序。和插入排序的思路一样但能让大的数据通过间距gap更快的甩到后面去小的数据更快的到前面来增量递减 gapgap/2 或 gapgap/31一般取这个 [ gap随n变化 ]进行多次预排序【gap递减的幅度也是有讲究的请看下文 】gap越大跳的越快越不接近有序gap越小越慢越接近有序一点。
多次预排的意义让大的数据更快的到后面去让小的数更快的到前面来。
二gap1 插入排序 完成排序收尾
当 gap1 时就是插入排序。完成全部数据的排序。这时的数据已经非常接近有序了这时的插入排序将会非常高效 五、码源详解
1ShellSort1 —— gap组 轮完一组再接下一组
运用两层循环
外层循环控制轮到的组号内层循环控制一组内间隔为gap之间数据的比较
//希尔排序 —— 一组一组轮
void ShellSort(DataType* a, int n) {int gap n;while (gap 1) {//gap gap / 2;gap gap / 3 1; //1确保除到最后gap1 //gap根据n的大小进行变化 //gap也能取n/2最终除出来一定为1//将 数组中 间隔为gap的数分为一组共分为gap组间隔的数据中间的个数便是所有已经分好的组数//一组一组遍历for (int j 0; j gap; j) {//每组进行遍历for (int i j; i n - gap; i gap) {int end i;int tmp a[end gap]; //先将要移的数先保存起来前面发生挪动会将其覆盖while (end 0) { //向前遍历完if (tmp a[end]) { //比tmp大就往后移a[end gap] a[end];end - gap; //再继续向前比较}else {break;}a[end gap] tmp;}}}}
}注意边界问题建议大家套值进去试不容易出错。
2ShellSort2 —— 多组并排
一组排完第一个gap就跳到另一组排另一组的第一个gap每组都一部分一部分地排
//希尔排序 —— 多组并排
void ShellSort(DataType* a, int n) {int gap n;while (gap 1) {//gap gap / 2; //gap也能取n/2最终除出来一定为1gap gap / 3 1; //1确保除到最后gap1 //gap根据n的大小进行变化 for (int i 0; i n - gap; i) {int end i;int tmp a[end gap];while (end 0) {if (tmp a[end]) {a[end gap] a[end];end - gap; //希尔排序的本质还是插入排序end从前往后每个end都向前遍历一次遍历与其间隔gap的数只不过是先通过gap分组来排出个相对有序然后实现更高效的插入排序}else {break;}a[end gap] tmp; //若发生了值的交换 end-gap后 再加上gap 就是现在end的位置就是将小的tmp值换到现在end的位置//若当前没有发生值的交换则让tmp储存下一个相距gap的值 a[endgap]让下一个值再进行 向前比较遍历}}}
}【关于gap幅度的选择】
《数据结构-用面相对象方法与C描述》— 殷人昆
gap越大跳的越快越不接近有序gap越大能让大和小数据更快地到两边。 gap越小越慢越接近有序一点。
相比之下gapgap / 3 1 是比较适合的大小
int gap n;while (gap 1) {//gap gap / 2;gap gap / 3 1; //1确保除到最后gap1 //gap根据n的大小进行变化 //gap也能取n/2最终除出来一定为1六、效率分析
1时间复杂度 ON^ 1.3和ONlogN是一个量级的可能ON^ 1.3会略差于ONlogN
希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定:
《数据结构(C语言版)》— 严蔚敏
《数据结构-用面相对象方法与C描述》— 殷人昆 因为咋们的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按照O(n^1.25)到 O(1.6* n^1.25) 来算。
结论ON^ 1.3 以 gapN / 3 为例有N/3组数据每组里有3个数据进行比较每组比3次 一个gap 比较N/3 * 3 N次但其中并不是都要交换 N^2 N^1.3 (N*logN).
稳定性不稳定
呈如图这样的趋势先增大中间性能增大再回复到小。
是个数学问题 复变函数 图中的变化参数 大概为 log2 N底数为2
