希尔排序
学习目标：
一.希尔排序的思想
二.增量序列
三.复杂度分析
四.希尔排序为什么快？
五.强化练习
一.希尔排序的思想
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增量序列
Dk= 2k- 1 , 也就是 1，3，7，15，… 。
数学界猜想它最坏的时间复杂度为O(n3/2) ，
平均时间复杂度为O(n5/4)
(2) Knuth增量序列
D1= 1; Dk+1= 3 * Dk+ 1，也就是 1，4，13，40，… 。
数学界猜想它的平均时间复杂度为O(n3/2)
(3) Sedgewick增量序列
1，5，19，41，109，… 。
这个序列的元素有的是通过 9 * 4k- 9 * 2k+ 1 计算出来的
有的是通过 4k- 3 * 2k+ 1 计算出来的
并将其按照从小到大排列
数学界猜想它最坏的时间复杂度为O(n4/3)
平均时间复杂度为O(n7/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;}}}三.复杂度分析
由于增量序列会极大影响Shell排序的效率
时间复杂度：平均时间复杂度介于O(n)到O(n2)
普遍认为最好的时间复杂度为O(n1.3)
空间复杂度：O(1) 只需要常数级的临时变量
四.希尔排序为什么快？
1.“逆序对”概念引入
当我们从小到大排序时，在数组中的两个数字，如果前面一个数字大于后面的数字
则这两个数字组成一个逆序对
而所有排序算法的本质都是：消除逆序对
对于随机的数组，逆序对的数量是O(n2)级的
如果使用交换相邻元素的方法来消除逆序对，每次只能消除一组逆序对
所以交换的次数是O(n2)级的
这就是冒泡、选择、插入排序算法时间复杂度只能达到O(n2)的原因
而基于交换元素的排序算法 ( 空间复杂度为O(1) ) 想突破O(n2)，必须通过一些比较，交换间隔比较远的元素
也就是需要在一次交换中能够消除一个以上的逆序对
Shell排序算法就是如此
此后的快排、堆排也是如此…
五.强化练习
506. 相对名次 - 力扣（LeetCode）
杂度为O(1) ) 想突破O(n2)，必须通过一些比较，交换间隔比较远的元素
也就是需要在一次交换中能够消除一个以上的逆序对
Shell排序算法就是如此
此后的快排、堆排也是如此…
五.强化练习
506. 相对名次 - 力扣（LeetCode）
912. 排序数组 - 力扣（LeetCode）
