数据结构--希尔排序

目录

希尔排序的定义 

给一个序列进行希尔排序 

 希尔排序的算法实现

 算法性能分析

1.时间复杂度

2.稳定性 

3.适用性 

知识点回顾

---

希尔排序的定义 

 

给一个序列进行希尔排序 

 

第一趟d可以是元素个数/2

相距为4的子表

 

对子表进行直接插入排序（由小到大）

 

 

得到结果是

 

第二趟相距为2的元素为一组

 

 相距为2的子表

 

对子表进行直接插入排序（由小到大） 

第二趟得到结果是

 

第三趟d=1，相距为1的元素为子表，正好就是所有的元素，整个表已经呈现出“基本有序”，对整体在进行一次“直接插入排序”

 第三趟的子表

 

第三趟子表排序后的结果

 

 希尔排序的算法实现

 

 算法性能分析

1.时间复杂度

 

2.稳定性 

不稳定

3.适用性 

仅适合于顺序表，不适用于链表

知识点回顾