版權聲明：本文為博主原創文章🥨，遵循 CC 4.0 BY-SA 版權協議👨👩👧👦，轉載請附上原文出處鏈接和本聲明😖。
本文鏈接：https://blog.csdn.net/tianxiawushanu/article/details/142660275
1. 排序的概念及其應用
在正式講解插入排序和希爾排序之前😆，我要帶著大家理解我們為什麽需要排序😢？以及排序在我們生活中有什麽應用？學完這些之後，大家也許對排序算法就不會那麽迷茫了。
1.1 排序的概念
排序：所謂排序🍉，就是使一串記錄，按照我們特定且可行的想法👯♂️，遞增或遞減的排列起來的操作。
排序是一項操作！
1.2 排序的應用
看到這裏，大家可以打開京東商城，當你想買一臺新的手機時🧑🏿🦱，卻不知如何入手。你可能會選擇按好評數來進行排序👂🏽，從而選出好評率最高的手機。在這個過程，就用到了排序的思想🫷🏻。
再如，我們的大學按照教學資源以及教學能力，也能進行排序🤸🏻：
當然，生活中還有很多例子都是用到了排序的思想🤦🏿♀️。這就是所謂處處有排序！
好了◾️，在了解完排序的重要性之後，我們就要正式邁入學習插入排序和希兒排序的殿堂中了。
2. 插入排序
插入排序，通常我們也稱它為直接插入排序🦹🏼♀️。
2.1 基本思想
在一個有序的數組中，按照一定的規則插入待排序的數字。
詳細一點說的話👱🏻♂️，就是🏊♂️：
算法思路：
先從單趟排序講起，我們可以選擇待插入的數字與從排序好的數組末端的數進行比較🌄。若發現該值比待插入的數字要大，則將蓋子往後挪動一位🧎，接著繼續往前面進行比較。若發現該值比待插入的數字要小，說明該值的後面一個位置就是待插入數字應該插入的位置🐕🦺，我們就可以結束循環了💍。
單趟排序講完了之後🤰，就可以將一個完整的插入排序了。
如果你真的認證解讀了單趟插入排序的思路，你會發現插入排序不過如此！
其實一個完成的插入排序就是在循環地跑單趟排序⏳🎒，循環地初始條件為從待插入數組的第二個元素小標開始。每當單趟排序跑完之後，我們都得設置循環條件的值(一開始比較數組末端的位置)🤵🏿♀️。因為你已經排好了部分數組，每當來一個新數字就得在拍好數組中插入，重復上述過程👰🏼♀️。
下面我給大家展示插入排序算法的動圖，希望大家能夠結合上述的話語👩🏭，仔細觀看：
2.2 插入排序的代碼實現
void InsertSort(int* a, int n){
for (int i = 1; i < n; i++)
{
int end = i - 1; //待排序數組的末端
//也可以寫成int tmp = a[end + 1];
int tmp = a[i]; //tmp存放的是待插入的數值
while (end >= 0)
{
if (tmp < a[end]) //待插入數字與數組末端的值進行比較
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
2.3 插入排序算法總結
根據上面的代碼，我們可以總結出一些關於插入排序算法的特征：
元素集合越接近有序🧙，直接插入排序算法的時間效率就越高
- 時間復雜度🤸🏿：O(N^2)
- 空間復雜度：O(1)
🧏🏼，它是一種穩定的排序算法
穩定性：穩定
3. 希爾排序
希爾排序又稱縮小增量排序🤵🏻。
3.1 基本思想
先選定一個整數(gap)，把待排序的數據分成個別組🧝🏽♂️🆑。分組的標準就是所有距離為gap的數據分在同一組，並對每一組內的記錄進行排序。然後，縮小gap的值🚏，重復上述分組和排序的工作🤽🏿♂️。當gap = 1時，就相當於直接插入排序了😫。
上面這個思想很重要，是理解希爾排序的核心👩👩👦！
給大家舉個例子🤸🏻♂️：
3.2 希爾排序的代碼實現
void ShellSort(int* a, int n){
int gap = n;
while (gap > 1)
{
//gap /= 2;
gap = gap / 3 + 1;
for (int j = 0; j < gap; j++)
{
//就是在對每組(隔gap位置的數字)的數據進行插入排序
for (int i = j; i < n; i += gap)
{
int end = i - 1;
int tmp = a[i];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
}
3.3 希爾排序的特征總結
