Copyright ? 1900-2016, NORYES, All Rights Reserved.

http://www.cnblogs.com/noryes/

歡迎轉載，請保留此版權聲明。

-----------------------------------------------------------------------------------------

?

?

?

?

基本思想:

?

?

?

? ? 將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。

?

?

?

? ? 要點：設立哨兵，作為臨時存儲和判斷數組邊界之用。

?

?

?

? ? 直接插入排序示例：

?

?

?

?

?

?

?

?

? ? 如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。

?

?

?

算法實現：

?

?

?

?

void?print(int?a[],?int?n?,int?i){??

????cout<<i?<<":";??

????for(int?j=?0;?j<8;?j++){??

????????cout<<a[j]?<<"?";??

????}??

????cout<<endl;??

}??

??

??

void?InsertSort(int?a[],?int?n)??

{??

????for(int?i=?1;?i<n;?i++){??

????????if(a[i]?<?a[i-1]){???????????????//若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入??

????????????int?j=?i-1;???

????????????int?x?=?a[i];????????//復制為哨兵，即存儲待排序元素??

????????????a[i]?=?a[i-1];???????????//先后移一個元素??

????????????while(x?<?a[j]){??//查找在有序表的插入位置??

????????????????a[j+1]?=?a[j];??

????????????????j--;?????????//元素后移??

????????????}??

????????????a[j+1]?=?x;??????//插入到正確位置??

????????}??

????????print(a,n,i);???????????//打印每趟排序的結果??

????}??

??????

}??

??

int?main(){??

????int?a[8]?=?{3,1,5,7,2,4,9,6};??

????InsertSort(a,8);??

????print(a,8,8);??

}??

?

?

?

?

?

?

?

效率：

?

?

?

時間復雜度：O（n^2）.

?

?

?

其他的插入排序有二分插入排序，2-路插入排序。

?

?

?

?weiss 代碼

1 /* 2 * Simple insertion sort. 3 */ 4 template <class T> 5 void DLLALGOLIB insertionSort(std::vector<T>& coll) 6 { 7 for (int idx = 1; idx < (int)coll.size(); ++idx) 8 { 9 T tmp = coll[idx]; 10 11 int j = idx; 12 for (; j > 0 && tmp < coll[j - 1]; --j) 13 { 14 coll[j] = coll[j - 1]; 15 } 16 17 coll[j] = tmp; 18 19 PRINT_ELEMENTS(coll); 20 } 21 } 22 23 24 /* 25 * STL insertion sort. 26 */ 27 template <class Iterator> 28 void DLLALGOLIB insertionSort(const Iterator& begin, const Iterator& end) 29 { 30 if (begin != end) 31 { 32 insertionSortHelp(begin, end, *begin); 33 } 34 } 35 36 37 template <class Iterator, class Object> 38 void DLLALGOLIB insertionSortHelp(const Iterator& begin, const Iterator& end, const Object& obj) 39 { 40 insertionSort(begin, end, std::less<Object>()); 41 } 42 43 44 template <class Iterator, class Comparator> 45 void DLLALGOLIB insertionSort(const Iterator& begin, const Iterator& end, Comparator lessThan) 46 { 47 if (begin != end) 48 { 49 insertionSort(begin, end, lessThan, *begin); 50 } 51 } 52 53 54 template <class Iterator, class Comparator, class Object> 55 void DLLALGOLIB insertionSort(const Iterator& begin, const Iterator& end, Comparator lessThan, const Object& obj) 56 { 57 for (Iterator idx = begin + 1; idx != end; ++idx) 58 { 59 Object tmp = *idx; 60 61 Iterator j = idx; 62 for (; j != begin && lessThan(tmp, *(j - 1)); --j) 63 { 64 *j = *(j - 1); 65 } 66 67 *j = tmp; 68 69 //PRINT_ELEMENTS(coll); 70 } 71 }

?

轉載于:https://www.cnblogs.com/noryes/p/5716689.html

總結

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

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