?歡迎來到CILMY23的博客

🏆本篇主題為：【數(shù)據(jù)結(jié)構(gòu)與算法】選擇排序篇----詳解直接插入排序和哈希排序

🏆個人主頁：CILMY23-CSDN博客

🏆系列專欄：Python | C++ | C語言 | 數(shù)據(jù)結(jié)構(gòu)與算法 | 貪心算法 | Linux?| 算法專題?| 代碼訓(xùn)練營

🏆感謝觀看，支持的可以給個一鍵三連，點贊關(guān)注+收藏。

---

?前言

本期要講解的是常見排序算法中的插入排序，插入排序又分兩種，一種是直接插入排序，一種是希爾排序。

---

一、直接插入排序

1.1 插入排序的基本思想：

插入排序是一種簡單的插入排序方法，其基本思想是：

把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。

實際中我們玩撲克牌時，就用了插入排序的思想，我們從桌面抽一張牌，然后把牌按照我們所想的情況排序，插入到合適的位置，這就是插入排序的大致過程。

?

1.2 直接插入排序操作：

當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時用array[i]的排序碼與 array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移?

?

1.3 直接插入排序的特性總結(jié)：

1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復(fù)雜度：O(N^2)（逆序），最好情況是O(N) (順序有序)
3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
4. 穩(wěn)定性：穩(wěn)定

1.4 代碼實現(xiàn)?

第一部分：

先寫單趟的排序，現(xiàn)在取 end 之前的位置都是有序的，要比對的數(shù)值是 end+1 的位置數(shù)，這里我們用一個變量 tmp 來存儲。

我們想實現(xiàn)升序的tmp

如果 tmp 比 end 位置的值小，那么就要把 end 位置的數(shù)值往后移動，end 往前移動，直到我們找到 tmp 比 end 位置的數(shù)值小，我們就可以直接插入。?

特殊情況：

當 end+1 處的位置為最小值時，此時 end 為 -1 ，tmp 也就是 end+1 的位置處于 0 。

代碼：

首先先不管end 是多少，我們知道[0,end]是有序，那end + 1 位置就是我們要比較的數(shù)，假設(shè)這個數(shù)比end位置小，那前面的位置就往后移動，直到數(shù)組盡頭，或者找到比 end位置要大的數(shù)，在這個數(shù)的后面進行插入。?

int end;
int tmp = a[end+1];
while(tmp < a[end])
{a[end+1] = a[end];end--;
}
a[end+1] = tmp

為什么最后是end+1？

?取第二種極端情況，也就是插入排序的end走到盡頭了，此時end 為 -1 這時候我們要在數(shù)組下標0的位置插入，所以要+1。

第二部分

確認多趟的情況 ，首先得保證前 end 都是有序的，想要確認end前有序，我們就再套一層循環(huán)，從0開始，讓 end?從 0?的位置開始，遍歷每個數(shù)值過去，這樣整個數(shù)組都可以實現(xiàn)排序了。

void Insert_Sort(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;}
}

?1.5 動圖理解

二、希爾排序（縮小增量排序）

2.1 基本思想

希爾排序法又稱縮小增量法。

希爾排序法的基本思想是：

先選定一個整數(shù)，把待排序文件中所有記錄分成按距離的個組，所有距離為gap的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后，取，重復(fù)上述分組和排序的工作。當?shù)竭_gap=1時，所有記錄在統(tǒng)一組內(nèi)排好序。

例如下圖：?

第一趟排序，gap = 5,從第一個數(shù)開始，每隔五個數(shù)取一組，9和4為一組；1和8為一組；2和6為一組；5和3為一組，7和5為一組，這樣整個數(shù)組都分好了，然后在每個小組里面進行排序，9和4排序，因為9比4大，所以9在后面，4在前面，以此類推……

第二趟排序，gap = 3，從第一個數(shù)開始，每隔三個數(shù)取一組，4,2,5,8,5為一組；1,3,9,6,7為一組；這樣整個數(shù)組就又分好了，然后在每個小組里面進行排序，4，2，5，8，5排序，排好后，就是4，2，5，8，5.同樣以此類推排第二個小組。

