我們先來(lái)學(xué)習(xí) 直接插入排序, 直接排序算是所有排序中最簡(jiǎn)單的了,代碼也非常好實(shí)現(xiàn),盡管直接插入排序很簡(jiǎn)單,但是我們依舊不可以上來(lái)就直接寫(xiě)代碼,一定要分析之后才開(kāi)始寫(xiě),這樣可以提高自己寫(xiě)代碼的準(zhǔn)確率,整體流程下來(lái),對(duì)知識(shí)的理解也會(huì)加深.

💗 直接插入排序

默認(rèn)第一個(gè)元素為有序的,然后從無(wú)序序列中的最左邊取元素,從有序序列的右到左依次比較,直到找到合適的位置,然后插入. (簡(jiǎn)言之: 從無(wú)序序列取第一個(gè)元素從左到右比較插入到有序序列合適的位置)

---

用生活中的例子來(lái)描述直接插入排序理解起來(lái)會(huì)更加容易,所以我們這里就用一個(gè)生活中常發(fā)生的事來(lái)類(lèi)比學(xué)習(xí)吧,如果我們把直接插入排序用打撲克牌來(lái)模擬,會(huì)是怎樣的效果呢?

現(xiàn)在就來(lái)試試吧~

使用玩撲克牌的例子來(lái)模擬直接插入排序是一個(gè)很好的主意，這個(gè)例子非常貼近直接插入排序的實(shí)際操作過(guò)程。讓我們?cè)敿?xì)地通過(guò)這個(gè)例子來(lái)理解直接插入排序：

1. 初始狀態(tài)：你的手中還沒(méi)有牌，而洗好的牌堆是無(wú)序的。
2. 拿起第一張牌：從牌堆中拿起最上面的一張牌，這是你手中的第一張牌，所以它自然就是有序的。
3. 繼續(xù)摸牌：再次從牌堆中拿起最上面的一張牌。
4. 比較和插入：
   • 將這張新拿到的牌與手中已有的牌從右到左進(jìn)行比較。
   • 如果新牌比正在比較的牌小，就將手中的這張牌向右移動(dòng)一個(gè)位置，為新牌騰出空間。
   • 繼續(xù)這個(gè)過(guò)程，直到找到一個(gè)牌位，那里的牌比新牌小或者沒(méi)有牌了（也就是這張新牌是目前最小的）。
5. 插入新牌：將新牌放入這個(gè)位置。
6. 重復(fù)過(guò)程：繼續(xù)從牌堆中拿牌，并重復(fù)上述比較和插入的過(guò)程，直到牌堆中的所有牌都被拿完并按順序排列在手中。

這個(gè)過(guò)程很好地模擬了直接插入排序的邏輯。在每一步中，你都保證了手中的牌是有序的，通過(guò)找到合適的位置為新牌插入。這就是直接插入排序的精髓：一步步構(gòu)建有序序列，直到所有元素都被正確地插入。

我們把上面的操作用圖示來(lái)演示一下,進(jìn)一步加深理解 , 假設(shè)現(xiàn)在的洗好的撲克牌為一組無(wú)序序列 : {6,4,9,1,10,2,8}

好,可以開(kāi)始打牌了~

Java代碼

package src.boke;public class InsertSort {public static void main(String[] args){//無(wú)序序列int[] arr = {6,4,9,1,10,2,8};//調(diào)用直接排序方法insertSort(arr);//打印有序序列printArray(arr);}/*** 直接插入排序方法實(shí)現(xiàn)* @param arr 待排序序列/無(wú)序序列*/public static void insertSort(int[] arr){//對(duì)傳進(jìn)來(lái)的無(wú)序序列進(jìn)行直接插入排序操作for (int i = 1; i < arr.length; i++) {//接收int[i] ,即摸到的牌int key = arr[i];int j  = i-1;for (; j >=0 ; j--) {if(arr[j]>key){arr[j+1] = arr[j];}else{break;}}arr[j+1] = key;}}/*** 打印素組的方法*/public static void printArray(int[] arr){for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] +" ");}}
}

C代碼

#include <stdio.h>void insertSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;// 將大于 key 的元素向右移動(dòng)一個(gè)位置while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}void printArray(int arr[], int n) {for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {6, 4, 9, 1, 10, 2, 8};int n = sizeof(arr) / sizeof(arr[0]);insertSort(arr, n);printArray(arr, n);return 0;
}

JavaScript代碼

function insertSort(arr) {for (let i = 1; i < arr.length; i++) {let key = arr[i];let j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}function printArray(arr) {console.log(arr.join(" "));
}// 測(cè)試
let arr = [6, 4, 9, 1, 10, 2, 8];
insertSort(arr);
printArray(arr);

---

穩(wěn)定性

排序穩(wěn)定性是排序算法的一個(gè)重要特性，它涉及相等元素的相對(duì)順序在排序前后是否保持不變。

具體來(lái)說(shuō)：

• 穩(wěn)定排序：如果一個(gè)排序算法在排序后保持了相等元素在原序列中的相對(duì)順序，那么這個(gè)算法是穩(wěn)定的。換句話說(shuō)，如果兩個(gè)具有相等關(guān)鍵字的元素在排序前是以某種順序排列的，那么在排序后它們?nèi)匀灰酝瑯拥捻樞蚺帕?#xff0c;這樣的排序算法就被認(rèn)為是穩(wěn)定的。
• 不穩(wěn)定排序：如果排序算法不能保證相等元素的相對(duì)順序，則稱這種排序是不穩(wěn)定的。在這種情況下，相等的元素可能會(huì)因排序過(guò)程而交換位置。

