?
目錄
一. 導入
二. 直接插入排序
? ? ? ? 2.1 基本思想
? ? ? ? 2.2 過程分析
????????2.3 代碼實現(xiàn)
? ? ? ? 2.4 復雜度/穩(wěn)定性分析
三. 希爾排序(縮小增量排序)
? ? ? ? 3.1 基本思想
? ? ? ? 3.2 過程分析?
????????3.3 代碼實現(xiàn)?
????????3.4 復雜度/穩(wěn)定性分析
?一. 導入
? ? ? ? 本期是排序篇的第二期，我們的主角是插入排序。在座的各位或多或少都玩過撲克牌吧！我們在摸撲克牌時，往往會將大牌插到小牌后面，小牌插到大牌前面。當摸完所有的牌后，我們手中的牌自然也就有序了，這實際上就是用到了插入排序的思想
本期要點
- 對直接插入排序進行解析
- 對希爾排序進行解析
- 兩種插入排序的復雜度和穩(wěn)定性進行分析
二. 直接插入排序
? ? ? ? 2.1 基本思想
? ? ? ? 插入排序的基本思想是：把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。
? ? ? ? 2.2 過程分析
? ? ? ? 我們可以將第一個元素作為一個有序序列，從第二個元素開始插入到這個有序序列中，過程如下：
以升序為例：
當插入第i個元素時(i>=1)，說明前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，我們將array[i]位置的值從后往前與array[i-1],array[i-2],…依次進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。
為什么不從前往后開始進行比較？
如果我們從前往后進行比較，當找到插入位置時，根據(jù)順序表的插入我們知道：必須先將后面的元素全部后移，而后移又不能從前往后移，否則會造成元素覆蓋，我們必須從后往前移動。折騰了半天又要從后往前遍歷，那為什么不一開始就從后往前比較，在比較的同時一并挪動元素，何樂而不為呢？
? ? ? ? 單趟插入動圖：
????????全過程動圖
?????????2.3 代碼實現(xiàn)
//插入排序
void InsertSort(int* a, int n)
{
assert(a); //確保a不為空
int end;
for (int i = 1; i < n; i++) //從第二個元素開始插入，下標為1
{
int tmp = a[i];
end = i - 1; //前面的元素已經(jīng)有序，從末端，也就是i-1處開始比較
while (end >= 0) //查找插入位置
{
if (a[end] > tmp) //大于則往后挪動數(shù)據(jù)
{
a[end + 1] = a[end];
end--;
}
else //a[end] <= tmp，找到插入位置，跳出循環(huán)
{
break;
}
}
a[end + 1] = tmp; //在合適位置插入
}
}
? ? ? ? ?2.4 復雜度/穩(wěn)定性分析
? ? ? ? ? 復雜度
? ? ? ? ?根據(jù)上面的動圖我們可以發(fā)現(xiàn)，當元素集合越接近有序，直接插入的時間效率越高，當元素集合已經(jīng)有序時，時間復雜度便是O(N)，即遍歷一遍數(shù)組（最優(yōu)情況）。
? ? ? ? ?而時間復雜度我們看的是最壞情況，即數(shù)組元素逆序的情況。此時每次插入相當于頭插，而頭插的時間復雜度為O(N)，因此總時間復雜度為O( 插入次數(shù) * 單次插入時間復雜度 ) =?。
? ? ? ? ?而除了待排序數(shù)組之外只有常數(shù)級的輔助空間，空間復雜度為O(1)。
? ? ? ? ? 穩(wěn)定性
? ? ? ? ? 由于我們是大于tmp才進行元素挪動，當?shù)扔趖mp時直接將tmp放到后方，不會對相同元素的順序進行改變，因此直接插入排序是穩(wěn)定的排序
? ? ? ? ?
三. 希爾排序(縮小增量排序)
? ? ? ? 3.1 基本思想
? ? ? ? ?希爾排序又稱縮小增量法，其基本思想是：選出一個整數(shù)gap表示增量，根據(jù)gap將待排序的記錄分為gap組，所有距離為gap的記錄分在同一組，然后對每一組進行直接插入排序。隨著排序次數(shù)的增多，增量gap逐漸減少，當gap=1時，即所有記錄分在同一組進行直接插入排序，排序完成后序列便有序了，算法結(jié)束。分組方法如下：
? ? ? ? 3.2 過程分析?
- 首先，我們需要對gap的初始值進行確定，這并沒有一個確定的答案，一般是按照數(shù)據(jù)量來進行選取。一般我們選取gap = n/3 + 1或者gap = n/2作為gap的初始值。
- 根據(jù)算法的思想，我們觀察到gap是在不斷地進行縮小，最后縮小到1進行直接插入排序。因此我們gap的縮小增量可以繼續(xù)使用gap = gap/3 + 1或gap = n/2來表示。
- 對1、2點進行合并后，我們可以這樣用來表示gap的迭代更新：
int gap = n; //n為序列元素個數(shù)
while(gap > 1)
{
//gap = gap/2;
gap = gap/3 + 1;
//每組進行直接插入排序
//...
}上面的循環(huán)在以下兩種情況下會結(jié)束：
- n == 1：即序列只有一個元素，此時無需進行排序，不會進入循環(huán)
- n != 1 ，gap == 1：由于gap的更新是在插入排序之前，因此當循環(huán)判斷到gap == 1時，上一次進行的就是以1為gap增量的直接插入排序，此時序列已經(jīng)有序，退出循環(huán)。
為什么要取gap = gap/3 + 1而不是gap = gap/3？
由于最后gap要縮小到1進行直接插入排序，而如果我們選取gap = gap/3時，假設gap初始為6，第一次更新后gap=2，第二次更新后gap=0(向下取整)，循環(huán)便結(jié)束了，并不會進行g(shù)ap=1時的插入排序。因此，為了避免這種情況的發(fā)生，我們讓gap = gap/3 + 1保證最后一次gap一定為1。
那為什么取gap = gap/2而不是gap = gap/2 + 1？
這種情況不需要處理的原因是gap不可能等于0，因為進入循環(huán)的條件是gap>1,而gap只有等于0或1時gap/2才會為0。因此，無論gap初始為多少，最后一定都會在gap=1處停下。并且，當gap=2時，使用gap = gap/2 + 1會出現(xiàn)死循環(huán)噢
? ? ? 4. 每組之間進行的就是我們上面介紹的直接插入排序，不一樣的是相鄰元素的距離是gap而不是1。以下是gap = 3時的單趟希爾排序的動圖過程：
? ? ? ? 5. 下面是希爾排序的全過程（以gap = gap/3 + 1為例）：
?? ? ? ? 6. 通過觀察，我們可以發(fā)現(xiàn)實際上希爾排序就是直接插入排序的優(yōu)化版。隨著每一趟的分組排序，序列越來越接近有序。前面我們說過，直接插入排序在序列越接近有序的情況下效率越高，希爾排序就是通過每趟的預排序來使得序列越來越接近有序，從而提高直接插入排序的整體效率。
????????7. 要點提煉：當gap > 1時，對序列進行分組預排序，目的是使得序列越來越接近有序；當gap == 1時，數(shù)組接近有序，此時進行直接插入排序效率大幅提高。
?????????3.3 代碼實現(xiàn)?
//寫法1：一組一組排
void ShellSort1(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//1：gap > 1,預排序
//2：gap == 1，直接插入排序
gap = gap / 3 + 1; //縮小增量
for (int j = 0; j < gap; j++) //一組一組進行插入排序，共gap組
{
//對當前組進行直接插入排序,組內(nèi)相鄰元素相距gap。
//(其實就相當于把上面介紹的直接插入排序代碼中的-1改成-gap即可)
for (int i = j; 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;
}
}
}
}但是，上面的代碼實際上還可以寫得更加簡潔
我們知道每個組的元素都相距gap，而組與組之間距離都為1。那么，我們實際上不用一組一組分開排，而是采用多組并排的方式，這樣就可以少寫一個for循環(huán)，代碼如下
//寫法2：多組并排
void ShellSort2(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//1：gap > 1,預排序
//2：gap == 1，直接插入排序
gap = gap / 3 + 1; //縮小增量
for (int i = 0; i < n - gap; i++) //多組并排，i就不是+gap了，而是+1，排下一組的元素
{
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;
}
}
}?????????3.4 復雜度/穩(wěn)定性分析
? ? ? ? ? 復雜度
? ? ? ? ?盡管上面的代碼有多個循環(huán)嵌套，但這并不意味著希爾排序的效率低下。我們根據(jù)代碼來分析一下希爾排序的時間復雜度，過程如下圖所示：
? ? ? ? ?我們可以看到，在gap很大或者gap很小的情況下，每趟排序的時間復雜度為O(N)，共進行趟，那我們是不是可以認為希爾排序的時間復雜度為O(NlogN)？實際上并不行，因為當gap處于中間的過程時，時間復雜度的分析實際上是個很復雜的數(shù)學問題。每一趟預排序之后都對下一趟排序造成影響，這就好比疊buff的過程。
以下分別是兩本書中對希爾排序時間復雜度的說法：
1、《數(shù)據(jù)結(jié)構(gòu)(C語言版)》--- 嚴蔚敏
?2、《數(shù)據(jù)結(jié)構(gòu)-用面相對象方法與C++描述》--- 殷人昆
? ? ? ? ?因為我們上面的gap是按照Knuth提出的方式取值的，并且Knuth進行了大量的試驗統(tǒng)計，時間復雜度我們就按照：到來進行取值。
? ? ? ? ?然后就是空間復雜度，由于我們依舊只用到了常數(shù)級的輔助變量，因此空間復雜度為O(1)。
? ? ? ? ? 穩(wěn)定性
? ? ? ? ??由于希爾排序是分組進行排序，當相同的數(shù)被分到不同組時，很可能就會改變相同的數(shù)的順序，因此，希爾排序是不穩(wěn)定的排序。?
以上，就是本期的全部內(nèi)容啦??文章來源：http://www.zghlxwxcb.cn/news/detail-621621.html
制作不易，能否點個贊再走呢??文章來源地址http://www.zghlxwxcb.cn/news/detail-621621.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】手撕排序NO.2----直接插入排序與希爾排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
