前言：

本文主要講解插入排序中的直接插入排序和希爾排序。

1、直接插入排序：

1.1基本思想

直接插入排序是一種簡(jiǎn)單的插入排序法，其基本思想是把待排序的數(shù)值按照大小順序逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到將所有記錄插入完為止，得到一個(gè)新的有序序列。

實(shí)際中我們玩撲克牌時(shí)，就用了插入排序的思想。

下面的圖片就是插入排序的整體過(guò)程，第一步認(rèn)為5是一個(gè)有序區(qū)間，然后2比5小，就讓5向后移，前面填充2，又形成一個(gè)有序的序列，以此類推……

原碼：

外層的循環(huán)相當(dāng)于每次插入的撲克牌，內(nèi)層循環(huán)決定了這張撲克牌怎么插，插在哪里

void StraightInsert(int arr[], int n)
{//[0-end]有序，插入end+1位置的數(shù)，使得[0-end+1]序列仍然有序for (int i = 0;i<n-1;i++){int end = i;int tmp = arr[i + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}elsebreak;}arr[end + 1] = tmp;}
}

時(shí)間復(fù)雜度：

時(shí)間復(fù)雜度計(jì)算的是完成程序的次數(shù)，不能只看是雙層循環(huán)就 武斷 O(N^2)！

前面講過(guò)時(shí)間復(fù)雜度計(jì)算的是最差的情況，最差的情況就是將逆序的排成升序的，1+2+3+……n-1，這是一共累加的次數(shù)，求和發(fā)現(xiàn)這是一個(gè)等差數(shù)列求和，最高項(xiàng)就是N^2，因此時(shí)間復(fù)雜度就是O(N^2)。

最好的情況下本來(lái)就是順序，end位置的值都需要跟前面一個(gè)比較，所以就是O(N)。

2、希爾排序

2.1概念：

希爾排序是一種特殊的直接插入排序，也算是直接插入排序的優(yōu)化版本。

2.2思想：

我們發(fā)現(xiàn)在一些直接插入排序的例子時(shí)，發(fā)現(xiàn)其實(shí)一些排序是很接近O(N)。

比如1，2，5，3，6

因此我們想先進(jìn)行預(yù)排序（讓原來(lái)的排序更接近有序），接著再進(jìn)行直接插入排序。

2.3預(yù)排序

何為預(yù)排序？

預(yù)排序就是分組排，間隔為gap的為一組，注意 組數(shù)==gap的值

預(yù)排序的規(guī)律：（重要）

• 多組間隔為gap的預(yù)排序，gap從大到小
• gap越大：大的數(shù)可以越快的到后面，小的數(shù)可以越快的到前面。
• gap越大，預(yù)排序越不接近有序
• gap越小，預(yù)排序越接近有序
• gap==1時(shí)，就是直接插入排序。

那gap到底是多少呢？

這個(gè)問(wèn)題較難回答，這個(gè)問(wèn)題沒(méi)有官方的答案。

首先gap不可能是一個(gè)固定的數(shù)，應(yīng)該與數(shù)組的長(zhǎng)度n相關(guān)，我們一般采用gap ==? n/ 2的表達(dá)式來(lái)去定義gap的值，因?yàn)橐ＷC最后gap要被除到1為止

原碼：

void ShellSort(int arr[], int n)
{int gap = n;while (gap > 1){gap = gap / 3+1;for (int i = 0; i < n - gap; i++)//這里的循環(huán)判斷條件也很有講究，正好能將多組gap排完{int end = i;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];//將數(shù)據(jù)往后移end -= gap;}elsebreak;}arr[end + gap] = tmp;}}
}

通過(guò)代碼，我們不難發(fā)現(xiàn)預(yù)排序大部分的代碼內(nèi)容與直接插入排序是一樣的，只不過(guò)將1換成了gap而已。

預(yù)排序需要排很多次，真的比直接插入排序快嘛？

我們自己可以比較這兩種排序方式上的時(shí)間差距，經(jīng)過(guò)比較我們發(fā)現(xiàn)，直接插入排序的時(shí)間要比希爾排序的時(shí)間多上100倍左右！（隨著N的增大，時(shí)間差也會(huì)增大）

時(shí)間復(fù)雜度

首先外層的while循環(huán)執(zhí)行的次數(shù)是logN，內(nèi)層的循環(huán)當(dāng)gap很大時(shí)，執(zhí)行次數(shù)是N，當(dāng)gap很小時(shí)，執(zhí)行次數(shù)也接近于N，所以最終的時(shí)間復(fù)雜度O(logN*N)。

注意N^2與N*logN兩者并不是一個(gè)量級(jí)的，特別是當(dāng)N的數(shù)非常大時(shí)。

一些書(shū)上直接給出了結(jié)論O(N^1.3)。