引言

????????排序在我們生活中十分常見(jiàn)，無(wú)論是購(gòu)物軟件中的商品推薦還是名次、排名都與排序算法息息相關(guān)。希爾排序是排序中較快的一種，而希爾排序?qū)崿F(xiàn)的基礎(chǔ)是插入排序。

排序的實(shí)現(xiàn)

插入排序（以升序?yàn)槔?#xff09;

? ? ? ? 插入排序的原理是從第二個(gè)數(shù)開(kāi)始，與前面的數(shù)相比較，如果比前面的數(shù)大，則與其交換，并且此移動(dòng)過(guò)程會(huì)一直持續(xù)直到前k（k為此次剛開(kāi)始移動(dòng)的數(shù)的位置）個(gè)數(shù)達(dá)到有序?yàn)橹?#xff1b;否則不會(huì)移動(dòng)。代碼如下：

void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}}

????????我們將一直要改變的那個(gè)數(shù)設(shè)為tmp,將它與前面的數(shù)（end）比較，如果tmp較小，則進(jìn)行交換，先將啊a[end] 覆蓋a[end + 1],再--end達(dá)到tmp繼續(xù)與前一個(gè)數(shù)比較的效果，最后達(dá)到效果.

希爾排序

希爾排序分為兩步：預(yù)排序與插入排序.

預(yù)排序

預(yù)排序的目的是先讓數(shù)組接近有序，將所有數(shù)據(jù)分為gap組，其代碼與插入排序十分類(lèi)似。

以該圖為例，改預(yù)排序的流程是5與9比較，如果比9小，則將9放到原來(lái)5的位置，

再將8與9相比較并與5比較，8比9小，再將9放到8的位置，8比5大，所以再停止

最后將最后的5進(jìn)行排序即可.

再嵌套一層循環(huán)使其達(dá)到排三組循環(huán)的效果

9--5--8--5

1--7--6

2--4--3

代碼如下：

void ShellSort(int* a, int n)
{int gap = 3;for (int j = 0; j < gap; j++){for (int i = 0; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

?我們也可以只用兩層循環(huán)實(shí)現(xiàn)，即分組排序的順序改為

9--5,1--7,2--4,5--8,7--6,4--3,8--5.，實(shí)現(xiàn)代碼如下：

//Shell排序的雙層循環(huán)的寫(xiě)法void ShellSort(int* a, int n)
{int gap = 3;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}

總排序

gap一般取整個(gè)數(shù)組的數(shù)量除以三，為保證最后一次一定是1，我們將其設(shè)為gap = gap / 3 +1,這樣最后就可以由一個(gè)插入排序?qū)︻A(yù)排序后的數(shù)組進(jìn)行總排序.并且我們每次預(yù)排序都會(huì)使數(shù)組更加有序，代碼如下：

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

希爾排序的速度

在release環(huán)境下，測(cè)試100,000個(gè)數(shù)據(jù)，其結(jié)果如下：

我們發(fā)現(xiàn)，希爾排序的速度是與堆排序是一個(gè)數(shù)量級(jí)的，而插入排序的速度也是比冒泡排序要快一個(gè)量級(jí)的.

測(cè)試1,000,000個(gè)數(shù)據(jù)

測(cè)試10,000,000個(gè)數(shù)據(jù)

堆排序的時(shí)間復(fù)雜度是O(),所以希爾排序的速度算是非?？斓?#xff0c;有實(shí)踐意義。

希爾排序的時(shí)間復(fù)雜度是 O().