• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    5年前 (2013-07-08)  C++ |   3 条评论  17 
    文章评分 0 次,平均分 0.0

    STL里的sort算法,并不是一成不变的使用快排(qsort),而是综合各方面因素来优化得到的一种综合算法。

    1.当数据量较大时(STL中定为16),使用快排(Quick Sort)进行区间递归排序;
    2.当数据量较大,而且递归层次较深(__lg() *2),则采用堆排序(Heap Sort),因为区间太小的递归的栈消耗与参数入栈出栈效率并没有那么的理想;
    3.当数据量较小时,则直接使用插入排序(Insert Sort).
    以默认的重载了operator<的类对象为例,当然使用函数对象来作为排序规则的原理一样。

    先看插入排序:

    template <class RandomAccessIterator>
    void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
      if (first == last) return; 
      for (RandomAccessIterator i = first + 1; i != last; ++i)
        __linear_insert(first, i, value_type(first));
    }
    

    其中的

    for (RandomAccessIterator i = first + 1; i != last; ++i)

    作为外层循环来决定__linear_insert的处理区间,区间为[first,i)。

    再来看看__linear_insert

    template <class RandomAccessIterator, class T>
    inline void __linear_insert(RandomAccessIterator first, 
                                RandomAccessIterator last, T*) {
      T value = *last;
      if (value < *first) {
        copy_backward(first, last, last + 1);
        *first = value;
      }
      else
        __unguarded_linear_insert(last, value);
    }

    注意这里的区间并不是半开半闭,而是[first, last],而且[first, last)已经是有序,观测值为value=*last.
    既然[first, last)已经是有序,如果value小于*first,则使用copy_backward将[first,last)整体右移。
    否则使用__unguarded_linear_insert来找到合适的位置插入,顾名思义,为线性查找插入。

    template <class RandomAccessIterator, class T>
    void __unguarded_linear_insert(RandomAccessIterator last, T value) {
      RandomAccessIterator next = last;
      --next;
      while (value < *next) {
        *last = *next;
        last = next;
        --next;
      }
      *last = value;
    }

    很简单,就是倒序线性找位置。其中next为前一个迭代器,last为后一个迭代器。

     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/1662.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享