有关希尔排序的问题。。求解答

2016/4/21镜像同步10 回复

如图，学弟最近在学数据结构时翻到希尔排序，有些疑问，求各位学长学姐同学解答。。。 1：书里只写了对Hk排序时，不会改变H（k+1）的有序性，但书里也没有什么证明。。。所以这个定理是怎么证明的。。 2：貌似对希尔排序的算法分析是通过1的定理分析的，所以想求对希尔排序的复杂度分析在网上搜了很多博客之类的，发现都没有相关的分析，求解答第一次发帖，有什么不妥的地方，望学长学姐同学包涵。。。

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

nuanyangyang机器人#1 · 2016/4/21

希尔排序的复杂度很难说，但肯定大于O(n*log(n))

m995877461机器人#2 · 2016/4/21

【在 nuanyangyang 的大作中提到: 】 : 希尔排序的复杂度很难说，但肯定大于O(n*log(n)) 最好情况比较好理解。。。就是平均情况比较难理解。。。不是很明白为什么会比插入排序快，有没有比较理论的证明呢。。。。

m995877461机器人#3 · 2016/4/22

顶

whn6325689机器人#4 · 2016/4/23

首先，希尔排序的复杂度主要受到增量的影响，那么也就是说，增量的选择决定了希尔排序的时间复杂度。其次，究竟应该选取什么样的增量才是最好，目前还是一个数学难题，迄今为止还没有人找到一种最好的增量序列。不过大量的研究表明，当增量序列为dlta[k]=2t‐k+1‐1（0≤k≤t≤.log2(n+1).）时，可以获得不错的效率，其时间复杂度为O(n^3/2)，要好于直接排序的O(n^2)。另，已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)

m995877461机器人#5 · 2016/4/23

【在 whn6325689 的大作中提到: 】 : 首先，希尔排序的复杂度主要受到增量的影响，那么也就是说，增量的选择决定了希尔排序的时间复杂度。 : 其次，究竟应该选取什么样的增量才是最好，目前还是一个数学难题，迄今为止还没有人找到一种最好的增量序列。不过大量的研究表明，当增量序列为dlta[k]=2t‐k+1‐1（0≤k≤t≤.log2(n+1).）时，可以获得不错的效率，其时间复杂度为O(n^3/2)，要好于直接排序的O(n^2)。 : 另，已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...) 请问对于希尔排序比插入排序快，或者说希尔排序的某种增量的复杂度有严格的证明吗。。。

whn6325689机器人#6 · 2016/4/24

证明有啊= =就是比较复杂 http://blog.csdn.net/u013007900/article/details/51232472 如果以后需要搜索一些学术性的东西，建议用Google 希尔排序退化之后也不见得比插入排序快多少，在某些情况下，希尔排序还是会退化成O(n^2)的啊【在 m995877461 的大作中提到: 】 : : 请问对于希尔排序比插入排序快，或者说希尔排序的某种增量的复杂度有严格的证明吗。。。

prison机器人#7 · 2016/4/24

看了一波你的博客，膜拜一下大男神【在 whn6325689 的大作中提到: 】 : 证明有啊= =就是比较复杂 : http://blog.csdn.net/u013007900/article/details/51232472 : 如果以后需要搜索一些学术性的东西，建议用Google : ...................

whn6325689机器人#8 · 2016/4/24

= =只是转载一波，其实我是有考虑翻译一下的只是最近期中太忙了，而且也在读英语【在 prison 的大作中提到: 】 : 看了一波你的博客，膜拜一下大男神

prison机器人#9 · 2016/4/24

啊，我是看了一下你博客里的其他文章，好多很不错的工程向的文章【在 whn6325689 的大作中提到: 】 : = =只是转载一波，其实我是有考虑翻译一下的 : 只是最近期中太忙了，而且也在读英语