希爾排序和插入排序很相似，有點(diǎn)像插入排序的升級(jí)版本。

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡(jiǎn)單插入排序經(jīng)過(guò)改進(jìn)之后的一個(gè)更高效的版本，也稱(chēng)為縮小增量排序，同時(shí)該算法是沖破O(n2）的第一批算法之一。

希爾排序也是一種插入排序算法，只不過(guò)在插入排序上突破了結(jié)界，達(dá)到了另一種頂峰的存在，這種頂峰使得時(shí)間復(fù)雜度變成「O(nLogn)~O(n^2)」。

假設(shè)，我們需要給下面的數(shù)據(jù)進(jìn)行排序：

結(jié)合之前的文章，我們知道兩個(gè)數(shù)據(jù)的插入排序就是比較兩個(gè)數(shù)據(jù)的大小，然后進(jìn)行排列。

希爾排序是通過(guò)分組 插入。

首先，我們排序的數(shù)量是8個(gè)，我們需要把數(shù)據(jù)分成8/2=4組，如下圖所示：

對(duì)上面4組的數(shù)據(jù)進(jìn)行插入排序后得到：

然后，再繼續(xù)分組8?2?2=2分成2組：

這兩組數(shù)據(jù)再進(jìn)行插入排序，如下圖所示：

這樣之后，整個(gè)數(shù)據(jù)的排序就差不多完成了。

我們?cè)谶@個(gè)基礎(chǔ)上再對(duì)整個(gè)隊(duì)列執(zhí)行一次插入排序，就會(huì)完成了整個(gè)隊(duì)列的排序，因?yàn)橹耙呀?jīng)對(duì)數(shù)據(jù)進(jìn)行過(guò)排序，再進(jìn)行插入排序的時(shí)候，效率會(huì)明顯得到提升。

整個(gè)過(guò)程可以觀(guān)看動(dòng)態(tài)圖片：

代碼實(shí)現(xiàn)看看：

#include?
#include?
#include?

int?shell_sort(int?arr[],int?n)
{
????register?int?i,?j,?tmp;
????int?step;

????for(step?=?n/2;?step?>?0;step?/=?2)/*增量步長(zhǎng)*/
????{
????????/*step?=?4?2?1*/
????????for(i?=?step;?i?????????{
????????????tmp?=?arr[i];
????????????j?=?i?-?step;
????????????for(;j?>=?0?