美文网首页
希尔排序算法及分析

希尔排序算法及分析

作者: 观语小白 | 来源:发表于2020-03-28 23:22 被阅读0次

希尔排序Shell Sort

  • 我们注意到插入排序的比对次数, 在最好的情况下是O(n), 这种情况发生在列表已是有序的情况下, 实际上, 列表越接近有序, 插入排序的比对次数就越少
  • 从这个情况入手, 希尔排序以插入排序作为基础, 对无序表进行“间隔”划分子列表, 每个子列表都执行插入排序

算法思路

  • 随着子列表的数量越来越少, 无序表的整体越来越接近有序, 从而减少整体排序的比对次数
  • 间隔为3的子列表, 子列表分别插入排序后的整体状况更接近有序
  • 最后一趟是标准的插入排序, 但由于前面几趟已经将列表处理到接近有序, 这一趟仅需少数几次移动即可完成

相关文章

  • 希尔排序算法及分析

    希尔排序Shell Sort 我们注意到插入排序的比对次数, 在最好的情况下是O(n), 这种情况发生在列表已是有...

  • 排序算法(四) 希尔排序(插入排序的进化)

    参考Java排序算法(四):希尔排序常见排序算法 - 希尔排序 (Shell Sort) 希尔排序算法是按其设计者...

  • 排序算法

    排序算法 排序是最基本的算法之一,常见的排序算法有插入排序、希尔排序、选择排序、冒泡排序、堆排序、归并排序及快速排...

  • 排序算法(二)之希尔排序

    图解排序算法(二)之希尔排序 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也...

  • 排序-希尔排序(分治)

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

  • swift经典算法-希尔排序

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

  • 排序算法④——希尔排序

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

  • java实现快速排序、归并排序、希尔排序、基数排序算法...

    快速排序算法 归并排序算法 希尔排序算法 基数排序算法

  • 希尔排序学习

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

  • 排序算法-7---希尔排序

    排序算法-7---希尔排序 概念 希尔排序(Shellsort),也称递减增量排序算法,是一种典型的插入排序算法,...

网友评论

      本文标题:希尔排序算法及分析

      本文链接:https://www.haomeiwen.com/subject/zqbeuhtx.html