??前言
大家好啊！本文阿輝講介紹插入排序和希爾排序，并將解釋為什么希爾排序比插入排序更快。
??插入排序（insertsort）
??原理
插入排序，實際上是我們平時都使用過的排序，為什么這么說呢??？想必大家都玩過撲克牌吧，大家是如何整理手中的牌的呢？一定是想下面這樣對吧??
沒錯，插入排序也是的么實現(xiàn)的
其實關(guān)于插入排序，一句話足以概括：對于要排序的數(shù)據(jù)，從前往后遍歷所有數(shù)據(jù)，遍歷到的數(shù)據(jù)與之前的數(shù)據(jù)進行比較，以升序為例，若遍歷位置的數(shù)據(jù)比前一個數(shù)據(jù)小兩者就交換，然后接著與前一個位置比較如果還小就繼續(xù)交換，直到比前一個數(shù)據(jù)大就停止交換
給鐵子們上動圖??
??代碼實現(xiàn)（coding）
對于插入排序，我們需要兩個循環(huán)來控制，一個循環(huán)來遍歷所有數(shù)據(jù)，另 一個循環(huán)用來遍歷已排好序的部分與要插入數(shù)據(jù)比較
coding
void insertsort(int arr[],int sz){
int insert = 0;//遍歷要插入的位置
for(insert = 1;insert < sz;insert++){
int cur = insert;//記錄待排序的位置
int pre = cur - 1;//記錄待排序的前一個位置
while(arr[cur] < arr[pre] && cur > 0){//沒前一個位置大就交換，待排序位置來到0位置就退出循環(huán)
int tmp = arr[cur];
arr[cur] = arr[pre];
arr[pre] = tmp;
--cur,--pre;//待排序位置和前一個位置同時--
}
}
}
??總結(jié)
穩(wěn)定性的定義
說到穩(wěn)定性，與之對應(yīng)就是不穩(wěn)定性，那么排序算法的穩(wěn)定性又為何意呢？通俗地講就是，能保證排序前兩個相等的數(shù)其在序列的前后位置順序與排序后它們的前后位置順序一致。形式化解釋如下：一列數(shù)中，如果Ai = Aj，Ai位于Aj的前置位，那么經(jīng)過升降序排序后Ai仍然位于Aj的前置位
阿輝之前介紹的 冒泡和選擇排序和今天的插入排序，到現(xiàn)在排序中三個最挫的排序已經(jīng)介紹完了，這三個的時間復(fù)雜度都是O(n2),選擇排序是最挫的，冒泡和插入排序都可以做到有穩(wěn)定性而選擇排序做不到
為什么選擇排序不行，一個簡單的例子就能解釋
比如一串數(shù)字 83482，一趟選擇下來，第一個8與2交換，這樣第一個8和第二個8之間的穩(wěn)定性就被打破了
??希爾排序（shellsort）
希爾排序（Shell Sort）是一種基于插入排序的排序算法，也被稱為“縮小增量排序”（Diminishing Increment Sort）。它通過將整個列表分割成多個較小的子序列，并對這些子序列進行插入排序，從而逐步減少排序的范圍，最終完成整個列表的排序。希爾排序在提供了一種平衡了性能和簡單性的排序方法。
好吧上面百度粘的說得不是人話
其實希爾排序就是將數(shù)據(jù)分組，在每個組內(nèi)進行插入排序（對就是直接進行插入排序），那么如何分組呢？設(shè)置一個增量序列，開始的增量通常是數(shù)組長度的一半，然后下一次增量減半，增量設(shè)為gap，給鐵子們上圖
??代碼實現(xiàn)（coding）
void shellsort(int arr[],int sz){
for(int gap = sz/2;gap > 0;gap /= 2){
for(int i = gap;i < n;++i){//i從每組的第二個數(shù)遍歷，因為每組的第一個數(shù)不用進行插入排序
int k = arr[i];//記錄當前進行插入排序的數(shù)據(jù)
for(int j = i;j >= gap && k < arr[j - gap];j -= gap)//如果待插入的數(shù)據(jù)比前一個數(shù)據(jù)小就將前一個數(shù)移到待排序的位置，接著與下一個位置比較
arr[j] = arr[j-gap];
arr[j] = k;//最后將要插入的數(shù)據(jù)插到合適的位置
}
}
}
希爾排序沒有穩(wěn)定性，是阿輝介紹的第一個時間復(fù)雜度突破O(n2)的排序，時間復(fù)雜度在O(nlogn)~O(n2)之間，有同學(xué)可能會問為啥僅僅分了各組就讓希爾排序更快了，問的好重點來了
??為啥希爾排序能比插入排序更快
其實一個列子就能讓你明白，比如下列這個數(shù)組：
對于最后的1插入排序需要交換5次才能來到正確的位置
而如果使用希爾排序，對于第一個增量3，1將與8一組，一次交換就讓1跨過了3和4下標的位置，從而少了2次交換，所以希爾排序比插入排序更快，它降低了交換的次數(shù)文章來源：http://www.zghlxwxcb.cn/news/detail-787666.html
其實，阿輝介紹的這些比較挫的排序，之所以挫就是因為它們大量浪費了交換，后續(xù)阿輝介紹的時間復(fù)雜度在O(nlogn)的排序都減少了交換的次數(shù)
文章來源地址http://www.zghlxwxcb.cn/news/detail-787666.html
到了這里，關(guān)于【排序算法】插入排序與希爾排序，你不想知道為什么希爾比插入更快嗎？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
