STL源码剖析之排序(二)stable_sort

Datetime:2016-08-23 03:46:09          Topic: STL  Source Code Analysis           Share

stable_sort reference

一、stable_sort算法:

本质是归并排序,但归并排序合并时需要一个辅助的缓冲数组。当内存足够开缓冲区时,合并的时间复杂度为O(n),排序总的时间复杂度为O(nlogn);没有缓冲区时,合并的时间复杂度为O(nlogn),排序总的复杂度为O(nlog²n)。

不需要缓冲数组的合并算法:merge_sort(first, middle, last),其中[first,middle)有序,[middle,last)有序。

  • 判断[first, middle)与[middle, last)哪个区间更长,不妨设前半段区间更长
  • 取[first, middle)的中点 first_cut = first + (middle – first) / 2
  • 在后半段区间找到第一个大于(大于等于)first_cut值的位置 second_cut = std::lower_bound(middle, last, *first_cut)
  • 区间(first_cut, second_cut)向右旋转使middle成为第一个位置 std::rotate (first_cut, middle, second_cut)
  • 得到新的前后两个半区间的分界点 new_middle = first_cut + (second_cut – middle)
  • 递归[first, new_middle), [new_middle, last),重复上述步骤
  • 以上只是大致算法,还要注意边界细节问题

二、源码剖析

stable_sort:先申请一段缓冲区,如果没申请到就调用inplace_stable_sort,否则调用stable_sort_adaptive

stl stable_sort

/**
   *  @brief Sort the elements of a sequence, preserving the relative order
   *         of equivalent elements.
   *  @ingroup sorting_algorithms
   *  @param  first   An iterator.
   *  @param  last    Another iterator.
   *  @return  Nothing.
   *
   *  Sorts the elements in the range @p [first,last) in ascending order,
   *  such that @p *(i+1)<*i is false for each iterator @p i in the range
   *  @p [first,last-1).
   *
   *  The relative ordering of equivalent elements is preserved, so any two
   *  elements @p x and @p y in the range @p [first,last) such that
   *  @p x<y is false and @p y<x is false will have the same relative
   *  ordering after calling @p stable_sort().
  */
  template<typename _RandomAccessIterator>
    inline void
    stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	_DistanceType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
      __glibcxx_requires_valid_range(__first, __last);

      _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
								 __last);
      if (__buf.begin() == 0)
	std::__inplace_stable_sort(__first, __last);
      else
	std::__stable_sort_adaptive(__first, __last, __buf.begin(),
				    _DistanceType(__buf.size()));
    }

inplace_stable_sort:不需要缓冲区的归并排序,时间复杂度为O(nlog²n)。

当排序区间小于15时,直接采用插入排序,__insertion_sort在sort源码中有分析。

stl __inplace_stable_sort

/// This is a helper function for the stable sorting routines.
  template<typename _RandomAccessIterator>
    void
    __inplace_stable_sort(_RandomAccessIterator __first,
			  _RandomAccessIterator __last)
    {
      if (__last - __first < 15)
	{
	  std::__insertion_sort(__first, __last);
	  return;
	}
      _RandomAccessIterator __middle = __first + (__last - __first) / 2;
      std::__inplace_stable_sort(__first, __middle);
      std::__inplace_stable_sort(__middle, __last);
      std::__merge_without_buffer(__first, __middle, __last,
				  __middle - __first,
				  __last - __middle);
    }

merge_without_buffer采用上文中的算法进行合并,空间复杂度为O(1)

里面还用到了 std::rotate , std::advance , std::distance

