注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

阿飘的博客

十里平湖霜满天 寸寸青丝愁华年

 
 
 

日志

 
 

IntroSort[SGI STL]  

2011-11-15 18:19:15|  分类: shell&c |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自ManJuSaka《IntroSort[SGI STL]》

IntroSort(自省的快排)

 

u  本质是什么?

n  SGI STLSORT实现:IntroSort

n  综合:快排,堆排,插入排序

n  分割层次不超出2*K

n  分割层次超出2*K后,则调用HEAPSORT

n  序列长度<16时退出分割循环,> 16则继续分割

n  当整个序列基本有序后,直接调用插入排序,完成最后的排序。

n   

 

u  原理

n  三点中值法。取中间大小的为PIVOT

n  分割函数,使用中间左右两部分:L< M < R, 返回M

n  左部分递归调用,右部分在循环中处理。

n  若分割层次大于2*K K <= lg2N,则调用heapsort,防止退化为N2..

n  若当前进入的子序列长度< 16,则退出。(宗旨是调用QUITSORT使之基本有序)

n  当整个序列基本有序后,直接调用简单插入排序。

n   

//**********************************************************//

//**************************************************//

template <class _RandomAccessIter>

inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {

  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);

  __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,

                 _LessThanComparable);

  if (__first != __last) {

    __introsort_loop(__first, __last,

                     __VALUE_TYPE(__first),

                     __lg(__last - __first) * 2);

    __final_insertion_sort(__first, __last);

  }

}

 

 

template <class _RandomAccessIter, class _Tp, class _Size>

void __introsort_loop(_RandomAccessIter __first,

                      _RandomAccessIter __last, _Tp*,

                      _Size __depth_limit)

{

  while (__last - __first > __stl_threshold) {

    if (__depth_limit == 0) {

      partial_sort(__first, __last, __last);

      return;

    }

    --__depth_limit;

    _RandomAccessIter __cut =

      __unguarded_partition(__first, __last,

                            _Tp(__median(*__first,

                                         *(__first + (__last - __first)/2),

                                         *(__last - 1))));

    __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);

    __last = __cut;

  }

}

 

 

template <class _Size>

inline _Size __lg(_Size __n) {

  _Size __k;

  for (__k = 0; __n != 1; __n >>= 1) ++__k;

  return __k;

}

template <class _Tp>

inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {

  __STL_REQUIRES(_Tp, _LessThanComparable);

  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;

}

 

 

template <class _RandomAccessIter>

inline void partial_sort(_RandomAccessIter __first,

                         _RandomAccessIter __middle,

                         _RandomAccessIter __last) {

  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);

  __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,

                 _LessThanComparable);

  __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first));

}

 

// partial_sort, partial_sort_copy, and auxiliary functions.

 

template <class _RandomAccessIter, class _Tp>

void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,

                    _RandomAccessIter __last, _Tp*) {

  make_heap(__first, __middle);

  for (_RandomAccessIter __i = __middle; __i < __last; ++__i)

    if (*__i < *__first)

      __pop_heap(__first, __middle, __i, _Tp(*__i),

                 __DISTANCE_TYPE(__first));

  sort_heap(__first, __middle);

}

 

 

template <class _RandomAccessIter>

void __final_insertion_sort(_RandomAccessIter __first,

                            _RandomAccessIter __last) {

  if (__last - __first > __stl_threshold) {

    __insertion_sort(__first, __first + __stl_threshold);

    __unguarded_insertion_sort(__first + __stl_threshold, __last);

  }

  else

    __insertion_sort(__first, __last);

}

 

template <class _RandomAccessIter, class _Compare>

void __insertion_sort(_RandomAccessIter __first,

                      _RandomAccessIter __last, _Compare __comp) {

  if (__first == __last) return;

  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)

    __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp);

}

 

template <class _RandomAccessIter, class _Tp, class _Compare>

void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,

                               _Compare __comp) {

  _RandomAccessIter __next = __last;

  --__next; 

  while (__comp(__val, *__next)) {

    *__last = *__next;

    __last = __next;

    --__next;

  }

  *__last = __val;

}

 

template <class _RandomAccessIter, class _Tp>

inline void __linear_insert(_RandomAccessIter __first,

                            _RandomAccessIter __last, _Tp*) {

  _Tp __val = *__last;

  if (__val < *__first) {

    copy_backward(__first, __last, __last + 1);

    *__first = __val;

  }

  else

    __unguarded_linear_insert(__last, __val);

}

 

 

 

  评论这张
 
阅读(408)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017