穩(wěn)定性的重要性主要體現(xiàn)在當(dāng)元素有多個(gè)字段進(jìn)行排序時(shí)。在某些情況下，維持?jǐn)?shù)據(jù)的初始順序是重要的。例如，在對(duì)一組人按照出生日期排序后，可能需要對(duì)結(jié)果按姓名排序，如果使用穩(wěn)定排序算法，那么同一天出生的人將按照他們?cè)嫉捻樞?#xff08;即按姓名的順序）排列。

通過(guò)上述測(cè)試我們可以知道,當(dāng)我們?cè)诒容^key和arr[j] 的時(shí)候,如果取了 等號(hào) ,那么此時(shí)就是不穩(wěn)定的,如果沒(méi)有取 等號(hào) 就是穩(wěn)定的,所以直接插入排序是穩(wěn)定的嗎?

讓我們?cè)敿?xì)解釋一下為什么這樣會(huì)發(fā)生：

• 當(dāng)使用 arr[j] > key 進(jìn)行比較時(shí)，如果 arr[j] 等于 key，那么循環(huán)會(huì)停止，key 將被插入到 arr[j] 的后面。因此，原始數(shù)組中順序相鄰的、值相等的元素在排序后仍將保持相同的順序，這保證了排序的穩(wěn)定性。
• 然而，如果使用 arr[j] >= key 進(jìn)行比較，當(dāng) arr[j] 等于 key 時(shí)，排序過(guò)程仍會(huì)繼續(xù)，嘗試找到更前面的位置插入 key。這可能導(dǎo)致 key 被插入到其他相等元素的前面，從而改變了這些元素的相對(duì)順序，這破壞了排序的穩(wěn)定性。

結(jié)論 : 一個(gè)本身就穩(wěn)定的排序你可以將其實(shí)現(xiàn)為不穩(wěn)定的,但是一個(gè)本身就不穩(wěn)定的排序你無(wú)法將其變成穩(wěn)定的. 所以 : 直接插入排序是穩(wěn)定的排序

---

時(shí)間復(fù)雜度

• 直接插入排序的時(shí)間復(fù)雜度是 O(n^2)

直接插入排序的時(shí)間復(fù)雜度分析涉及到最好情況、平均情況和最壞情況。

1. 最好情況時(shí)間復(fù)雜度：當(dāng)輸入數(shù)組已經(jīng)是有序的，每次比較都不需要進(jìn)行移位操作（因?yàn)槊總€(gè)元素已經(jīng)是在其正確的位置上），直接插入排序只需要進(jìn)行一次遍歷來(lái)確認(rèn)所有元素都已排序。因此，在這種情況下，時(shí)間復(fù)雜度是 O(n)，其中 n 是數(shù)組的長(zhǎng)度。
2. 最壞情況時(shí)間復(fù)雜度：在最壞的情況下，數(shù)組完全逆序，即每次插入都需要將元素移動(dòng)到數(shù)組的最前面。這就需要對(duì)于每個(gè)元素進(jìn)行從 1 到 i（其中 i 是當(dāng)前元素的索引）的比較和移動(dòng)，因此需要的操作數(shù)接近于 1+2+3+…+(n?1)，這是一個(gè)等差數(shù)列求和，總和是 O(n^2)。
3. 平均情況時(shí)間復(fù)雜度：在平均情況下，元素需要移動(dòng)的次數(shù)大約是數(shù)組長(zhǎng)度的一半，因此平均情況時(shí)間復(fù)雜度也是O(n^2)。

---

空間復(fù)雜度

• 你直接插入排序的空間復(fù)雜度是O(1)

直接插入排序的空間復(fù)雜度主要考慮的是算法在執(zhí)行過(guò)程中需要額外使用的內(nèi)存空間。

在直接插入排序中，所有的排序操作都是在原始數(shù)組上進(jìn)行的，不需要額外的數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)。排序過(guò)程中唯一需要的額外空間是一個(gè)用于存儲(chǔ)待插入元素的臨時(shí)變量（比如 key）。除此之外，還需要少量的額外空間用于循環(huán)計(jì)數(shù)和索引存儲(chǔ)。

由于這些額外空間的需求量不隨待排序的數(shù)據(jù)量的增加而增加（也就是說(shuō)，無(wú)論要排序多少數(shù)據(jù)，所需的額外空間量都是固定的），因此直接插入排序的空間復(fù)雜度是O(1)，也就是說(shuō)它是一個(gè)原地排序算法。這也意味著直接插入排序非常節(jié)省內(nèi)存，適合于在內(nèi)存受限的環(huán)境中使用。