/// This is a helper function for the merge routines.
  template<typename _BidirectionalIterator, typename _Distance>
    void
    __merge_without_buffer(_BidirectionalIterator __first,
			   _BidirectionalIterator __middle,
			   _BidirectionalIterator __last,
			   _Distance __len1, _Distance __len2)
    {
      if (__len1 == 0 || __len2 == 0)
	return;
      if (__len1 + __len2 == 2)
	{
	  if (*__middle < *__first)
	    std::iter_swap(__first, __middle);
	  return;
	}
      _BidirectionalIterator __first_cut = __first;
      _BidirectionalIterator __second_cut = __middle;
      _Distance __len11 = 0;
      _Distance __len22 = 0;
      if (__len1 > __len2)
	{
	  __len11 = __len1 / 2;
	  std::advance(__first_cut, __len11);
	  __second_cut = std::lower_bound(__middle, __last, *__first_cut);
	  __len22 = std::distance(__middle, __second_cut);
	}
      else
	{
	  __len22 = __len2 / 2;
	  std::advance(__second_cut, __len22);
	  __first_cut = std::upper_bound(__first, __middle, *__second_cut);
	  __len11 = std::distance(__first, __first_cut);
	}
      std::rotate(__first_cut, __middle, __second_cut);
      _BidirectionalIterator __new_middle = __first_cut;
      std::advance(__new_middle, std::distance(__middle, __second_cut));
      std::__merge_without_buffer(__first, __first_cut, __new_middle,
				  __len11, __len22);
      std::__merge_without_buffer(__new_middle, __second_cut, __last,
				  __len1 - __len11, __len2 - __len22);
    }

stable_sort_adaptive:缓冲区大小不够时,继续递归分治;否则直接调用merge_sort_with_buffer排序,最后调用merge_adaptive合并操作。

stl __stable_sort_adaptive

template<typename _RandomAccessIterator, typename _Pointer,
	   typename _Distance>
    void
    __stable_sort_adaptive(_RandomAccessIterator __first,
			   _RandomAccessIterator __last,
                           _Pointer __buffer, _Distance __buffer_size)
    {
      const _Distance __len = (__last - __first + 1) / 2;
      const _RandomAccessIterator __middle = __first + __len;
      if (__len > __buffer_size)
	{
	  std::__stable_sort_adaptive(__first, __middle,
				      __buffer, __buffer_size);
	  std::__stable_sort_adaptive(__middle, __last,
				      __buffer, __buffer_size);
	}
      else
	{
	  std::__merge_sort_with_buffer(__first, __middle, __buffer);
	  std::__merge_sort_with_buffer(__middle, __last, __buffer);
	}
      std::__merge_adaptive(__first, __middle, __last,
			    _Distance(__middle - __first),
			    _Distance(__last - __middle),
			    __buffer, __buffer_size);
    }

merge_sort_with_buffer:

用循环语句实现的归并排序。先调用chunk_insertion_sort对每个长度为_S_chunk_size=7的子区间进行插入排序,循环将[first, last) 合并后存到buffer,再将buffer排序后存回first。

mege_sort_loop: 对区间[first, last)的每个长度为step_size是子区间进行合并操作。

std::merge reference
template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
	   typename _Distance>
    void
    __merge_sort_loop(_RandomAccessIterator1 __first,
		      _RandomAccessIterator1 __last,
		      _RandomAccessIterator2 __result,
		      _Distance __step_size)
    {
      const _Distance __two_step = 2 * __step_size;

      while (__last - __first >= __two_step)
	{
	  __result = std::merge(__first, __first + __step_size,
					   __first + __step_size,
					   __first + __two_step,
					   __result);
	  __first += __two_step;
	}

      __step_size = std::min(_Distance(__last - __first), __step_size);
      std::merge(__first, __first + __step_size, 
			    __first + __step_size, __last,
			    __result);
    }

  template<typename _RandomAccessIterator, typename _Distance>
    void
    __chunk_insertion_sort(_RandomAccessIterator __first,
			   _RandomAccessIterator __last,
			   _Distance __chunk_size)
    {
      while (__last - __first >= __chunk_size)
	{
	  std::__insertion_sort(__first, __first + __chunk_size);
	  __first += __chunk_size;
	}
      std::__insertion_sort(__first, __last);
    }

  enum { _S_chunk_size = 7 };

  template<typename _RandomAccessIterator, typename _Pointer>
    void
    __merge_sort_with_buffer(_RandomAccessIterator __first,
			     _RandomAccessIterator __last,
                             _Pointer __buffer)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	_Distance;

      const _Distance __len = __last - __first;
      const _Pointer __buffer_last = __buffer + __len;

      _Distance __step_size = _S_chunk_size;
      std::__chunk_insertion_sort(__first, __last, __step_size);

      while (__step_size < __len)
	{
	  std::__merge_sort_loop(__first, __last, __buffer, __step_size);
	  __step_size *= 2;
	  std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
	  __step_size *= 2;
	}
    }

merge_adaptive:

缓冲区大小足够时,即只要满足较小半区间小于缓冲区大小,直接O(n)合并;否则,用类似上文中的算法,递归处理

