C++STL sort排序内部机制--Apple的学习笔记

STL sort实现原理：

STL中的sort并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。

既然选择用c++11做vslam了，STL是必须学习的。本着不重复造轮子，站在巨人的肩膀上的原则。当然还是要理解下STL中的机制，并且自己体验一把，才能确认STL库确实是好用的，而不是别人说好用就是好用~

c++ code

    #include <chrono>
    #include <iostream>
    #include <unistd.h>
    #include <thread>
    #include <vector>
    #include <algorithm>
    using namespace std;
    /*
    ratio<3600, 1>           hours
    ratio<60, 1>             minutes
    ratio<1, 1>              seconds
    ratio<1, 1000>           milliseconds
    ratio<1, 1000000>        microseconds
    ratio<1, 1000000000>     nanosecons
    */
    #define LEN 10000
    
    int main()
    {
        int n=0;
        int min=0;
        vector<int> v1;
        for( int i = 0; i != LEN; ++i )
        {
            v1.push_back(rand()%10);
        }
        //copy(v1.begin(), v1.end(), v2.begin()); 
        vector<int> v2(v1.begin(), v1.end());   //创建一个copy副本,使用冒泡排序
        auto beginTime = chrono::high_resolution_clock::now();
        sort( v1.begin(), v1.end()); //从小到大排序，使用STL排序
        auto endTime = chrono::high_resolution_clock::now();
        auto elapsedTime= chrono::duration_cast<chrono::milliseconds>(endTime - beginTime);
        cout << "v1:Algorithm elapsed time is " << elapsedTime.count() << " milliseconds" << endl;
    
        beginTime = chrono::high_resolution_clock::now();
        for(int i = 0; i < LEN; i++ )
        {
          min = v2[i];
          for(int j = i; j < LEN; j++ )
          {
            if(v2[j]<min)
            {
              min= v2[j];
              v2[j]=v2[i];
              v2[i]=min;
            }
          }
        }
    
        endTime = chrono::high_resolution_clock::now();
        elapsedTime= chrono::duration_cast<chrono::milliseconds>(endTime - beginTime);
        cout << "v2:Algorithm elapsed time is " << elapsedTime.count() << " milliseconds" << endl;
        // For debug
        // for( int i = 0; i != LEN; ++i )
        // {
        //     cout<<v1[i]<<v2[i]<<endl;
        // }
    
        cin.get();
        return 0;
    }

输出结果：

D:\ws\alg_compare\build>main.exe
v1:Algorithm elapsed time is 2 milliseconds
v2:Algorithm elapsed time is 185 milliseconds