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

    1中说了插入排序实现方法与思想,插入排序可能算是所有排序算法中思想最简单的一种了。

    接下来关注下快排,因为这是在数据量较大时采用的排序方法。
    通常的快排算法是将一个大区间分成两个区间,左边区间的数都小于关键字key,右边区间的数都大于关键字key。
    再分别对左边和右边区间递归执行上过程,知道每个区间只有一个元素,排序完毕。
    但是区间较小时,也进行如此递归是得不偿失,所以STL中的sort里的快排是当区间的长度小于等于16时结束Quick Sort.

    另外在快排时,需要找一个关键字key作为观测值,这个值的决定也影响分区,因为普通的分区存在以下的情况:可能存在一个区为空白,也即是没有值大于该值,或者没有值小于该值。为了弥补这个缺陷,STL采用的是median-of-three partitioning.

    template <class T>
    inline const T& __median(const T& a, const T& b, const T& c) {
      if (a < b)
        if (b < c)
          return b;
        else if (a < c)
          return c;
        else
          return a;
      else if (a < c)
        return a;
      else if (b < c)
        return c;
      else
        return b;
    }

    即是找3个数中的中位数。

    区间分割时,还是老套路,first向尾部移动,last向头部移动,直到first越过last时停止。

    template <class RandomAccessIterator, class T>
    RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
                                               RandomAccessIterator last,
                                               T pivot) {
      while (true) {
        while (*first < pivot) ++first;
        --last;
        while (pivot < *last) --last;
        if (!(first < last)) return first;
        iter_swap(first, last);
        ++first;
      }
    } 

    该函数返回分区后右边区间的头迭代器。
    来看看sort的核心部分

    template <class RandomAccessIterator, class T, class Size>
    void __introsort_loop(RandomAccessIterator first,
                          RandomAccessIterator last, T*,
                          Size depth_limit) {
      while (last - first > __stl_threshold) {
        if (depth_limit == 0) {
          partial_sort(first, last, last);
          return;
        }
        --depth_limit;
        RandomAccessIterator cut = __unguarded_partition
          (first, last, T(__median(*first, *(first + (last - first)/2),
                                   *(last - 1))));
        __introsort_loop(cut, last, value_type(first), depth_limit);
        last = cut;
      }
    } 

    上边采用last =cut来控制左右递归。当区间长度<=16时快排结束,进入插入排序。下面的代码就可以看出。

    template <class RandomAccessIterator>
    inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
      if (first != last) {
        __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
        __final_insertion_sort(first, last);
      }
    }    

    __final_insertion_sort内部总体来说就是插入排序了,代码很简单,可以找来看看。

     

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

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享