插入排序在算法思想中屬于“減治法”。

減治法的基本思想是：規模為n的原問題的解與較小規模的子問題的解之間具有某種關系。由于存在這種關系，所以只需求解其中一個較小規模的子問題就可以得到原問題的解。

插入排序就是基于“減治法”中的“減一技術”實現的。如果題目要求對a[0]到a[n-1]進行排序，我幻想從a[0]到a[n-2]已經是有序的了，那么我需要做的就是在這些有序的元素中為a[n-1]找到一個合適的位置，然后把它插到那里就行。

雖然插入排序基于遞歸思想，可從頂至下實現；但是，從底至上地實現這個算法——使用迭代會效率更高。從a[1]開始，到a[n-1]為止，a[i]被插入到數組的前i個有序元素中的適當位置上（但是，和選擇排序不同，這個位置一般來說并不是它的最終位置）。

示意圖如下。

C語言代碼如下。

/* a是整形數組的首地址* len是數組長度* 排序結果為非降序*/ void insert_sort(int *a, int len) {int i,j,temp;for(i=1; i<len; ++i){if(a[i-1] <= a[i]) //a[i]已經在合適的位置上了continue; //處理下一個數temp = a[i]; //因為移動元素會覆蓋a[i],所以把a[i]暫存起來j = i-1;while((j >= 0) && (a[j] > temp)){a[j+1] = a[j]; //a[j]向后移動一個位置--j;}a[j+1] = temp; //插入a[i]} }

【參考資料】
《算法設計與分析基礎（第3版）》（清華大學出版社）第4.1節

總結

以上是生活随笔為你收集整理的程序员面试系列——插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。