目錄

前言

一.插入排序

1.思想

2.實現

3.特點

二,希爾排序

1.思想

2,實現

3.特點

---

前言

????????排序算法是計算機科學中的基礎工具之一，對于數據處理和算法設計有著深遠的影響。了解不同排序算法的特性和適用場景，能夠幫助程序員在特定情況下選擇最合適的算法，從而提高程序的效率和性能。本節我們講述插入排序和希爾排序。

一.插入排序

1.思想

插入排序基本思想是將一個元素逐個插入到已經排好序的元素序列中，從而得到一個新的有序序列。插入排序的步驟如下：

1. 初始狀態： 假設第一個元素已經是有序序列，可以將其視為一個只包含一個元素的序列。

2. 從第二個元素開始： 將當前元素與已經排好序的元素比較，找到合適的位置插入。

3. 插入操作： 將當前元素插入到合適的位置，同時調整其他元素的位置，以保持已有序序列的有序性。

4. 重復： 重復步驟2和步驟3，直到所有元素都被插入到有序序列中，整個序列變得有序。

2.實現

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;}
}

時間復雜度:O(n^2)

空間復雜度O(1)

穩定性:穩定

3.特點

1.優勢:

1. 對小型數據集的適用性： 插入排序在對小型數據集或基本有序的數據集進行排序時表現良好。

2. 適用于鏈表： 插入排序在對鏈表進行排序時也是一種有效的選擇，因為它可以通過改變節點的鏈接來進行排序，而無需移動大量數據。

3. 穩定性： 插入排序是一種穩定的排序算法，即相等元素的相對順序在排序前后保持不變。

2,缺點:

1. 時間復雜度： 插入排序的平均和最壞情況時間復雜度均為O(n^2)，其中n是數組的長度。這使得插入排序在處理大規模數據時效率相對較低，

2. 對逆序數據的性能較差： 當輸入數據基本逆序排列時，插入排序的性能會顯著下降。每次插入都需要移動大量的元素，導致算法效率低下。

二,希爾排序

1.思想

????????插入排序在數組接近有序的時候效率較高,我們就先嘗試讓數組接近有序.再使用插入排序,這是希爾排序

????????基本思想是通過將待排序的元素分組，對每組使用插入排序，然后逐步減小每組的元素數量，最終完成整個序列的排序。希爾排序的主要思想包括以下幾個步驟：

1. 分組數： 選擇一個遞減的序列（，這個序列的最后一個元素通常是1。常見的步長序列選擇有希爾自己提出的 N/2（其中N是數組長度）或其他更復雜的序列。

2. 分組： 將待排序的元素按照步長分成若干個子序列，每個子序列相互獨立。

3. 對每個子序列進行插入排序： 對每個子序列應用插入排序算法，將子序列內的元素進行排序。

4. 減小組： 縮小步長，重復步驟2和步驟3，直到步長為1。

5. 最終插入排序： 當步長為1時，整個序列基本有序，此時使用插入排序對整個序列進行一次排序。

2,實現

void ShellSort(int* a, int n)
{int gap=n;while (gap > 1){gap = gap / 3 + 1;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;}}}
}

????????第一個while循環控制每一組的元素個數,當每一組的元素個數為1是,相當于插入排序,第一個for循環和第二個for循環控制對每一組進行插入排序

時間復雜度:大約O(n^1.3)

空間復雜度O(1)

穩定性:不穩定

3.特點

1.優勢:

1. 相對簡單： 希爾排序的實現相對簡單，不需要使用遞歸，只涉及到循環和插入排序的基本思想。這使得它在理解和實現上相對容易。

2. 原地排序： 希爾排序是一種原地排序算法，它只需要一個常數級別的額外空間用于存儲臨時變量，而不需要額外的數據結構。

3. 相對高效： 對于中等規模的數據集，希爾排序通常比插入排序和冒泡排序等簡單排序算法更高效。它通過逐步減小間隔，先對較遠距離的元素進行排序，然后逐漸縮小間隔，最終完成整體排序。這樣可以使得部分元素在更早的階段就趨于有序，減少了插入排序的工作量。

2.缺點

1. 不穩定性： 希爾排序不是穩定的排序算法。當存在相等元素時，它可能會改變它們的相對順序。在某些應用場景中，需要保持相等元素的相對位置關系，這時候希爾排序可能不是最佳選擇。

2. 不適合小規模數據集： 盡管希爾排序對于中等規模的數據集表現較好，但對于小規模數據集，其性能可能不如一些簡單的排序算法。例如，對于10個或更少的元素，插入排序可能更為高效。