【概述】

直接插入排序是一種穩(wěn)定的排序方法，其是插入排序中最簡(jiǎn)單的排序方法，類似于玩撲克時(shí)整理手牌的過(guò)程。

其基本思想是：依次將待排序序列中的每一記錄插入到一個(gè)已排好序的序列中，直到全部記錄都排好序。

其實(shí)現(xiàn)依靠雙重循環(huán)完成，外層循環(huán)執(zhí)行 n-1 次，內(nèi)層循環(huán)執(zhí)行次數(shù)取決于第 i 個(gè)記錄前有多少個(gè)記錄的關(guān)鍵碼大于第 i 個(gè)記錄的關(guān)鍵碼。

【排序過(guò)程】

1.排序過(guò)程

具體的排序過(guò)程為：

將整個(gè)待排序的記錄序列劃分為有序區(qū)和無(wú)序區(qū)，初始時(shí)有序區(qū)為待排序記錄序列中的第一個(gè)記錄，無(wú)序區(qū)包括所有剩余待排序的記錄

將無(wú)序區(qū)的第一個(gè)記錄插入到有序區(qū)的合適位置中，從而使無(wú)序區(qū)減少一個(gè)記錄，有序區(qū)增加一個(gè)記錄

重復(fù)執(zhí)行步驟 2，直到無(wú)序區(qū)中沒(méi)有記錄位置

2.實(shí)例

初始關(guān)鍵字： ?『?6，5，3，1，8，7，2，4?』

第一趟排序： 『?6?』，5，3，1，8，7，2，4?

第二趟排序： 6，5，3，1，8，7，2，4

? ? ? ? ? ? ? ? ? ? ? 『?6，5?』，3，1，8，7，2，4

第三趟排序： 5，6，3，1，8，7，2，4

?? ? ? ? ? ? ? ? ? ? ? 5，『6，3』，1，8，7，2，4

?? ? ? ? ? ? ? ? ? ? ? 『5，3』，6，1，8，7，2，4

第四趟排序： 3，5，6，1，8，7，2，4

?? ? ? ? ? ? ? ? ? ? ? 3，『5，1』，6，8，7，2，4

?? ? ? ? ? ? ? ? ? ? ?『?3，1』，5?，6，8，7，2，4

第五趟排序：?1，3，5?，6，8，7，2，4

?? ? ? ? ? ? ? ? ? ? ? 1，3，5，『6，8』，7，2，4?

第六趟排序：?1，3，5?，6?，8，7，2，4

?? ? ? ? ? ? ? ? ? ? ??1，3，5，6，『8，7』，2，4?

?? ? ? ? ? ? ? ? ? ? ??1，3，5，『6，7』，8，2，4?

第七趟排序：?1，3，5?，6?，7，8，2，4

?? ? ? ? ? ? ? ? ? ? ??1，3，5，6，7，『8，2』，4

?? ? ? ? ? ? ? ? ? ? ??1，3，5，6，『7，2』，8，4

?? ? ? ? ? ? ? ? ? ? ??1，3，5，『6，2』，7，8，4

?? ? ? ? ? ? ? ? ? ? ??1，3，『5，2』，6，7，8，4

?? ? ? ? ? ? ? ? ? ? ??1，『3，2』，5，6，7，8，4

?? ? ? ? ? ? ? ? ? ? ??『1，2』，3，5，6，7，8，4

第八趟排序：?1，2，3，5，6，7，8，4

?? ? ? ? ? ? ? ? ? ? ??1，2，3，5，6，7，『8，4?』

?? ? ? ? ? ? ? ? ? ? ??1，2，3，5，6，『7，4』，8

?? ? ? ? ? ? ? ? ? ? ??1，2，3，5，『6，4』，7，8

?? ? ? ? ? ? ? ? ? ? ??1，2，3，『5，4』，6，7，8

?? ? ? ? ? ? ? ? ? ? ??1，2，『3，4』，5，6，7，8

?結(jié)果： ? ? ???『??1，2，3，4，5，6，7，8 ?』

?? ????????

? ? ? ? ? ? ? ? ? ?排序過(guò)程?????????????????????????????????????????????????????????宏觀過(guò)程

【時(shí)空復(fù)雜度分析】

在最好的情況下，待排序序列為正序，每趟排序只需與有序序列的最后一個(gè)記錄的關(guān)鍵碼比較一次，移動(dòng)兩次記錄，那么總的比較次數(shù)為 n-1，總的移動(dòng)次數(shù)為 2(n-1)，因此，最優(yōu)時(shí)間復(fù)雜度為 (n)

在最壞的情況下，待排序序列為逆序，第 i 趟插入時(shí)，第 i 個(gè)記錄必須與前面的 i-1 個(gè)記錄的關(guān)鍵碼與哨兵比較，并且每比較一次就要做一次記錄的移動(dòng)，那么總的比較次數(shù)為 (n+2)(n-1)/2，總的移動(dòng)次數(shù)為 (n+4)(n-1)/2，因此，最壞時(shí)間復(fù)雜度為 O(n^2)

在平均情況下，待排序序列中各種可能排列的概率情況相同，在插入第 i 個(gè)記錄時(shí)平均要比較有序區(qū)中全部記錄的一半，那么總的比較次數(shù)為 (n+2)(n-1)/4，總的移動(dòng)次數(shù)為 (n+4)(n-1)/4，因此，平均時(shí)間復(fù)雜度為 O(n^2)

直接插入排序只需要一個(gè)記錄的輔助空間，用于作為待插入記錄的暫存單元和查找記錄的插入位置過(guò)程中的哨兵。?

【源程序】

void insertSort(int a[],int n){for(int i=2;i<=n;i++){int temp=a[i];//暫存待插入關(guān)鍵碼，并設(shè)置哨兵int j=i-1;while(temp<a[j]&&j>=1){//尋找插入位置a[j+1]=a[j];//記錄后移j--;}if(j!=i-1)//防止自我插入a[j+1]=temp;} }

總結(jié)

以上是生活随笔為你收集整理的理论基础 —— 排序 —— 直接插入排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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