學(xué)習(xí)目標(biāo)
寫在前面
1.插入排序
2.插入排序?qū)崙?zhàn)?
3.插入排序的實(shí)現(xiàn)?
4.插入排序的效率
5.平均情況
6.希爾排序
7.希爾排序的實(shí)現(xiàn)
8.希爾排序的效率
9.總結(jié)?
寫在前面
之前我們衡量一個(gè)算法的效率時(shí)，都是著眼于它在最壞情況下需要多少步。原因很簡(jiǎn)單，連最壞的情況都做足準(zhǔn)備了，其他情況自然不在話下。
但是，在我們實(shí)際生活中并不總是面臨最壞情況，更多的是平均情況。本章我們會(huì)見證一種自適應(yīng)性極強(qiáng)的排序算法---希爾排序，還有它的組成它的關(guān)鍵---插入排序。
1.插入排序
我們已經(jīng)學(xué)過兩種排序算法：冒泡排序和選擇排序。雖然它們的效率都是 O(N^2 )，但其實(shí)選擇排序比冒泡排序快一倍。
現(xiàn)在來學(xué)第三種排序算法——插入排序（直接插入排序）。你會(huì)發(fā)現(xiàn)，顧及最壞情況以外的場(chǎng)景將是多么有用。插入排序包括以下步驟。
插入排序包括以下步驟。
(1) 在第一輪里，暫時(shí)將索引 1（第 2格）的值移走，并用一個(gè)臨時(shí)變量來保存它。這使得該索引處留下一個(gè)空隙，因?yàn)樗话怠?/p>
?在之后的輪回，我們會(huì)移走后面索引的值。
(2) 接著便是平移階段，我們會(huì)拿空隙左側(cè)的每一個(gè)值與臨時(shí)變量的值進(jìn)行比較。
如果空隙左側(cè)的值大于臨時(shí)變量的值，則將該值右移一格。?
隨著值右移，空隙會(huì)左移。如果遇到比臨時(shí)變量小的值，或者空隙已經(jīng)到了數(shù)組的最左端，就結(jié)束平移階段。?
(3) 將臨時(shí)移走的值插入當(dāng)前空隙。
(4) 重復(fù)第(1)至(3)步，直至數(shù)組完全有序。
2.插入排序?qū)崙?zhàn)?
下面嘗試對(duì) [4, 2, 7, 1, 3] 數(shù)組運(yùn)用插入排序。
第 1輪先從索引 1開始，其值為 2。
準(zhǔn)備工作：暫時(shí)移走 2，并將其保存在變量 tmp 中。圖中被移到數(shù)組上方的就是
tmp。?
?第 1步：比較 4與 tmp中的 2。
第 2步：因?yàn)?4大于 2，所以把 4右移。
?于是空隙移到了數(shù)組最左端，沒有其他值可以比較了。
?第 3步：將 tmp插回?cái)?shù)組，完成第一輪。
開始第 2輪。
準(zhǔn)備工作：暫時(shí)移走索引 2的值，并保存到 tmp中。于是 tmp等于 7。
第 4步：比較 4與 tmp。
4小于 7，所以無須平移。因?yàn)橛龅搅诵∮?tmp的值，所以平移階段結(jié)束。
第 5步：將 tmp插回到空隙中，結(jié)束第 2輪。
開始第 3輪。
準(zhǔn)備工作：暫時(shí)移走 1，并將其保存到 tmp中。
?第 6步：比較 7與 tmp。
?第 7步：7大于 1，于是將 7右移。
?第 8步：比較 4與 tmp。
第 9步：4大于 1，于是也要將 4右移。?
第 10步：比較 2與 tmp。
第 11步：2比較大，所以將 2右移。
第 12步：空隙到了數(shù)組最左端，因此我們將 tmp插進(jìn)去，結(jié)束這一輪。?
開始第 4輪。
準(zhǔn)備工作：暫時(shí)移走索引 4的值 3，保存到 tmp中。
第 13步：比較 7和 tmp。
?第 14步：7更大，于是將 7右移。
第 15步：比較 4與 tmp。
第 16步：4大于 3，所以將 4右移。
第 17步：比較 2與 tmp。2 小于 3，于是平移階段完成。
?第 18步：把 tmp插回到空隙。
?至此整個(gè)數(shù)組都排好序了。
3.插入排序的實(shí)現(xiàn)?
以下使用C語言實(shí)現(xiàn)的直接插入排序：
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 (a[end] > tmp) //大于tmp，往后挪一個(gè)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp; //把tmp插入空隙
}
}?讓我們一步步來講解：
for (int i = 0; i < n - 1; i++)?最外層的這個(gè)循環(huán)用來控制end的位置，也就是一個(gè)輪回。
int end = i;
int tmp = a[end + 1];我們通過控制end的位置，使end與end之前的數(shù)列都是有序的，而把end+1索引處的值（也就是tmp）插入到end之前的數(shù)列中。所以，end的值是從0開始的。這樣能保證end與end之前的數(shù)列是有序的（因?yàn)橹挥幸粋€(gè)數(shù)），那么將tmp插入后，前end+1個(gè)數(shù)都是有序的，再依次執(zhí)行下去。
while (end >= 0)end索引處的值會(huì)發(fā)生移動(dòng)，最壞的情況是tmp的值比之前的有序數(shù)列中每一個(gè)值都要小，那么空隙的位置就在end=0處。例如：
if (a[end] > tmp) //大于tmp，往后挪一個(gè)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}找到空隙，將比tmp大的數(shù)字不斷往后挪，直到找到小于等于tmp的數(shù)字。
a[end + 1] = tmp; //把tmp插入空隙將tmp插入空隙。
4.插入排序的效率
插入排序包含 4種步驟：移除、比較、平移和插入。要分析插入算法的效率，就得把每種步驟都統(tǒng)計(jì)一遍。
首先看看比較。每次拿 tmp跟空隙左側(cè)的值比大小就是比較。
在數(shù)組完全逆序的最壞情況下，我們每一輪都要將 tmp左側(cè)的所有值與tmp比較。因?yàn)槟切┲等即笥?tmp，所以每一輪都要等到空隙移到最左端才能結(jié)束。
對(duì)于含有N個(gè)元素的數(shù)組，可以得出比較的總次數(shù)為：
1 + 2 + 3 + … + N -?1 次。
接下來看看其他幾種步驟。
我們每次將值右移一格，就是平移操作。當(dāng)數(shù)組完全逆序時(shí)，有多少次比較就要多少次平移，因?yàn)槊看伪容^的結(jié)果都會(huì)使你將值右移。
因而可以得出平移的總次數(shù)為：
1 + 2 + 3 + … + N -?1 次。
tmp的移除跟插入在每一輪里都會(huì)各發(fā)生一次。因?yàn)榭偸怯?N -?1輪，所以可以得出結(jié)論：有 N -?1次移除和 N -?1次插入。
把它們都相加。
N^2 比較和平移的合計(jì)
+ N -?1 次移除
+ N -?1 次插入
=
N^2 + 2N -?2步
我們已經(jīng)知道大 O有一條重要規(guī)則——忽略常數(shù)，于是你可能會(huì)將其簡(jiǎn)化成 O(N^2 + N)。不過，現(xiàn)在來學(xué)習(xí)一下大 O的另一條重要規(guī)則：
大 O 只保留最高階的 N。
換句話說，如果有個(gè)算法需要 N^4 + N^3 + N^2 + N步，我們就只會(huì)關(guān)注其中的 N^4 ，即以 O(N^4 )
來表示。為什么呢？
請(qǐng)看下表。
隨著 N的變大，N^4 的增長(zhǎng)越來越拋離其他階。當(dāng) N為 1000時(shí)，N^4 就比 N^3 大了 1000倍。因
此，我們只關(guān)心最高階的 N。
所以在插入排序的例子中，O(N^2 + N)還得進(jìn)一步簡(jiǎn)化成 O(N^2 )。
不過上一章曾指出，雖然冒泡排序和選擇排序都是 O(N^2 )，但選擇排序?qū)嶋H上是 N^2 / 2步，
比 N 2 步的冒泡排序更快。乍一看，你可能會(huì)覺得插入排序跟冒泡排序一樣，因?yàn)樗鼈兌际?O(N^2 )，其實(shí)插入排序是 N^2 + 2N -?2步。你或許會(huì)認(rèn)為比冒泡排序和插入排序快一倍的選擇排序是三者中最優(yōu)的，但事情并沒有這么簡(jiǎn)單。
5.平均情況
確實(shí)，在最壞情況里，選擇排序比插入排序快。但是我們還應(yīng)該考慮平均情況。
最好情況和最壞情況很少發(fā)生。現(xiàn)實(shí)世界里，最常出現(xiàn)的是平均情況。
這是很有道理的。你設(shè)想一個(gè)隨便洗亂的數(shù)組，出現(xiàn)完全升序或完全降序的可能性有多大？最可能出現(xiàn)的情況應(yīng)該是隨機(jī)分布。
下面試試在各種場(chǎng)景中測(cè)試插入排序。
完全降序的最壞情況之前已經(jīng)見過，它每一輪都要比較和平移所遇到的值（這兩種操作合計(jì)N^2 步）。
對(duì)于完全升序的最好情況，因?yàn)樗兄刀家言谄湔_的位置上，所以每一輪只需要一次比較，完全不用平移。
最壞情況是所有數(shù)據(jù)都要比較和平移；最好情況是每輪一次比較、零次平移；對(duì)于平均情況，總的來看，是比較和平移一半的數(shù)據(jù)。
如果說插入排序的最壞情況需要 N 2 步，那么平均情況就是 N 2 / 2步。盡管最終大 O都會(huì)寫成 O(N^2 )。
可以看到插入排序的性能在不同場(chǎng)景中差異很大。最壞、平均、最好情況，分別需要 N^2 、
N^2 / 2、N步。
那么哪種算法更好？選擇排序還是插入排序？答案是：看情況。對(duì)于平均情況（數(shù)組里的值隨機(jī)分布），它們性能相近。如果你確信數(shù)組是大致有序的，那么插入排序比較好。如果是大致逆序，則選擇排序更快。
6.希爾排序
希爾排序是對(duì)插入排序做了簡(jiǎn)單的優(yōu)化，卻產(chǎn)生了質(zhì)的飛躍。直接讓不太起眼的插入排序比肩聞名算法界的快速排序。我們知道對(duì)于插入排序，數(shù)據(jù)的元素越是接近有序，那么它的效率就越高；對(duì)于完全有序的數(shù)組，它甚至可以快到O(N)。
那么希爾排序的主要思想是，我們不斷地對(duì)數(shù)組進(jìn)行預(yù)排序，使數(shù)組里大的元素盡量到數(shù)組的后面，小的元素盡量到數(shù)組的前面。
完成對(duì)數(shù)組的預(yù)排序看，我們采取的方法是對(duì)數(shù)組進(jìn)行分組，把數(shù)組里間隔相同長(zhǎng)度的元素劃分為一組。例如：
?接下來我們對(duì)每一組的元素進(jìn)行排序。
如圖所示，第一趟排序，較大的元素已經(jīng)到了數(shù)組的后面了。接下來再次重新分組，再次預(yù)排序：
經(jīng)過第二趟預(yù)排序，我們發(fā)現(xiàn)數(shù)組已經(jīng)大致接近有序了，那么最后一次，我們?nèi)￠g隔為1分組，其實(shí)就是一次普通的插入排序：
至此，數(shù)組已經(jīng)完全有序了。
通過上面的例子不難看出，希爾排序就是對(duì)插入排序的簡(jiǎn)單優(yōu)化，引入了預(yù)排序的概念。
當(dāng)gap>1時(shí)，進(jìn)行的是預(yù)排序（也就是對(duì)每一組進(jìn)行插入排序）；
當(dāng)gap=1時(shí)，進(jìn)行對(duì)整個(gè)數(shù)組的插入排序。
7.希爾排序的實(shí)現(xiàn)
下面使用C語言實(shí)現(xiàn)的希爾排序：
void ShellSort(int* a, int n)
{
int gap = n; //間隔
while (gap > 1)
{
gap = gap / 3 + 1; //+1是為了使gap最后等于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;
}
}
}代碼相較于插入排序并沒有改變多少，在插入排序的基礎(chǔ)上多了一層循環(huán)用來控制gap。
此處可以看出，預(yù)排序并不是固定的3次或者4次。而是取決于數(shù)組元素個(gè)數(shù)，這么做一是為了方便控制gap，二是預(yù)排序越多次，對(duì)整體排序而言更有利，所以我們不用吝嗇預(yù)排序，并不是預(yù)排序越多，花費(fèi)的步數(shù)就越多，時(shí)間復(fù)雜度就越高。
gap = gap / 3 + 1; 除了這樣控制gap外，還有一種常用的方法：
gap = gap / 2; 但是根據(jù)有人實(shí)驗(yàn)得出，第一種方式比第二種方式快一點(diǎn)點(diǎn)，但是差距很細(xì)微，所以兩者皆可。
8.希爾排序的效率
希爾排序的時(shí)間復(fù)雜度并不好算，因?yàn)槊看稳ap的值都不同，而且gap取不同值的情況下，每次預(yù)排序所面臨的數(shù)據(jù)也不同。希爾排序的時(shí)間復(fù)雜度計(jì)算需要運(yùn)用到數(shù)學(xué)知識(shí)，而且目前為止我們也沒有得到嚴(yán)格的標(biāo)準(zhǔn)答案。有人在大量實(shí)驗(yàn)的基礎(chǔ)上得出希爾排序的時(shí)間復(fù)雜度接近O(N^1.3)。
《數(shù)據(jù)結(jié)構(gòu)(C語言版)》--- 嚴(yán)蔚敏
?《數(shù)據(jù)結(jié)構(gòu)-用面相對(duì)象方法與C++描述》--- 殷人昆
因?yàn)槲覀兊膅ap取值的方式是按照Knuth的方式取的，所以以我們這種方式實(shí)現(xiàn)的希爾排序時(shí)間復(fù)雜度暫定為O(N^1.25)。
目前僅僅靠時(shí)間復(fù)雜度的對(duì)比，我們也許感受不到什么叫做質(zhì)的飛躍，那我們就通過一組數(shù)據(jù)來對(duì)比一下二者的差距。
這是一個(gè)測(cè)試排序算法所用時(shí)間的函數(shù)：
void TestOP()
{
srand(time(0));
const int N = 1000000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
int j = 0;
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
printf("%d\n", j);
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
//SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
//HeapSort(a4, N);
int end4 = clock();
int begin7 = clock();
//BubbleSort(a7, N);
int end7 = clock();
int begin5 = clock();
//QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
//MergeSort(a6, N);
int end6 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("BubbleSort:%d\n", end7 - begin7);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}我們以排序1百萬個(gè)元素為例，得到以下結(jié)果：
?很顯然兩種排序算法已經(jīng)不在一個(gè)數(shù)量級(jí)了。
9.總結(jié)
懂得區(qū)分最好、平均、最壞情況，是為當(dāng)前場(chǎng)景選擇最優(yōu)算法以及給現(xiàn)有算法調(diào)優(yōu)以適應(yīng)環(huán)境變化的關(guān)鍵。記住，雖然為最壞情況做好準(zhǔn)備十分重要，但大部分時(shí)間我們面對(duì)的是平均情況。文章來源：http://www.zghlxwxcb.cn/news/detail-612930.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-612930.html
到了這里，關(guān)于『初階數(shù)據(jù)結(jié)構(gòu) ? C語言』⑥ - 插入排序&希爾排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
