求希尔排序的时间空间复杂度。。。还有要是可能的话给讲解下是怎么个回事吧，弄晕了。。谢谢、、、

Question

如题所述

Answer 1

你好，希尔排序的时间复杂度是O（n的1.25次方）~O(1.6n的1.25次方) 这是一个经验公式，好像没人解释过，就是一句经验得出的。（不好意思。。没解释出来）
空间复杂度是O（1） 因为只有一个缓冲单元。
希望对你有帮助。
希尔排序的算法：
Void ShellInsert(Sq:ost&L,int dk){
For(i=dk+1;i<=L.length;++i)
If(LT(L.r[i].kye,L.r[i-dk].key)){
L.r[0]=L.r[i];
For(j=i-dk;j>0&<(L.r[0].key,l.r[j].key);j-=dk)
L.r[j+dk]=L.r[j];
L.r[j+dk]=L.r[0];
}
}//ShellInsert本回答被提问者采纳