SGI STL关于sort的优化[2]

2013年7月8日 由 Creater 留言 »

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内部总体来说就是插入排序了,代码很简单,可以找来看看。

广告位

发表评论

你必须 登陆 方可发表评论.