[已解决]希尔排序和插入排序

飞花落尽

为什么说希尔排序是插入排序的优化？最后不都要经历步进值为1的排序吗?
还有这几个名词是什么意思？
时间复杂度：O(n2)
最优时间复杂度：O(n)
平均时间复杂度：O(n2)
空间复杂度：总共 O(n)，需要辅助空间 O(1)

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2021-12-1 21:45:52

一般刷题都会有若干参数数据作为测试，为了测试代码是否最优，参数一般都会设超级大的数值作为测试，比如某某参数 n (1 <= n <= 100000）之类的，这时时间复杂度就起很大作用了。
时间复杂度其实和时间没有直接关系，时间复杂度是以 1 循环次数作为 1 单位计算，简单的说就是你的代码需要循环多少次可以得出答案？
而空间复杂度顾名思义就是空间单位用量，和记忆大小没有关系，空间复杂度是以 1 变量作为 1 单位计算，简单的说就是不管你的代码变量类型是什么，大小多少无所谓，1 个变量 1 单位空间复杂度。
大写 O 符 表示时间复杂度或空间复杂度（有时空间复杂度也用 S 替代），括号里面表示单位，n 为参数变量。

O(n2) 表示 时间复杂度为 n 次方
而 O(n) 表示 时间复杂度为 n
一般指的是 for 循环嵌套另一个 for 循环，最坏可能必须循环 n*n 次才得到答案，最快可能则只需循环 n 次便得出答案。（一般时间复杂度必然是取最坏可能作为基准）

跳转到最佳答案楼层

傻眼貓咪

一般刷题都会有若干参数数据作为测试，为了测试代码是否最优，参数一般都会设超级大的数值作为测试，比如某某参数 n (1 <= n <= 100000）之类的，这时时间复杂度就起很大作用了。
时间复杂度其实和时间没有直接关系，时间复杂度是以 1 循环次数作为 1 单位计算，简单的说就是你的代码需要循环多少次可以得出答案？
而空间复杂度顾名思义就是空间单位用量，和记忆大小没有关系，空间复杂度是以 1 变量作为 1 单位计算，简单的说就是不管你的代码变量类型是什么，大小多少无所谓，1 个变量 1 单位空间复杂度。
大写 O 符 表示时间复杂度或空间复杂度（有时空间复杂度也用 S 替代），括号里面表示单位，n 为参数变量。

O(n2) 表示 时间复杂度为 n 次方
而 O(n) 表示 时间复杂度为 n
一般指的是 for 循环嵌套另一个 for 循环，最坏可能必须循环 n*n 次才得到答案，最快可能则只需循环 n 次便得出答案。（一般时间复杂度必然是取最坏可能作为基准）

飞花落尽

傻眼貓咪 发表于 2021-12-1 22:12
一般刷题都会有若干参数数据作为测试，为了测试代码是否最优，参数一般都会设超级大的数值作为测试，比如某 ...

那还有一个这个问题：为什么说希尔排序是插入排序的优化？最后不都要经历步进值为1的排序吗?

lightninng

飞花落尽 发表于 2021-12-2 00:00
那还有一个这个问题：为什么说希尔排序是插入排序的优化？最后不都要经历步进值为1的排序吗?

当你使用随机存取的数据结构时（比如数组），每次插入都需要移动数据，当当前插入的数据位置比较靠前时，需要移动大量的数据，最坏情况是倒序时，每次都要将当前插入完成的数据都往后移动一位。
希尔排序通过步长将数据分组，然后在分组内做插入排序，绝大部分情况下它在插入时需要移动的数据数量会比直接插入排序要少。
为了有个直观的感觉，楼主可以试一下54321这个5元素序列用两种排序方法分别需要移动多少次序列中的元素

另外时间复杂度和空间复杂度中n^2和n并不是指它使用的时间是n^2或者n而是，这个时间或空间是和n^2或n同数量级的，换句话说，只能不同的序列情况这个时间或者空间复杂度不会有指数级上的差别，而只是几何级的差距~

飞花落尽

lightninng 发表于 2021-12-2 07:56
当你使用随机存取的数据结构时（比如数组），每次插入都需要移动数据，当当前插入的数据位置比较靠前时 ...

所以不发生移动（只是判断）就不算他的时间复杂度是吗？
（就比如判断A[j+1]>A[j]）

lightninng

飞花落尽 发表于 2021-12-2 15:59
所以不发生移动（只是判断）就不算他的时间复杂度是吗？
（就比如判断A[j+1]>A[j]）

不是的，实际上计算时间复杂度的时候，是通过计算重复最多的语句的频次来判断的，但是频次也不是时间复杂度，而是频次中影响重复次数最大的那一项且不含系数，比如某个语句在程序中重复了n^2+2n+1次，另一个程序的某个语句重复了2n^2+4n+5。两个程序的频次分别是n^2+2n+1和2n^2+4n+5，但是时间复杂度都是O(n^2)

lightninng

飞花落尽 发表于 2021-12-2 15:59
所以不发生移动（只是判断）就不算他的时间复杂度是吗？
（就比如判断A[j+1]>A[j]）

建议系统学一下数据结构这门课，推荐清华大学出版社出的，严蔚敏老师出的《数据结构（C语言版）》，内容非常严谨，如果能跟着都实现一遍，对于数据结构的学习帮助非常大~~~

tomok

学习 收藏

飞花落尽

lightninng 发表于 2021-12-2 17:15
不是的，实际上计算时间复杂度的时候，是通过计算重复最多的语句的频次来判断的，但是频次也不是时间复杂 ...

好的，谢谢