在這樣的排序下就逐漸接近了有序的數(shù)組。我們把這樣的操作叫做預(yù)排序。

最后第三趟排序，當gap == 1時，你會發(fā)現(xiàn)，這個跟直接插入排序沒有區(qū)別，開始取第一個數(shù)，保證第一個數(shù)有序，然后開始走直接插入的思想。?

通過這樣的過程我們就可以發(fā)現(xiàn)，直接插入排序也是希爾排序中的一步驟。?

2.2 希爾排序的特性總結(jié)：

1. 希爾排序是對直接插入排序的優(yōu)化。
2. 當gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣排序起來就會很快。對整體而言，可以達到優(yōu)化的效果。
3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的希爾排序的時間復(fù)雜度都不固定，但也有大致算出來的。估計結(jié)果為O(n^1.3)

4. 穩(wěn)定性：不穩(wěn)定

2.3 希爾排序代碼

void Shell_Sort(int *a,int n)
{int gap = n;while (gap > 1){gap = gap / 2;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{tmp;}}a[end] = tmp;}}
}

2.4 希爾排序操作詳解

?希爾排序分兩步走，一步是預(yù)排序，它的目的是讓整個數(shù)組接近有序，第二步是直接插入排序。

第一種預(yù)排序（一組一組排序）：

預(yù)排序的思路如下：

1. 先把數(shù)組分成以gap為距離的各個小組
2. 把分好的各單位小組進行插入排序
3. 對每個小組進行插入排序

第一步：

假設(shè)我們現(xiàn)在有這樣的三個小組，分別用紅，橙，綠三種顏色進行標記。?

把紅色的第一個小組單獨拿出來

我們標上下標，我們發(fā)現(xiàn)對這一個小組進行插入排序，原先的end+1就變成了end+gap。?

現(xiàn)在是交換紅色的部分，橙色和綠色我們并不在乎。，因為tmp < nums[end],所以只需要比較end處和end+gap處的值，然后繼續(xù)直接插入排序的操作即可。

?我們可以仿照直接插入排序?qū)懗鋈缦碌募t色單區(qū)排序。

int gap = 3;
int end = 0;
int tmp = a[end + gap];
while (end >= 0)
{if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{tmp;}
}
a[end] = tmp;

第二步：?

?然后控制多個紅色小組

?我們套一層for循環(huán)，注意，j不能超過n-gap，防止end+gap越界。

最大的地方是：end+gap = n - 1

所以 j == end <= n-gap-1 == j < n - gap。

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

第三步：

控制多個組進行插入排序?

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

?第二種預(yù)排序（多組并排）：

?其實這里的多組并排原理很簡單，就是讓end按照順序走下去：

也就是將第二步和第三步合并了，這就很接近我們剛開始的步驟。

所以預(yù)排序：

gap越大，大的值更快調(diào)整到后面，小的值更快調(diào)用到前面，?越不接近有序

gap越小， 跳的越慢 越接近有序，如果gap==1，那就是插入排序。

代碼：

end每次只走一步，這樣一組組的跳，就是多組并排了。?

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{tmp;}}a[end] = tmp;
}

第二步 直接插入排序

要想最后接近有序，每次gap就要變化，最后一次gap==1，所以gap要跟著n進行變化

?所以在外圍添加一個循環(huán)，當gap > 1的時候是預(yù)排序，當gap == 1的時候是直接插入排序。

int gap = n;
while (gap > 1)
{gap = gap / 2;//覺得一次2太小//gap = gap / 3 + 1//...	
}

2.5 希爾排序動圖

?

---

🛎?感謝各位同伴的支持，本期數(shù)據(jù)結(jié)構(gòu)與算法---選擇排序篇就講解到這啦，如果你覺得寫的不錯的話，可以給個一鍵三連，點贊，關(guān)注+收藏，若有不足，歡迎各位在評論區(qū)討論。????