赞
踩
希尔(Shell)排序法是D.L.Shell在1959年发明的一种排序法,是第⼀个突破O(n2)的排序算法,是简单插⼊排序的改进版,其排序算法类似于简单插入排序,但它可以减少数据搬移的次数。希尔排序⼜叫缩⼩增量排序。
将数据区分成特定间隔的几个小分块,以插入排序法排完区块内的数据后再逐渐减少间隔的距离。
希尔排序与直接插入排序非常相似,区别就在于直接插入排序是按照元素位置顺序进行依次判断,希尔排序是将间隔的元素进行插入,用一个实例来看:
例:
原数组元素:6 9 2 3 4 7 5 1
组中有8个元素,所以先设n=8,将其分为n/2=4个小区块,但是这几个小区块的元素并不是相连的,而是有间隔的,第一次分隔的四个小区块分别为(6, 4),
(9, 7),(2, 5),(3, 1)
将每个区块中的两个元素进行直接插入排序,得到结果的四个新的区块为:
(4, 6),(7 ,9),(2, 5),(1, 3)
第一次分块并插入排序后的数组元素为:4 7 2 1 6 9 5 3
再次缩小区块为(n/2)/2=2块,第二次分隔后的两个小区块为:(4, 2, 6, 5
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。