丁丁的博客
0%

sort函数源码浅析

Posted on Edited on In Views: Valine:

基本用法

首先肯定是用法,由于在排序过程中涉及到元素交换等操作，所以sort函数仅支持可随机访问的容器，如数组， string、vector、deque等。函数原型如下

1
2
template<typename _RandomAccessIterator> void sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
template<typename _RandomAccessIterator, typename _Compare> void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

不传入第三个参数的话，默认是升序排列，直接传入两个迭代器即可。
降序需要传入比较函数。

1
sort(arr.begin(), arr.end(), greater<type>())

传入函数、仿函数、lambda都可实现，若函数返回true，则表示a与b应该交换顺序；若返回false, 则a与b保持原有顺序。

1
2
3
4
5
bool cmp(T a, T b);
sort(arr.begin(), arr.end(), cmp);
sort(arr.begin(), arr.end(), [&](T a, T b){
    return a < b;
});

结构体排序时，需事先自定义比较函数或重载比较运算符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Student {
    int id, x, y;
    bool operator < (Student &a) const {
        return id > a.id;
    }
};
sort(s, s + 10);
struct Student {
    int id, x, y;
};
bool cmp(Student a, Student b) {
    return a.id > b.id;
}
sort(s, s + 10, cmp);

源码分析

sort是三种排序的组合使用，快排，插排，堆排，根据数据量自动调整，当数据量较大时采用快排分段递归，分段后数据量小于某个阈值时，会改用插入排序，如果递归层数过深有出现最坏情况的倾向还会改用堆排。
首先sort会进行一些合法性检查，之后调用_sort方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename _RandomAccessIterator, typename _Compare>
  _GLIBCXX20_CONSTEXPR
  inline void
  sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
   _RandomAccessIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
   typename iterator_traits<_RandomAccessIterator>::value_type,
   typename iterator_traits<_RandomAccessIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);
    __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

    std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
  }

_sort的函数模板如下，首先两个迭代器，first != last情况下执行，_introsort_loop是内省排序的实现，_final_insertion_sort是插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 template<typename _RandomAccessIterator, typename _Compare>
   _GLIBCXX20_CONSTEXPR
   inline void
   __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
   _Compare __comp)
   {
     if (__first != __last)
{
  std::__introsort_loop(__first, __last,
			std::__lg(__last - __first) * 2,
			__comp);
  std::__final_insertion_sort(__first, __last, __comp);
}
   }

其中内省排序的算法便是sort的核心，他可以根据递归的深度决定是快排还是堆排来实现，能够保证最坏的时间复杂度也是O(NlogN)，同时在序列几乎有序时也会直接使用插入排序。
首先，快排在大多数情况下是效率最佳，快排和堆排的渐进时间复杂度相当，而快排基于的是分而治之的思想，父问题分开的子问题本质上是不重叠的，减少了大量的无效比较。
但其实快排的效率很大程度上取决于pivot元素的选取，最好的情况下，pivot每次都能将数据等分成两半，这样递归的深度就是logN，时间复杂度为O(NlogN),但在特殊情况下比如说每次选的pivot都分在数组最端点，这样递归的树变成了完全向一侧倾斜，递归深度N - 1，这种情况下复杂度O(N^2)。
当快排进入这种情况时，应切换到堆排序，堆排虽然可能不如快排效率高在任何情况下都是O(NlogN)，当快排递归的开销过大时，使用堆排是比较好的方案。
观察如下introsort的函数模板，首先可以看到一个_S_threshold的宏，判断的是范围大小，当范围小于16时则可认定这个序列基本有序，退出使用插排。而再往下是_depth_limit其实就是递归次数的限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
   _GLIBCXX20_CONSTEXPR
   void
   __introsort_loop(_RandomAccessIterator __first,
	     _RandomAccessIterator __last,
	     _Size __depth_limit, _Compare __comp)
   {
     while (__last - __first > int(_S_threshold))
{
  if (__depth_limit == 0)
    {
      std::__partial_sort(__first, __last, __last, __comp);
      return;
    }
  --__depth_limit;
  _RandomAccessIterator __cut =
    std::__unguarded_partition_pivot(__first, __last, __comp);
  std::__introsort_loop(__cut, __last, __depth_limit, __comp);
  __last = __cut;
}
   }

 /**
  *  @doctodo
  *  This controls some aspect of the sort routines.
 */
 enum { _S_threshold = 16 };

当快速排序遇到最坏情况时，意味着在递归时会连续多次选中带分割区间的最值元素，从而导致多次无效分割，进而导致递归层数快速增加。在introsort的设计中一旦递归深度超出一个阈值，则认为快速排序掉入陷阱并切换到堆排序算法。快速排序在理想状态下应当递归约logn次。因此，如果递归深度明显大于logn，说明快速排序就掉进陷阱了。
回看_sort模板在调用introsort时，传进的参数是std::__lg(__last - __first) * 2，其实就是2 * logn，这是应当终止递归的阈值设置。

