希尔排序

文章目录[x]
  1. 1:希尔排序
  2. 2:算法步骤
  3. 3:算法演示
  4. 4:排序动画过程解释

希尔排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

算法步骤

  1. 选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
  2. 按增量序列个数 k,对序列进行 k 趟排序;
  3. 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

来源:https://github.com/hustcc/JS-Sorting-Algorithm

算法演示

排序动画过程解释

  1. 首先,选择增量 gap = 10/2 ,缩小增量继续以 gap = gap/2 的方式
  2. 初始增量为 gap = 10/2 = 5,整个数组分成了 5 组
  3. 按颜色划分为【 8 , 3 】,【 9 , 5 】,【 1 , 4 】,【 7 , 6 】,【 2 , 0 】
  4. 对这分开的 5 组分别使用上节所讲的插入排序
  5. 结果可以发现,这五组中的相对小元素都被调到前面了
  6. 缩小增量 gap = 5/2 = 2,整个数组分成了 2 组
  7. 【 3 , 1 , 0 , 9 , 7  】,【 5 , 6 , 8 , 4 , 2  】
  8. 对这分开的 2 组分别使用上节所讲的插入排序
  9. 此时整个数组的有序性是很明显的
  10. 再缩小增量 gap = 2/2 = 1,整个数组分成了 1 组
  11. 【 0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0  】
  12. 此时,只需要对以上数列进行简单的微调,不需要大量的移动操作即可完成整个数组的排序

转载自:https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247483989&idx=1&sn=0b218fa5f66ee26438dd0dd5e19a49b2&chksm=fa0e6dd4cd79e4c2e112063e2483f88cfeab7765b41216df8bd9d175ef4a38b0b3ed4b59d667&scene=21#wechat_redirect

点赞

发表评论