問題描述：

????排序問題：

????輸入：N個數(shù)的一個序列<a1,a2,a3,...,an>。

????輸出：輸入序列的一個序列<a1',a2',a3',...,an'>,滿足a1'<=a2'<=a3'<=...<=an'。

雖然排序的是一個序列，但實(shí)際上來說，輸入的是有N個元素的數(shù)組。所以每一個被排序的數(shù)在排序過程中被稱為關(guān)鍵字key。

插入排序的過程：

遍歷數(shù)組中的每個關(guān)鍵字key，將它的位置空出來，然后從key開始往前遍歷，直到找到找排在他前面的比它小的value，key之前value之后的這一段序列后移，然后將key插入到value后面，這就完成了一次插入。

具體實(shí)現(xiàn)：

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

行號???????? 算法語句??????? ?????????????? 執(zhí)行次數(shù)? ??? ????代價(jià) c_i

1????? ??? int i,j,key;??????? ??????????????? ??????1????? ??? ?????????????????

2????? ??? for (j=1;j<=length;j++)???? ???????n+1 ? ???????????????????

3????? ??? key=array[j]; ??????????????????????????n? ? ? ? ? ? ? ????????? ?

4????? ??? i=j-1;?????? ??????????????????????????????? n? ? ? ? ? ? ? ? ?????????

5????? ??? while(i>=0&&array[i]>key) ??????? ??? ?????????????????????????

6????? ??? array[i+1]=array[i];????? ???????????????????????????????? ??

7????? ??? i=i-1;?????? ????????????????? ????????????????? ??? ? ? ? ? ? ? ? ?

8????? ??? array[i+1]=key;???? ????????????????????????? n? ? ? ? ? ? ? ? ??????????????????

9????? ??? return array;? ?????????????????????????????????? 1????? ???????????????????????????

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

將上面的式子合并相同的項(xiàng)，得到：

可以看到，第 2 至第 4 項(xiàng)的系數(shù)以及第八項(xiàng)都是 n，因此可以將它們合并為 4cn?的形式，其中 ，即：

在插入排序算法的最壞情況下，數(shù)組的元素按照降序排列，即每個元素都要移動到它應(yīng)該插入的位置，因此第 j?個元素需要移動 j-1?次，因此：

將 ?代入 ，得到：

因此，在最壞情況下，可以轉(zhuǎn)化為 。將其代入原式，得到：

因此，在最壞情況下，該插入排序算法的時(shí)間復(fù)雜度仍然是 ，其中 為數(shù)組長度。

輸出非增序列：

要輸出非增序列，需要對插入排序算法做一些修改。在原始算法中，每次將一個元素插入已排序序列中的適當(dāng)位置，這樣可以得到遞增的序列。為了得到非增序列，需要修改插入操作的邏輯，即如果插入的元素小于或等于已排序序列中的某個元素，則將其插入到該元素的后面，否則插入到序列的最前面。

本文給出示例代碼如下：

至此，插入排序完畢。