1
2
3
std::__introsort_loop(__first, __last,
				std::__lg(__last - __first) * 2,
				__comp);

同时，通过上文代码可以看到depth_limit每次调用会自减一次，到零的话则调用partial_sort，进入到建堆和堆排的过程中了。

1
2
3
4
5
6
7
8
9
10
11
template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    __partial_sort(_RandomAccessIterator __first,
		   _RandomAccessIterator __middle,
		   _RandomAccessIterator __last,
		   _Compare __comp)
    {
      std::__heap_select(__first, __middle, __last, __comp);
      std::__sort_heap(__first, __middle, __comp);
    }

unguarded_partition_pivot则是pivot元素的选取，返回一个迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
            _RandomAccessIterator __last, _Compare __comp)
{
    _RandomAccessIterator __mid = __first + (__last - __first) / 2;
    std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
                __comp);
    return std::__unguarded_partition(__first + 1, __last, __first, __comp);
}

为了高效，首先进入右递归，然后last = pivot进行左递归，当while的判断条件失效时，会避免更多的递归。

1
2
3
4
_RandomAccessIterator __cut =
	    std::__unguarded_partition_pivot(__first, __last, __comp);
	  std::__introsort_loop(__cut, __last, __depth_limit, __comp);
	  __last = __cut;

再细看unguarded_partition_pivot的实现，可以学习一下STL选取分割位置的方法。

1
2
3
4
5
6
7
8
9
10
11
12
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
            _RandomAccessIterator __last, _Compare __comp)
{
    _RandomAccessIterator __mid = __first + (__last - __first) / 2;
    std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
                __comp);
    return std::__unguarded_partition(__first + 1, __last, __first, __comp);
}

__move_median_to_first是找出__a、__b、__c的中值，并将这个中值放在__result位置处。因此，根据传入参数，就是找出__first+1、__mid、__last-1三个位置的中值，并将中值和__first位置的值进行交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/// Swaps the median value of *__a, *__b and *__c under __comp to *__result
 template<typename _Iterator, typename _Compare>
   _GLIBCXX20_CONSTEXPR
   void
   __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
		   _Iterator __c, _Compare __comp)
   {
     if (__comp(__a, __b))
{
  if (__comp(__b, __c))
    std::iter_swap(__result, __b);
  else if (__comp(__a, __c))
    std::iter_swap(__result, __c);
  else
    std::iter_swap(__result, __a);
}
     else if (__comp(__a, __c))
std::iter_swap(__result, __a);
     else if (__comp(__b, __c))
std::iter_swap(__result, __c);
     else
std::iter_swap(__result, __b);
   }

找到pivot之后__unguarded_partition(__first + 1, __last, __first, __comp)进行分割。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 template<typename _RandomAccessIterator, typename _Compare>
   _GLIBCXX20_CONSTEXPR
   _RandomAccessIterator
   __unguarded_partition(_RandomAccessIterator __first,
		  _RandomAccessIterator __last,
		  _RandomAccessIterator __pivot, _Compare __comp)
   {
     while (true)
{
  while (__comp(__first, __pivot))
    ++__first;
  --__last;
  while (__comp(__pivot, __last))
    --__last;
  if (!(__first < __last))
    return __first;
  std::iter_swap(__first, __last);
  ++__first;
}
   }

上述函数调用结束后，在序列大小小于一定数字时，就跳出introsort的过程了，进入插入排序的过程。插排在已经部分有序的序列中非常快，接近O(n)的复杂度，而堆排或快排如果按照各自的算法，没有利用已经部分有序的前提，所以就不如插排。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 template<typename _RandomAccessIterator, typename _Compare>
   _GLIBCXX20_CONSTEXPR
   void
   __final_insertion_sort(_RandomAccessIterator __first,
		   _RandomAccessIterator __last, _Compare __comp)
   {
     if (__last - __first > int(_S_threshold))
{
  std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
				  __comp);
}
     else
std::__insertion_sort(__first, __last, __comp);
   }

函数模板内有一个 if 分支。当区间长度较小时，直接调用__insertion_sort；当区间长度较大时，对前__stl_threshold 个元素调用 __insertion_sort，而对前 __stl_threshold 个元素之后的元素调用__unguarded_insertion_sort。
借由此种实现方式，其效率比标准的插入排序效率要高。基于函数调用的条件，__unguarded_insertion_sort无需检测数据越界，在一定程度上对性能有所优化。

参考书籍

《STL源码剖析》https://book.douban.com/subject/1110934/