【C++語言實作通用插入排序算法】

插入排序算法的C++通用版本，支援任何以疊代器（或普通數組首、尾指針）傳入的數組的就地排序。

myutil.h

<code>#pragma once #ifndef _MY_UTIL_H #define _MY_UTIL_H #include&lt;iterator&gt;  //iterator_traits //template function to display arrays with new line printed when finish. template&lt;class Iterator&gt; void displayArr(const Iterator &amp;beg, const Iterator &amp;end){   typedef typename std::iterator_traits&lt;Iterator&gt;::value_type Ty;   std::copy(beg, end, std::ostream_iterator&lt;Ty&gt;(std::cout, " "));   std::cout&lt;&lt;std::endl; } #endif</code>

insertion_sort.h

<code>#pragma once #ifndef _INSERT_SORT_H #define _INSERT_SORT_H #include&lt;iterator&gt;  //iterator_traits template&lt;class Iterator, class cmp&gt; void insertSort(const Iterator &amp;beg, const Iterator &amp;end){   typedef typename std::iterator_traits&lt;Iterator&gt;::value_type val_t;   Iterator step = beg;   Iterator insertPos;   Iterator beforeInsertPos;   for(++step; step != end; ++step){     val_t key = *step;     insertPos = step;     beforeInsertPos = insertPos;     for(--beforeInsertPos; cmp()(*beforeInsertPos, key); --beforeInsertPos){       *insertPos-- = *beforeInsertPos;       if(beforeInsertPos == beg)         break;     }//end of for     *insertPos = key;   }// end of for }// end of insertion sort #endif</code>

main.cpp

<code>#include&lt;iostream&gt; #include&lt;string&gt; #include&lt;vector&gt; #include&lt;list&gt; #include"myutil.h"  //displayArr #include"insertion_sort.h"  //insertSort using std::cout; using std::endl; using std::vector; using std::string; using std::list; int main(int argc, char **argv) {   int intArr[ ] = { 231, -547, -54, 54, 0, -1, 45, -54, 123, 9, -54 };   int *intArrEnd = intArr + sizeof(intArr) / sizeof(*intArr);   double doubleArr[ ] = { 0.0, -28.7, 465.2 };   double *doubleArrEnd = doubleArr + sizeof(doubleArr) / sizeof(*doubleArr);   string strArr[] = {"月夜幻影", "bill", "billhoo", "Alex", "alex", "Petter"};   string *strArrEnd = strArr + sizeof(strArr) / sizeof(*strArr);   vector&lt;string&gt; strVec(strArr, strArrEnd);   list&lt;string&gt; strList(strArr, strArrEnd);   cout&lt;&lt;"before insertion sort..."&lt;&lt;endl;   displayArr&lt;int*&gt;(intArr, intArrEnd);   displayArr&lt;double*&gt;(doubleArr, doubleArrEnd);   displayArr&lt;string*&gt;(strArr, strArrEnd);   displayArr(strVec.begin(), strVec.end());   displayArr(strList.begin(), strList.end());   //do insertion sort in ascending order   insertSort&lt;int*, std::greater&lt;int&gt;&gt;(intArr, intArrEnd);   insertSort&lt;double*, std::greater&lt;double&gt;&gt;(doubleArr, doubleArrEnd);   insertSort&lt;string*, std::greater&lt;string&gt;&gt;(strArr, strArrEnd);   insertSort&lt;vector&lt;string&gt;::iterator, std::greater&lt;string&gt;&gt;(strVec.begin(), strVec.end());   insertSort&lt;list&lt;string&gt;::iterator, std::greater&lt;string&gt;&gt;(strList.begin(), strList.end());   cout&lt;&lt;"\nascending order:"&lt;&lt;endl;   displayArr&lt;int*&gt;(intArr, intArrEnd);   displayArr&lt;double*&gt;(doubleArr, doubleArrEnd);   displayArr&lt;string*&gt;(strArr, strArrEnd);   displayArr(strVec.begin(), strVec.end());   displayArr(strList.begin(), strList.end());   //do insertion sort in descending order   insertSort&lt;int*, std::less&lt;int&gt;&gt;(intArr, intArrEnd);   insertSort&lt;double*, std::less&lt;double&gt;&gt;(doubleArr, doubleArrEnd);   insertSort&lt;string*, std::less&lt;string&gt;&gt;(strArr, strArrEnd);   insertSort&lt;vector&lt;string&gt;::iterator, std::less&lt;string&gt;&gt;(strVec.begin(), strVec.end());   insertSort&lt;list&lt;string&gt;::iterator, std::less&lt;string&gt;&gt;(strList.begin(), strList.end());   cout&lt;&lt;"\ndescending order:"&lt;&lt;endl;   displayArr&lt;int*&gt;(intArr, intArrEnd);   displayArr&lt;double*&gt;(doubleArr, doubleArrEnd);   displayArr&lt;string*&gt;(strArr, strArrEnd);   displayArr(strVec.begin(), strVec.end());   displayArr(strList.begin(), strList.end());   return EXIT_SUCCESS; }</code>

     本文轉自Bill_Hoo 51CTO部落格，原文連結：http://blog.51cto.com/billhoo/793581，如需轉載請自行聯系原作者