直接插入排序与希尔排序
直接插入排序（Straight Insertion Sort）：
????????一種最簡(jiǎn)單的排序方法，其基本操作是將一條記錄插入到已排好的有序表中，從而得到一個(gè)新的、記錄數(shù)量增1的有序表。
原理圖如下所示：
圖片取自：1.3 插入排序 | 菜鳥(niǎo)教程
?如上圖所示，默認(rèn)的就是第一位是已經(jīng)排序好的，然后對(duì)第二位和第一位進(jìn)行比較，如果第二位大于第一位，第二位不動(dòng)，然后現(xiàn)在已排序的序列就由一個(gè)變?yōu)榱藘蓚€(gè)了，再由第三位和第二位進(jìn)行比較，如果第三位大于第二位，則不動(dòng)，如果第三位小于第二位，第三位和第二位位置調(diào)換，再和第一位進(jìn)行比較，大了，不換位置，小了，交換位置......
大致原理就說(shuō)明白了，下面來(lái)進(jìn)行代碼的實(shí)現(xiàn)：
void InsertSort(int* arr, int len)
{int tmp = 0;//用來(lái)存儲(chǔ)拿出來(lái)比較的值int j; //出了內(nèi)層for循環(huán)還會(huì)用到j(luò) 所以搞個(gè)全局變量for (int i = 1; i < len; i++) //i代表未排序序列中的第一個(gè)值(默認(rèn)第一個(gè)數(shù)組第一個(gè)已排序完成){arr[i] = tmp;//將該值取出來(lái)賦值給tmp，防止丟失for (j = i - 1; j >= 0; j--){if (arr[j] > tmp){arr[j + 1] = arr[j];}else{break;}}arr[j + 1] = tmp;//因?yàn)閠mp與arr[j]作比較的，如果tmp>arr[j]的話，特沒(méi)譜是插入在arr[j+1]的位置上}
}
希爾排序：
? ? ? ? 希爾排序是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。
該視頻教程簡(jiǎn)單易懂，推薦去看看！
[算法]六分鐘徹底弄懂希爾排序，簡(jiǎn)單易懂_嗶哩嗶哩_bilibilihttps://haokan.baidu.com/v?vid=9577557500401627062&pd=bjh&fr=bjhauthor&type=videohttps://www.bilibili.com/video/BV1rE411g7rW?from=search&seid=12091555806493200736&spm_id_from=333.337.0.0
原理圖如下所示：
?
?
?上述增量之間只有一個(gè)要求------->互質(zhì)，上述我采用了1，3，5這三個(gè)互質(zhì)數(shù)字組成的增量數(shù)組，當(dāng)然你也可以將該增量數(shù)組寫(xiě)成1，3，5，7都是沒(méi)問(wèn)題的
void Shell(int* arr, int len, int gap) //這塊gap = brr[i]
{int tmp = 0;int j;for (int i = gap; i < len; i++){tmp = arr[i];for (int j = i - 1; j >= 0; j -= gap){if (arr[j] > tmp){arr[j + 1] = arr[j];}else{break;}}arr[j + gap] = tmp; //就是將直接插入排序的間隔由1變到了gap}
}void ShellSort(int* arr, int len)
{int brr[] = { 1,3,5 };//增量數(shù)組中一定要有1，最后得把數(shù)組遍歷一遍int len_brr = sizeof(brr) / sizeof(brr[0]);for (int i = 0; i < len_brr; i++){Shell(arr,len,brr[i]);}
}這兩個(gè)排序比較簡(jiǎn)單 就不多敘述了? 到后面的歸并排序，堆排序，快速排序那塊的時(shí)候比較難一些會(huì)說(shuō)的詳細(xì)一些！
希爾排序的代碼實(shí)現(xiàn)和直接插入排序的實(shí)現(xiàn)方法基本一毛一樣，就是直接插入排序的間隔是1，而希爾排序的間隔是個(gè)數(shù)組brr[]，每一輪使用brr[]中的互質(zhì)元素就好！
“堅(jiān)持住少年，堅(jiān)持終會(huì)見(jiàn)到明天的曙光，而大部分人都死在了今天的晚上！”
總結(jié)
以上是生活随笔為你收集整理的直接插入排序与希尔排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
