本章開始就要分享一些常用的排序方法，我們的日常生活中很多地方都要使用排序，比如電商平臺可以按照你的需求進(jìn)行排序，或者是你想了解大學(xué)的綜合排名時
?
?我們之前也學(xué)到過一些簡單的排序比如冒泡排序，雖然他在時間復(fù)雜度上可以說是依托答辯，但是作為排序算法來講還是非常有教學(xué)意義的，讓更多的人可以了解到排序。
那首先分享兩種排序算法，簡單了解一下排序，以下是本章目錄；
目錄
1.直接插入排序
2.希爾排序
2.1對gap的解釋
1.直接插入排序
玩兒斗地主時，我們需要將我們的牌排成有序的，例如對子、順子，以便于我們出牌。
直接插入排序是一種簡單的插入排序法，其基本思想是：
把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
用上面這副圖說就是我們手里已經(jīng)有了2、4、5、10，當(dāng)我們拿到7的時候我們需要對他的前后進(jìn)行對比并且找到合適的位置進(jìn)行插入。
為了便于理解以下先是單趟的插入排序
void InserSort(int* a, int n)
{
//[0,end]有序，插入tmp后依然有序
int tmp;
int end;
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}以上代碼中tmp可以理解為我們插入的數(shù)據(jù)，大致意思就是當(dāng)我們想要插入的數(shù)比最后一個數(shù)小的時候，就放在最后一個數(shù)的前面，并且將數(shù)組中的數(shù)字整體向后移動；但是當(dāng)其他情況的時就可以直接插入。
下圖是當(dāng)我們插入1的時候要和數(shù)組內(nèi)容進(jìn)行比較，最后將1插入到了最前面，圖示方便大家理解。
注意將a[end+1]=tmp;寫在括號外是為了避免數(shù)組為空的問題；
以上是單趟排序的理解，我們加上for語句來規(guī)定他的循環(huán)次數(shù)即可完成多趟排序
void InserSort(int* a, int n)
{
//[0,end]有序，插入tmp后依然有序
for (int i = 1; i <= n; i++)
{
int tmp = a[i];
int end = i - 1;
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
} 所所以不難看出他最壞的情況下的時間復(fù)雜度為O(N^2)?
那不就和我們之前所學(xué)的冒泡排序的時間復(fù)雜度一樣了嗎？并不是這樣。
冒泡排序的思想是相鄰兩個元素進(jìn)行比較在進(jìn)行交換，而且一趟排序只能確定一個數(shù)的位置，所以無論是否有序，他的時間復(fù)雜度都是O(n^2);
而插入排序在最好的情況下，也就是數(shù)組為升序的情況下時間復(fù)雜度為O(n),省去了兩兩交換的過程，當(dāng)然前提是數(shù)組為升序
以上就是插入排序的內(nèi)容
2.希爾排序 ?
希爾排序其實是對插入排序的一種優(yōu)化，大體思想就是在插入排序之前加上了與排序的步驟，所以他的思路就是1.預(yù)排序，使這個數(shù)組接近有序（注意是接近有序而不是有序）2.插入排序。
這個預(yù)排序的意思就是先將數(shù)組分組，固定一個gap，使數(shù)組間隔為gap分成一組，總共有g(shù)ap組。
我們用一段數(shù)組來舉例
我們假設(shè)gap為3
?如上圖就分成了一組，接下來繼續(xù)分組
?
?
?
可以看到gap為三時，紅色線標(biāo)注的9，6，3，1為一組數(shù)；藍(lán)色線標(biāo)注的8，5，3，0為一組數(shù)，最后用綠色線標(biāo)注的7，4，2為一組數(shù)；
接下來就要對gap組的數(shù)據(jù)分別插入排序(升序)；
首先是對第一組的數(shù)據(jù)插入排序成升序，如下圖；后面幾組數(shù)據(jù)以此類推
紅色組的數(shù)據(jù)
藍(lán)色組的數(shù)據(jù)
?
?
綠色組的數(shù)據(jù)?
?
?到這里我們會發(fā)現(xiàn)這樣預(yù)排序之后讓數(shù)組接近有序，這樣就達(dá)到了預(yù)排序的效果；
最后我們再對預(yù)排序后的數(shù)據(jù)進(jìn)行插入排序，這樣效率就會提高很多。
回頭再看這組數(shù)據(jù)，如果想讓他排成升序，但是這組數(shù)據(jù)確實降序，無疑在時間復(fù)雜度上一定是最壞的結(jié)果，所以時間復(fù)雜的度為O(n^2);
但是使用了希爾排序的預(yù)處理之后，讓數(shù)組接近升序，這樣就會在時間復(fù)雜度上回優(yōu)化不少；
為了方便理解，我們先排列第一組數(shù)據(jù)（以下代碼為錯誤代碼示范）；
void ShellSort(int* a, int n)
{
int gap = 3;
for (int i = 0; i < n; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}以上就是排完一個gap組的數(shù)據(jù)?
看完以上代碼不知到是否想到了插入排序的思想
?是的，預(yù)處理只是將數(shù)組之間比較的間隔拉大了一些，插入排序是后一個數(shù)向前插入，和自己的前一個數(shù)進(jìn)行比較；而希爾排序的預(yù)處理階段也是后一個數(shù)向前插入，只不過是和自己的前gap個數(shù)進(jìn)行比較；簡單來說就是插入排序只走一步，而希爾排序走的是規(guī)定的gap步。
但是觀察上面的代碼我們會發(fā)現(xiàn)當(dāng)i走到end的位置時，繼續(xù)往下走就會越界
?所以我們還需要將for循環(huán)中的循環(huán)條件改為i<n-gap;
void ShellSort(int* a, int n)
{
int gap = 3;
for (int i = 0; i < n-gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}這樣才算是真正的將第一組的數(shù)據(jù)，也就是紅色的線連接的9，6，3，1排成有序的1，3，6，9；
排完一組數(shù)據(jù)我們還需要將第二組藍(lán)色線的數(shù)據(jù)和第三組綠色線數(shù)據(jù)都排成有序；
上面的思想我們也講過只需控制下標(biāo)end就可以達(dá)到排序不同組數(shù)據(jù)的效果，所以我們不妨再套一個for循環(huán)來解決問題；
void ShellSort(int* a, int n)
{
int gap = 3;
for (int j = 0; j < gap; j++)//循環(huán)插入每組
{
for (int i = j; i < n; i += gap)//每組數(shù)據(jù)排序（升序）
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}這樣以來我們就解決了要排列多組數(shù)據(jù)的問題；
ok說了那么多我們寫個測試樣例驗證一下我們的結(jié)果
?可以看到我們的降序數(shù)組在希爾的預(yù)處理中已經(jīng)變得近似有序
接下來要說是到現(xiàn)在位置已經(jīng)有了三層循環(huán)，所以我們可以對其進(jìn)行優(yōu)化，以下是優(yōu)化的代碼
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 (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}首先我們對比兩種寫法
?
?其實對比兩種寫法，第一種會更利于理解一些，因為第一種的思路是一組一排，就是第一組數(shù)據(jù)排完排第二組，第二組排完派第三組以此類推，按照圖示來說就是先排紅色在排藍(lán)色在排綠色的數(shù)據(jù)。
?
而第二種寫法的思路是多組并排，也就是控制通過控制? i 來控制end，?也就是分別將每一組的第一個數(shù)據(jù)排好再去排每組的第二個數(shù)據(jù)，再去排每組的第三個數(shù)據(jù)以此類推，照圖示來說就是先排1，再排0，再排2，在排3，3，4，6，5…………
?其實兩者的時間復(fù)雜度是一樣的，效率上并沒有提升，只是在理解上更巧一點。
2.1對gap的解釋
在上面的代碼中為了測試方便一些于是自己寫了一個簡單的測試用例，并規(guī)定了gap為3；
那gap一定為3嗎？其實根據(jù)上面的希爾排序?qū)Ρ炔迦肱判蛑校柵判蛱母炝?，?dāng)后一個數(shù)比前一個數(shù)小的時候，他不是像插入排序一樣向前一位交換數(shù)據(jù)，而是向前gap位交換數(shù)據(jù)；
他的目的是在預(yù)處理中，將小的數(shù)更快的放到數(shù)組的前面，大的數(shù)更快的放到數(shù)組的后面而使數(shù)組盡量有序。
當(dāng)然gap也并非越大越好，因為gap越大，越不接近有序
當(dāng)我們將gap改成5時，我們會發(fā)現(xiàn)沒有g(shù)ap=3時有序；
?我們再將gap換成1
?我們就會發(fā)現(xiàn)數(shù)組就會排成升序了，這就和之前的插入排序一樣了
所以我們總結(jié)出
gap越大，大的數(shù)可以更快到后面，小的數(shù)可以更快到前面，越不接近有序；
gap越小，大的數(shù)和小的數(shù)移動越慢，但是會更接近有序；
gap==1時，就會直接變成插入排序；
?所以我們規(guī)定在使用希爾排序時將他的gap設(shè)置為? gap/3+1 ,因為要保證gap在數(shù)據(jù)很少的情況下也是int類型。
以下是規(guī)定gap后的代碼
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 (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}?接下來在對他進(jìn)行一次插入排序就可以使數(shù)組有序了。文章來源：http://www.zghlxwxcb.cn/news/detail-544045.html
以上就是有關(guān)插入排序和希爾排序內(nèi)容的分享，如果對你有所幫助還請三連支持，感謝您的閱讀。文章來源地址http://www.zghlxwxcb.cn/news/detail-544045.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】排序：插入排序與希爾排序詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
