1、基本思想：

? ???? 已知待排序列r[1...n],先將序列中的第一個(gè)記錄看成是一個(gè)有序的子序列，然后從第二個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成關(guān)鍵字非遞減有序序列為止。 具體操作如下：

??? （1）查找出r[i]在有序序列r[1...i-1]中的插入位置k;

??? （2）將r[k...i-1]中所有元素全部后移一個(gè)位置；

??? （3）將r[i]復(fù)制到r[k],則原r[1...r-1]的有序序列變成了一個(gè)r[1...i]的有序序列。

2、直接插入排序算法：

void InsertSort(ElemType A[],int n){int i,j;for(i = 2;i <= n;i++){                   //依次將A[2]~A[n]插入到前面已排序序列if(A[i].key < A[i-1].key){           //若A[i]的關(guān)鍵碼小于其前驅(qū)，需將A[i]插入有序表A[0] = A[i];                     //復(fù)制為哨兵，A[0]不存放元素for(j=i-1;A[0].key<A[j].key;--j) //從后往前查找待插入位置A[j+1]=A[j];                 //向后挪位A[j+1]=A[0];                     //復(fù)制到插入位置}}
}

3、性能分析：

? ?? （1）空間復(fù)雜度：僅使用了常數(shù)個(gè)輔助單元，因而空間復(fù)雜度為O(1)；

???? （2）時(shí)間復(fù)雜度：①最好情況下，表中元素已經(jīng)有序，此時(shí)每插入一個(gè)元素，都只需比較一次而不用移動元素，因而時(shí)間復(fù)雜度為O(n);②最壞情況下，表中元素順序剛好與排序結(jié)果中元素順序相反時(shí)，總的比較次數(shù)達(dá)到最大，為，總的移動次數(shù)也達(dá)到最大，為;③平均情況下，考慮待排序表中元素是隨機(jī)的，此時(shí)可以取上述最好與最壞情況的平均值作為平均情況下的時(shí)間復(fù)雜度，總的比較次數(shù)與總的移動次數(shù)均約為n2/4。由此，直接插入排序算法的時(shí)間復(fù)雜度為O(n2)

????? （3）直接插入排序是一個(gè)穩(wěn)定的排序方法。

????? （4）直接插入排序算法適用于順序存儲和鏈?zhǔn)酱鎯?/span>的線性表。

4、參考文獻(xiàn)：

????? [1]《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴(yán)蔚敏、吳偉民編著，清華大學(xué)出版社，ISBN：978-7-302-14751-0

????? [2]《2019年數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)指導(dǎo)》，王道論壇.組編，中國工信出版集團(tuán)、電子工業(yè)出版社，ISBN：978-7-121-33708-6
?

轉(zhuǎn)載于:https://www.cnblogs.com/yzdx/p/10747623.html

總結(jié)

以上是生活随笔為你收集整理的排序算法之直接插入排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。