stl merge_adaptive

/// This is a helper function for the merge routines.
  template<typename _BidirectionalIterator, typename _Distance,
	   typename _Pointer>
    void
    __merge_adaptive(_BidirectionalIterator __first,
                     _BidirectionalIterator __middle,
		     _BidirectionalIterator __last,
		     _Distance __len1, _Distance __len2,
		     _Pointer __buffer, _Distance __buffer_size)
    {
      if (__len1 <= __len2 && __len1 <= __buffer_size)
	{
	  _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
	  _GLIBCXX_STD_P::merge(__buffer, __buffer_end, __middle, __last, 
				__first);
	}
      else if (__len2 <= __buffer_size)
	{
	  _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
	  std::__merge_backward(__first, __middle, __buffer,
				__buffer_end, __last);
	}
      else
	{
	  _BidirectionalIterator __first_cut = __first;
	  _BidirectionalIterator __second_cut = __middle;
	  _Distance __len11 = 0;
	  _Distance __len22 = 0;
	  if (__len1 > __len2)
	    {
	      __len11 = __len1 / 2;
	      std::advance(__first_cut, __len11);
	      __second_cut = std::lower_bound(__middle, __last,
					      *__first_cut);
	      __len22 = std::distance(__middle, __second_cut);
	    }
	  else
	    {
	      __len22 = __len2 / 2;
	      std::advance(__second_cut, __len22);
	      __first_cut = std::upper_bound(__first, __middle,
					     *__second_cut);
	      __len11 = std::distance(__first, __first_cut);
	    }
	  _BidirectionalIterator __new_middle =
	    std::__rotate_adaptive(__first_cut, __middle, __second_cut,
				   __len1 - __len11, __len22, __buffer,
				   __buffer_size);
	  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
				__len22, __buffer, __buffer_size);
	  std::__merge_adaptive(__new_middle, __second_cut, __last,
				__len1 - __len11,
				__len2 - __len22, __buffer, __buffer_size);
	}
    }

两个辅助函数

__merge_backward与 std::merge 类似

__rotate_adaptive与 std::rotate 功能一样,只是用了缓冲区

/// This is a helper function for the merge routines.
  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
	   typename _BidirectionalIterator3>
    _BidirectionalIterator3
    __merge_backward(_BidirectionalIterator1 __first1,
		     _BidirectionalIterator1 __last1,
		     _BidirectionalIterator2 __first2,
		     _BidirectionalIterator2 __last2,
		     _BidirectionalIterator3 __result)
    {
      if (__first1 == __last1)
	return std::copy_backward(__first2, __last2, __result);
      if (__first2 == __last2)
	return std::copy_backward(__first1, __last1, __result);
      --__last1;
      --__last2;
      while (true)
	{
	  if (*__last2 < *__last1)
	    {
	      *--__result = *__last1;
	      if (__first1 == __last1)
		return std::copy_backward(__first2, ++__last2, __result);
	      --__last1;
	    }
	  else
	    {
	      *--__result = *__last2;
	      if (__first2 == __last2)
		return std::copy_backward(__first1, ++__last1, __result);
	      --__last2;
	    }
	}
    }

  /// This is a helper function for the merge routines.
  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
	   typename _Distance>
    _BidirectionalIterator1
    __rotate_adaptive(_BidirectionalIterator1 __first,
		      _BidirectionalIterator1 __middle,
		      _BidirectionalIterator1 __last,
		      _Distance __len1, _Distance __len2,
		      _BidirectionalIterator2 __buffer,
		      _Distance __buffer_size)
    {
      _BidirectionalIterator2 __buffer_end;
      if (__len1 > __len2 && __len2 <= __buffer_size)
	{
	  __buffer_end = std::copy(__middle, __last, __buffer);
	  std::copy_backward(__first, __middle, __last);
	  return std::copy(__buffer, __buffer_end, __first);
	}
      else if (__len1 <= __buffer_size)
	{
	  __buffer_end = std::copy(__first, __middle, __buffer);
	  std::copy(__middle, __last, __first);
	  return std::copy_backward(__buffer, __buffer_end, __last);
	}
      else
	{
	  std::rotate(__first, __middle, __last);
	  std::advance(__first, std::distance(__middle, __last));
	  return __first;
	}
    }




About List