当前位置：首页 > news >正文

希尔排序--自学笔记

news 2026/7/28 21:50:23

希尔排序

学习目标：

一.希尔排序的思想

二.增量序列

三.复杂度分析

四.希尔排序为什么快？

五.强化练习

一.希尔排序的思想

1.将待排序数组按照一定的“间隔”分为多个子数组，

每组分别进行“插入排序”

2.逐渐缩小间隔，进行下一轮排序

3.最后一轮时，取间隔为1，相当于直接使用插入排序

但此时经过 [宏观调控] 数组已经基本有序

所以此时插入排序只需进行少量交换

代码实现

publicstaticvoidshellSort(int[]arr){for(intgap=arr.length/2;gap>0;gap/=2){for(intgroupStartIndex=0;groupStartIndex<gap;groupStartIndex++){for(intcurrentIndex=groupStartIndex+gap;currentIndex<arr.length;currentIndex+=gap){intcurrentNumber=arr[currentIndex];intpreIndex=currentIndex-gap;while(preIndex>=groupStartIndex&&arr[preIndex]>currentNumber){arr[preIndex+gap]=arr[preIndex];preIndex-=gap;}arr[preIndex+gap]=currentNumber;}}}}

目前的思路是，根据gap分组，处理完一组后，调整指针，再处理下一组

这种思路非常符合人类思维，但对于计算机而言，它更喜欢

从gap开始，依次向前，将每个数字插入到其对应的组中，

虽然数字好像在不同组间跳跃，但对于计算机就像是在访问一段连续的数组

代码优化

将第二、三个for循环整合成一个

publicstaticvoidshellSort(int[]arr){for(intgap=arr.length/2;gap>0;gap/=2){for(intcurrentIndex=gap;currentIndex<arr.length;currentIndex++){intcurrentNumber=arr[currentIndex];intpreIndex=currentIndex-gap;while(preIndex>=0&&arr[preIndex]>currentNumber){arr[preIndex+gap]=arr[preIndex];preIndex-=gap;}arr[preIndex+gap]=currentNumber;}}}

二.增量序列

1.定义

Shell排序中，每一遍排序的间隔 ‘gap’ 被称为 “增量” ，所有增量组成的序列叫做增量序列

也就是上述例子中的’5‘，’2‘，’1‘，增量是依次递减

所以Shell排序又称为缩小增量排序

增量序列的选择会极大影响Shell排序的效率！

若没有正确选择增量序列，Shell排序效率可能比插入排序更低！

如图所示，在gap = 8 , 4 , 2 时无元素交换，只有在gap = 1时才发挥了作用

而此时Shell排序相比插入排序，多做了无用功

2.一些著名的增量序列

(1) Hibbard增量序列

D_k= 2^k- 1 , 也就是 1，3，7，15，… 。

数学界猜想它最坏的时间复杂度为O(n^3/2) ，

平均时间复杂度为O(n^5/4)

(2) Knuth增量序列

D₁= 1; D_k+1= 3 * D_k+ 1，也就是 1，4，13，40，… 。

数学界猜想它的平均时间复杂度为O(n^3/2)

(3) Sedgewick增量序列

1，5，19，41，109，… 。

这个序列的元素有的是通过 9 * 4^k- 9 * 2^k+ 1 计算出来的

有的是通过 4^k- 3 * 2^k+ 1 计算出来的

并将其按照从小到大排列

数学界猜想它最坏的时间复杂度为O(n^4/3)

平均时间复杂度为O(n^7/6)

3.增量序列示例

publicstaticvoidshellSort(int[]arr){//使用Knuth增量序列//先要找出增量序列的最大值intmaxKnuthNum=1;//初始化while(maxknuthNum*3+1<arr.length){maxKnuthNum=maxknuthNum*3+1}//把值赋给gap，并修改gap变化的规律for(intgap=maxknuthNum;gap>0;gap=(gap-1)/3){for(intcurrentIndex=gap;currentIndex<arr.length;currentIndex++){intcurrentNumber=arr[currentIndex];intpreIndex=currentIndex-gap;while(preIndex>=0&&arr[preIndex]>currentNumber){arr[preIndex+gap]=arr[preIndex];preIndex-=gap;}arr[preIndex+gap]=currentNumber;}}}