希尔排序(Shell Sort)算法学习
希尔排序是对插入排序的改进。 如果把排序的过程看作消除序列中 逆序对 的过程，那么排序的最终结果就是序列中没有逆序对。 普通的插入排序每次交换相邻元素，一次交换只能消除一个逆序对; 希尔排序允许交换相距一定间隔的元素，一次交换可以消除多个逆序对，因此速度更快。
算法步骤
希尔排序要使用一个序列{\(h_1\), \(h_2\),..., \(h_k\), }， 称为增量序列，其中\(h_1\)必须是1，如果\(i \lt j，则h_i \lt h_j\)， 还有就是每一项都不大于序列的长度。好的增量序列能显著改善算法性能。
算法的具体步骤描述如下：
- 取增量\(h_i\)，其中i = k，即增量序列中的最后一项。
- 增量\(h_i\)逻辑上把待排序序列分成\(h_i\)个子序列， 每个子序列由所有相距\(h_i\)的元素组成。
- 对每个子序列进行插入排序。这个排序步骤在Sedgewick的《Algorithms，4th edition》中叫做h-sort。
- 令i=i - 1，重复2，3步骤，直到\(h_i\) = 1。
在最后增量为1的时候进行的就是普通的插入排序，此时大部分逆序都已经被消除了， 因此这次插入排序的速度非常快。一般的实现中可以把增量序列单独作为数组存放，也可以使用表达式"生成"。
下面实现(C语言)改编自《Algorithms，4th edition》中的实现:
/*希尔排序*/
void shell_sort(int arr[], int length)
{
int h = 1, i, j;
// 计算增量的最大值，不超过数组长度的1/3.
while (h < length / 3)
{
// 这个就是"生成"增量序列的表达式
h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093...
}
while (h >= 1)
{
// h-sort 步骤
for (i = h; i < length; i++)
{
// 对一个"子序列"进行插入插排
for (j = i; j >= h; j -= h)
{
if (arr[j] < arr[j - h])
{
int tmp = arr[j];
arr[j] = arr[j - h];
arr[j - h] = tmp;
}
}
}
h = h / 3;
}
}
增量序列的好坏直接影响算法的性能。 有许多已知的比较好的序列，目前最好增量序列据说是由Sedgewick提出的：{1, 5, 19, 41, 109,...}， 其中有些项由\(9 * 4^i - 9 * 2^i + 1\)计算得到，另一些由\(4^i - 3 * 2^i + 1\)计算得到。
希尔排序的代码实现并不复杂，但是其时间复杂度的分析就相当复杂。 希尔排序的时间复杂度直接依赖于增量序列的选择。对希尔排序的的平均情形的分析， 除了最平凡的一些增量序列之外，是一个长期未能解决的难题。
2020年4月23日 06:06
Very helpful blog post! There is a great deal of information here that can assist any organisation get started with an effective social networking campaign. Funny Wifi Names 2020
2020年4月28日 05:24
I desire you to say thanks to for your time of this terrific read!!! I most definitely take pleasure in every little of it as well as I have you bookmarked to take a look at brand-new stuff of your blog a must-read blog site!
2020年5月01日 09:10
I also think this s an extremely remarkable website. I will check out again for even more top quality web content as well as likewise, suggest this site to all. Thanks. kbc winner
2020年5月02日 05:27
I value this article for the well-researched web content and superb phrasing.
I got so thinking about this product that I couldn't quit checking out.
Your blog is actually impressive. jio lottery winner,kbc lottery
2020年5月02日 20:25
These specific papers remarkable,
as well as My spouse and also I take pleasure in each of the perform that you have positioned into this.
I'm sure that you will be making a really helpful location.
I have been furthermore happy. Good carry out! kbc lottery
2020年5月08日 14:21
Pretty wonderful article. I just stumbled upon your weblog and also wished to claim that I have actually truly taken pleasure in browsing your post. I'll be subscribing to your feed and also I wish you write once more quickly! kbc head office number
2020年5月08日 15:30
Extremely good write-up, I delighted in reading your article, very wonderful share, I wish to twit this to my fans. Many thanks! kbc winner
2020年5月08日 15:34
Hi there,
I discovered your site by means of Google while looking for a related subject,
your site showed up, it looks excellent. I have actually bookmarked
it in my google book markings. kbc lottery winner
2020年5月08日 16:03
I desire you to thank for your time of this remarkable read!!! I most definitely appreciate every bit of it as well as I have you bookmarked to look into brand-new things of your blog site a must-read blog site! kbc lottery
2020年5月11日 23:19
I obtained way too much fascinating things on your blog. I think I am not the just one having all the pleasure right here! Maintain up the good work. kbc
2020年5月11日 23:37
Believe it or otherwise, it is the kind of info I've long been looking for. It matches my requirements a great deal. Thank you for creating this details. kbc registration
2020年5月11日 23:57
I check out a whole lot of blog posts, however I never ever heard a topic like this. I Love this topic you made regarding the blog owner's container checklist. kbc lottery
2020年5月23日 09:45
These specific papers fabulous, and also My spouse and I delight in each of the carry out that you have put right into this. I'm certain that you will certainly be making an actually valuable location. I have actually been in addition happy. Good carry out! kbc winner list
2020年5月23日 09:57
I review a lot of blog posts, yet I never listened to a subject like this. I Love this subject you made concerning the blogger's pail listing. kbc lottery winner
2020年5月23日 10:30
Sensational post. This isn't normally a horrendous post and also gives complete info. I like to check this message considering I met such a lot of brand-new authentic elements concerning it actually. Many thanks, lots. I bookmark your web log in light of I found dumbfounding details on your weblog, Thanks for sharing. kbc contact number
2020年5月23日 10:42
Favorable site, where did u create the details on this posting? I have actually checked out a few of the write-ups on your site now, and also I truly like your style. Thanks a million as well as please maintain the efficient work. kbc lottery winner
2020年5月23日 11:10
Really good write-up, I enjoyed reviewing your blog post, extremely great share, I wish to twit this to my fans. Thanks! kbc lottery
2020年5月25日 14:47
Very great blog site as well as posts. I am truly very pleased to see your blog site.
Now I am located which I really want. best free email marketing
2020年5月28日 12:04
Amazing article. I such as to examine this post considering I fulfilled such a whole lot of brand-new genuine elements worrying it truly. jio lottery 2020
2020年5月28日 12:07
Exceptional article. I was always examining this blog site, and I'm pleased! Extremely valuable info particularly the last component, I care for such details a whole lot. I was discovering this certain information for a lengthy time. Many thanks to this blog site my expedition has actually ended. kbc winner 2020
2020年6月05日 06:49
Remarkable post. I such as to check this blog post considering I satisfied such a whole lot of new genuine parts worrying it really. kbc winner list
2020年6月05日 07:51
I examine your blog every day and attempt to learn something from your blog site. Thank you as well as waiting for your new post. kbc lottery winner
2020年6月05日 10:03
Efficiently created info. It will be profitable to any person who uses it, counting me. Maintain the great. For certain I will certainly examine out more blog posts an everyday. kbc contact number
2020年6月05日 10:07
The most effective article I stumbled upon a variety of years, create something concerning it on this web page. kbc lottery winner
2020年6月05日 11:15
I actually delighted in analysis this message, big fan. Maintain the great work and please tell me when can you publish much more posts or where can I check out more on the subject? kbc lottery
2020年6月05日 11:18
Outstanding web site! I am examining just how I may be informed whenever a brand-new article has actually been made. kbc winner 2021
2020年6月05日 11:20
Thanks for sharing great information with us. I like your blog post and also all you share with us is up to date and also rather informative, I want to bookmark the web page so I can come right here once again to read you, as you have actually done a wonderful job. jio lottery 2021
2020年6月07日 06:54
Superior message, keep up with this outstanding job. It's good to know that this subject is being additionally covered on this website so cheers for taking the time to review this! Many thanks time and again! best dog training collars
2020年6月12日 10:46
Superior post, stay on par with this remarkable work. It's wonderful to understand that this subject is being additionally covered on this website so joys for making the effort to discuss this! Many thanks over and over! kbc lottery 2021
2020年6月12日 11:29
The most effective write-up I discovered a number of years, create something regarding it on this page. kbc head office number
2020年6月12日 11:52
I want you to give thanks to for your time of this fantastic read!!! I absolutely delight in every bit of it and I have you bookmarked to take a look at new things of your blog site a must-read blog site! jio lottery winner
2020年6月12日 13:12
Excellent website! I adore just how it is very easy on my eyes it is. I am questioning how I could be notified whenever a brand-new blog post has been made. Looking for even more new updates. Have a fantastic day! kbc lottery winner 2021
2020年6月12日 13:16
Thanks for sharing nice info with us. I like your blog post and all you share with us depends on date as well as fairly useful, I want to bookmark the page so I can come here once again to read you, as you have actually done a wonderful job. kbc lucky draw 2021
2020年6月12日 13:55
It is really a well-researched material and also exceptional wording. I obtained so taken part in this material that I couldn't wait to read. I am satisfied with your work and also ability. Many thanks. kbc winner list
2020年6月12日 13:58
I can not wait to dig kickoff and also deep utilizing resources that I obtained from you. Your liveliness is rejuvenating. kbc head office number
2020年6月15日 06:25
I value this write-up for the well-researched material and also exceptional wording. I got so curious about this product that I could not stop reading. Your blog is truly outstanding. כנסו לאתר
2020年7月06日 18:51
Exceptional website! I am examining exactly how I could be informed whenever a new article has been made. קאמאגרה
2020年7月10日 05:12
I'm certain that you will be making a truly beneficial place. Good perform! kbc lucky draw 2021
2020年7月10日 05:14
You really make it look so easy with your performance however I discover this matter to be in fact something which I think I would certainly never ever understand. It appears incredibly broad and also as well complicated for me. I'm expecting your following post, I'll try to obtain the hang of it! kbc lottery winner 2021
2020年7月11日 04:46
I really took pleasure in reading this article, big follower. Maintain the great as well as please inform me when can you publish more articles or where can I read a lot more on the subject? kbc winner list
2020年7月11日 04:46
Routine sees provided here are the easiest approach to value your energy, which is why I am mosting likely to the web site on a daily basis, looking for new, fascinating details. Thank you! kbc official website
2020年7月15日 07:00
Think it or not, it is the kind of information I've long been searching for. It matches my requirements a lot. Thanks for creating this info. kbc lottery 2021
2020年7月16日 04:16
Believe it or otherwise, it is the sort of info I've long been searching for. It matches my needs a whole lot. Thank you for composing this details. kaun banega crorepati lottery check
2020年7月16日 05:19
Great article but I was wondering if you could compose a little a lot more on this topic? I would certainly be really happy if you might specify a bit further. Appreciate it! 网课代写
2020年7月16日 05:22
These specific documents fabulous, as well as My partner and also I delight in each of the do that you have actually positioned into this. I'm sure that you will be making an actually beneficial location. I have actually been in addition delighted. Great do! paragonpoker
2020年7月16日 19:09
Hi there, I located your web site via Google while looking for a related topic, your web site came up, it looks fantastic. I have bookmarked it in my google book markings. kbc whatsapp number
2020年7月17日 18:58
These certain papers fabulous, as well as My spouse as well as I appreciate each of the carry out that you have put right into this. I'm sure that you will be making a truly helpful place. I have actually been in addition pleased. Excellent perform! kbc lottery check up
2020年7月19日 06:10
These particular documents incredible, as well as My partner as well as I delight in each of the carry out that you have put right into this. I'm certain that you will certainly be making a really useful area. I have actually been additionally happy. Great execute! Hppoker
2020年7月19日 06:13
You in fact make it look so easy with your performance however I discover this issue to be in fact something which I believe I would certainly never understand. It seems incredibly broad and also challenging for me. I'm looking ahead to your next article, I'll try to get the hang of it! mybestpoker
2020年7月19日 06:15
Very wonderful article, I took pleasure in reading your post, really wonderful share, I intend to twit this to my fans. Thanks! Lexispoker
2020年7月21日 06:09
I can not wait to dig deep as well as kickoff making use of sources that I received from you. Your spirit is rejuvenating. Judi Slot Online
2020年7月26日 05:31
I'm sure that you will certainly be making a truly beneficial location. Excellent do! Jio 25 Lakh Lottery Winner List
2020年7月26日 05:36
You in fact make it look so easy with your efficiency but I locate this matter to be actually something which I assume I would certainly never comprehend. It appears incredibly wide and also challenging for me. I'm looking forward to your following blog post, I'll attempt to get the hang of it! kbc prize winner file
2020年7月26日 05:36
Keep up the great; I review a couple of messages on this web site, including I think about that your blog site is remarkable as well as has collections of fantastic item of info. Many thanks for your important efforts. dndpoker
2020年7月27日 05:21
I really delighted in analysis this message, huge follower. Maintain up the great and also please tell me when can you release extra short articles or where can I review more on the subject? kbc new year lucky draw 2020
2020年7月27日 05:21
Normal sees listed right here are the most convenient approach to appreciate your power, which is why I am going to the website everyday, looking for brand-new, fascinating details. Thanks! kbc jio lottery winner
2020年8月08日 22:47
I actually like your composing style, great info, thankyou for uploading. 먹튀검증사이트
2020年8月08日 22:47
Exceptional web site! I adore exactly how it is easy on my eyes it is. I am examining exactly how I may be informed whenever a brand-new post has actually been made. Seeking even more brand-new updates. Have a great day! 먹튀커머스
2020年8月12日 16:37
Fabulous article, you have actually represented out some wonderful points, I similarly assume this s a really remarkable internet site. I will certainly visit once more for more high quality material and additionally, advise this website to all. Many thanks. แทงบอลออนไลน์
2020年9月08日 21:17
Live vs . Patriots Live Stream . Steelers Live Stream . Broncos Live Stream . Cowboys Live Stream . Packers Live Stream .
2020年9月10日 22:06
I truly appreciated analysis this article, huge follower. Maintain up the great and also please tell me when can you release a lot more articles or where can I review a lot more on the subject? บุหรี่ไฟฟ้า
2020年9月24日 03:45
Superior blog post, stay on top of this remarkable job. It's nice to know that this topic is being also covered on this internet site so joys for making the effort to discuss this! Thanks time and again! QR Code Generator
2020年10月27日 06:26
This article was composed by a genuine reasoning writer undoubtedly. I concur on much of them with the solid factors made by the author. I'll be back day in as well as day for further brand-new updates. radio app
2020年11月09日 22:29
Fantastic job right here on. I read a whole lot of article, yet I never listened to a subject such as this. I Love this subject you made concerning the blog writer's container listing. Really resourceful. 卡式台胞證
2020年11月11日 10:37
Fabulous message, you have represented out some wonderful points, I also believe this s a very terrific site. I will go to once more for more high quality web content and additionally, suggest this site to all. Thanks. 臺胞證
2021年1月19日 06:20
Fabulous blog post, you have actually signified out some fantastic factors, I furthermore assume this s a very terrific web site. I will certainly go to once more for more quality web content as well as likewise, recommend this site to all. Many thanks. notes
2021年4月09日 13:46
This write-up was composed by an actual reasoning writer undoubtedly. I settle on a number of them with the solid points made by the author. I'll be back day in and also day for more new updates. framing a basement
2021年5月09日 02:56
The very best short article I encountered a number of years, compose something about it on this page. Relx
2021年6月24日 04:45
Wonderful job below on. I check out a great deal of post, however I never ever heard a subject such as this. I Love this subject you made concerning the blogger's pail checklist. Extremely clever. Tech Politics Economy Latest News https://eprimefeed.com/ الإخبارية Life-Style News Fashion News Movie News Sports News
2021年12月08日 07:37
First You obtained a terrific blog. I will certainly have an interest in even more similar subjects. I see you obtained actually extremely beneficial topics, i will be constantly examining your blog site many thanks. joker123 online
2021年12月14日 05:53
Exceptional post. I was constantly checking this blog site, as well as I'm pleased! Exceptionally helpful information particularly the last part, I care for such details a lot. I was discovering this certain details for a long period of time. Many thanks to this blog my expedition has actually finished. Normanton Park
2022年6月18日 09:20
I want you to give thanks to for your time of this terrific read!!! I certainly enjoy every bit of it and I have you bookmarked to look into new stuff of your blog site a must-read blog! resume builder
2022年8月12日 02:45
Thank you very much for this wonderful article. life coach kenya