本文共 3364 字，大约阅读时间需要 11 分钟。

1.插入排序

普通版本

#include 
   
    #include 
    
     #include 
     
      using namespace std;template 
      
       void insertionSort(vector
       
         &a){    int i;    for (int j = 1; j < a.size(); j++) {        T tmp = a[j];        for (i = j; i > 0 && tmp < a [i - 1]; i--)            a[i] = a[i - 1];        a[i] = tmp;    }}int main(){    vector
        
          test = { 190, 435, 834, 8954, 923, 56, 20 ,1, 934}; clock_t time_stt = clock(); insertionSort(test); cout << "Total time: " << 1000 * (clock() - time_stt) / (double)CLOCKS_PER_SEC << "ms" << endl; for (auto i : test) cout << i << " "; cout << endl; return 0;}
        
       
      
     
    
   

• 运行结果：

$ ./a.outTotal time: 0.002ms1 20 56 190 435 834 923 934 8954

STL实现版本(模仿STL sort() 接口)

#include 
   
    #include 
    
     #include 
     
      using namespace std;// 模仿STL sort()接口template 
      
       void insertionSort(const Iterator &begin, const Iterator &end, Functor func, const Object &obj){    Iterator i;    for (Iterator j = begin + 1; j != end; j++) {        Object tmp = *j;        for (i = j; i != begin && func(tmp, *(i - 1)); i--)            *i = *(i - 1);        *i = tmp;    }}template 
       
        void insertionSort(const Iterator &begin, const Iterator &end, Functor func){    insertionSort(begin, end, func, *begin);}template 
        
         void _insertionSort(const Iterator &begin, const Iterator &end, const Object &obj){ insertionSort(begin, end, less
         
        
       
      
     
    
   

• 运行结果：

$ ./a.outTotal time: 0.005ms1 20 56 190 435 834 923 934 8954

仿函数

此时引入了仿函数(也叫函数结构，functor)，可以对排序顺序进行自定义

比如可以利用lambda讲排序结果反过来：

#include 
   
    #include 
    
     #include 
     
      using namespace std;// 模仿STL sort()接口template 
      
       void insertionSort(const Iterator &begin, const Iterator &end, Functor func, const Object &obj){    Iterator i;    for (Iterator j = begin + 1; j != end; j++) {        Object tmp = *j;        for (i = j; i != begin && func(tmp, *(i - 1)); i--)            *i = *(i - 1);        *i = tmp;    }}template 
       
        void insertionSort(const Iterator &begin, const Iterator &end, Functor func){    insertionSort(begin, end, func, *begin);}template 
        
         void _insertionSort(const Iterator &begin, const Iterator &end, const Object &obj){ insertionSort(begin, end, less
         
        
       
      
     
    
   

• 运行结果：

$ ./a.outTotal time: 0.006ms8954 934 923 834 435 190 56 20 1

复杂度分析

最坏情况

时间复杂度：

最好情况

时间复杂度：

• 我的个人主页：
• 我的个人站点博客：
• 我的CSDN博客：
• 我的简书：
• 我的GitHub：

转载地址：http://enloi.baihongyu.com/