SGI STL关于sort的优化[1]

2013年7月8日 由 Creater 留言 »

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为后一个迭代器。

广告位

发表评论

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