¶Shell Sort 希尔排序
分组插入排序:设置步长,将数组分为几组,将分割的两部分混合对应放在一起,对每组进行插入排序
==步长为1时,希尔排序变成了插入排序==
算法时间复杂度:O(nlogn) ~ O(n * n)
空间复杂度:O(1)
思考:gap每次将长度为N的列表分为N/2
部分,a[0]
和a[N/2 +1]
比较交换,接着合并再分割为N/4
,知道最后变为1的时候开始相邻的数字进行左右交换。
1 | import java.util.Arrays; |
分组插入排序:设置步长,将数组分为几组,将分割的两部分混合对应放在一起,对每组进行插入排序
==步长为1时,希尔排序变成了插入排序==
算法时间复杂度:O(nlogn) ~ O(n * n)
空间复杂度:O(1)
思考:gap每次将长度为N的列表分为N/2
部分,a[0]
和a[N/2 +1]
比较交换,接着合并再分割为N/4
,知道最后变为1的时候开始相邻的数字进行左右交换。
1 | import java.util.Arrays; |