文章

解析STL源码中的sort排序方法实现

本文介绍参考GCC实现的标准模板库，详细解析std::sort算法源码的实现思路，并以100M以上的测试数据对比其与纯快速排序的排序速度

发表于
作者 WhythZ
23 分钟阅读
解析STL源码中的sort排序方法实现

一、源码实现思路

  • 标准库中提供的排序算法std::sort的实现基于Introspective排序（IntroSort），其行为与三数取中值的快速排序（Median-of-three QuickSort）几乎完全相同，除了在阈值以下使用插入排序外，其每当Partition出现恶化倾向时，std::sort能侦测到并转而改用堆排序（HeapSort），这能使最坏时间复杂度由快速排序的最坏$O(n^2)$降低为堆排序的平均$O(n\ln n)$
    • 快速排序：时间复杂度平均$O(n\ln n)$，最坏$O(n^2)$，空间复杂度$O(\ln n)$与递归深度正相关
      • Partition：即例如每次调用快速排序都会将被排序数组分为两部分子数组，然后对子数组递归地调用快速排序
      • 恶化倾向：即例如快排的最坏情况为每次都划分出长度分别为$1$和n-1的两个子数组，这会导致快排函数调用的递归树高度达到最大，使得时间复杂度趋向$O(n^2)$
    • 插入排序：时间复杂度平均$O(n^2)$，空间复杂度$O(1)$
    • 堆排序：时间复杂度平均$O(n\ln n)$，无最坏情况，空间复杂度$O(1)$

  • 简而言之，算法std::sort在采取Median-of-Three基准选取策略的纯快速排序的基础上，在数组长度阈值$16$以下使用插入排序，在递归深度阈值超过$2\log_2n$时使用堆排序，目的是防止纯快速排序的最坏情况出现

  • 在阅读本文前，你至少需要理解快速排序的原理，关于上述提到的三种排序，你可以通过我的这三篇博客快速回顾其原理

二、std::__sort

  • 此处我们研究GCC的STL实现，以下是std::sort的原型模板函数std::__sort源代码，可见其执行分为两步
    • 第一步：std::__introsort_loop
    • 第二步：std::__final_insertion_sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// sort
template<typename _RandomAccessIterator, typename _Compare>
inline void __sort(
	_RandomAccessIterator __first,
	_RandomAccessIterator __last,
	_Compare __comp)
{
	//排除仅对一个数据排序的情况
	if (__first != __last)
	{
		//先调用Intro排序
		std::__introsort_loop(__first, __last,
			std::__lg(__last - __first) * 2, __comp);
		//最后调用一次插入排序
		std::__final_insertion_sort(__first, __last, __comp);
	}
}

三、std::__introsort_loop

3.1 Intro排序函数体

  • 函数__introsort_loop接收的参数列表意义如下
    • 前两个迭代器参数__first和__last确定被排序数组的始末
    • 第三个参数__depth_limit用于控制排序的最大递归层数
      • 此处的实现使用了最优情况下的递归树高度，乘以$2$作为限制Intro排序函数被递归调用的最大层数，以避免递归层数过深而排序效率下降
        • 若排序函数递归层数（即递归树的高度）过深，例如快速排序的最坏情况时递归树退化为链表，这会导致算法趋向最坏的$O(n^2)$时间复杂度
        • 理想的最优情况需要树高即递归层数最小，此时递归树是完全二叉树，近似看作完美二叉树，则易知树高与叶节点数$m$间的关系为$m=2^h\Rightarrow h=\log_2(m)$，此场景中叶节点数就等于被排序数组的长度
      • 在std::__sort的实现中调用本函数时传入的第三参数即为用函数__lg（即以$2$为底的对数函数）计算的$2h=2\log_2(m)$，例如长度为$1024$的数组代入得$2h=20$，即限制该数组进行Intro排序时最多只能递归$20$层
  • 该排序算法和传统的快速排序具有类似的框架
    • 若数组长度小于阈值S_threshold（该值等于$16$）则直接跳出while结束当前函数
    • 反之若大于阈值，则继续进行以下判断与执行
      • 若depth_limit等于$0$，则说明尽管通过Median-of-Three策略选择了较优的Pivot，但左右子数组仍不平衡，继而趋向于最坏复杂度$O(n^2)$，这意味着快排在当前被排序数组上不适用，于是转而使用堆排序__partial_sort
      • 反之若不等于$0$，则用__unguarded_partition_pivot进行基准选取与Partition，完成后继续依据Partition结果，对子数组递归调用__introsort_loop函数进行排序
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
28
29
30
31
32

/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void __introsort_loop(
	_RandomAccessIterator __first,
	_RandomAccessIterator __last,
	_Size __depth_limit,
	_Compare __comp)
{
	//被排序的数组长度阈值，小于等于该值则使用插入排序，大于则继续递归Intro排序
	while (__last - __first > int(_S_threshold))
	{
		//此处的递归层数由初始的2h不断递减而来，若等于0则调用堆排序
		if (__depth_limit == 0)
		{
			//堆排序
			std::__partial_sort(__first, __last, __last, __comp);
			return;
		}
		//递减递归层数
		--__depth_limit;
		//继续递归，首先需选取基准Pivot，即把三数的中位数存作__cut
		_RandomAccessIterator __cut =
			std::__unguarded_partition_pivot(__first, __last, __comp);
		//对__cut到__last内的序列递归调用Intro排序
		std::__introsort_loop(__cut, __last, __depth_limit, __comp);
		//将中位数放在末尾
		__last = __cut;
	}
	//若被排序数组小于等于阈值，则当前__introsort_loop结束
	//直到所有被递归调用的__introsort_loop都触碰到阈值，则回到std::__sort中
	//然后统一执行一次插入排序std::__final_insertion_sort
}

3.2 不恶化则递归Intro排序

  • 在递归调用std::__introsort_loop前需先调用__unguarded_partition_pivot函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14

/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
inline _RandomAccessIterator __unguarded_partition_pivot(
	_RandomAccessIterator __first,
	_RandomAccessIterator __last,
	_Compare __comp)
{
	//选取位于__first和__last中间的元素
	_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);
}
  • 此处使用Median-of-Three基准选取策略，由函数std::__move_median_to_first实现，其中函数对象__comp用于定义迭代器对象在逻辑上谁大谁小（最终要求排序结果是升序）
    • 若__comp(__a, __b)返回 true，则表示__a应排在__b前，即$a<b$
    • 若__comp(__a, __b)返回 false，则表示__a不应在__b前，即$a\geq b$
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
28
29
30
31
32

/// Swaps the median value of *__a, *__b and *__c under __comp to *__result
template<typename _Iterator, typename _Compare>
void __move_median_to_first(
	_Iterator __result,
	_Iterator __a,
	_Iterator __b,
	_Iterator __c,
	_Compare __comp)
{
	//若__a<__b
	if (__comp(__a, __b))
	{
		//若__a<__b，且__b<__c，则__b为基准
		if (__comp(__b, __c))
			std::iter_swap(__result, __b);
		//否则__a<__b，且__b>=__c，且__a<__c，则__c为基准
		else if (__comp(__a, __c))
			std::iter_swap(__result, __c);
		//否则__a<__b，且__b>=__c，且__a>=__c，则__a为基准
		else
			std::iter_swap(__result, __a);
	}
	//否则__a>=__b，且__a<__c，则__a为基准
	else if (__comp(__a, __c))
		std::iter_swap(__result, __a);
	//否则__a>=__b，且__a>=__c，且__b<__c，则__c为基准
	else if (__comp(__b, __c))
		std::iter_swap(__result, __c);
	//否则__a>=__b，且__a>=__c，且__b>=__c，则__b为基准
	else
		std::iter_swap(__result, __b);
}
  • Partition由std::__unguarded_partition实现
    • __first 和 __last 指针分别从数组的两端向中间移动
    • 当__first找到一个大于等于基准元素的元素，且__last找到一个小于等于基准元素的元素时，若不满足终止条件则交换这两个元素，以使得比基准小的在左侧，大的在右侧
    • 交换后让__first和__last 指针分别向右和向左移动一位，继续下一轮分区的过程，循环往复到__first >= __last 时则分区完成，返回__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
25
26
27
28
29
30
31
32
33
34
35
36
37

/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
_RandomAccessIterator __unguarded_partition(
	_RandomAccessIterator __first,
	_RandomAccessIterator __last,
	_RandomAccessIterator __pivot,
	_Compare __comp)
{
	while (true)
	{
		//将__first向后推移到恰好指向>=基准的元素的位置，即指向第一个>=基准的元素
		while (__comp(__first, __pivot))
			++__first;

		//第一次执行时，尾后迭代器__last指向待处理范围末尾的下一个位置，而不是最后一个元素本身
		//因此__last初始时并不指向一个有效的元素，需要将其前移指向实际的末尾元素
		//第二次以上执行时，__last所指向的元素已经满足while判断条件，故需向前推一位以继续
		--__last;

		//将__last向前推移至恰好<=基准的元素的位置，即指向第一个<=基准的元素
		while (__comp(__pivot, __last))
			--__last;

		//此时__first左侧全是<基准的元素，而__last后全是>基准的元素

		//若此时_first >= __last，则说明分区完成，返回__first给最外层的__cut
		//__cut作为Partition边界，将原数组分割成左侧小于基准、右侧大于基准的两部分
		if (!(__first < __last))
			return __first;

		//否则_first < __last，说明
		//此处交换的是元素，而非迭代器，迭代器仍指向原位，即__first所指元素仍在__last左侧
		std::iter_swap(__first, __last);
		//将元素交换后，__first和__last所指位置的元素已经满足while内的循环条件，故需要分别向右和向左移动一位以继续下一轮的执行，直到最终满足终止条件
		++__first;
	}
}

3.3 左半循环而右半递归

  • 当std::__unguarded_partition函数返回__cut到外部后
    • 对右半部分递归调用Intro排序
    • 对左半部分序列则不直接调用，而是将其留给下一轮的while循环进行排序，以减少因递归产生的开销，《STL源码剖析》中写道：该写法可读性差但效率并不比两次递归更好
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

/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
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;
		
		//分区的边界即__cut
		_RandomAccessIterator __cut =
			std::__unguarded_partition_pivot(__first, __last, __comp);
		//对__cut到__last的部分即数组的右半分区递归调用Intro排序
		std::__introsort_loop(__cut, __last, __depth_limit, __comp);
		//对于从__first到__cut的左半部分，留给下一个while循环处理，而不直接递归
		__last = __cut;
	}
}

3.4 恶化则转而调用堆排序

  • 当检测到递归层数超出限制时调用的堆排序std::__partial_sort源码如下，解析略
1
2
3
4
5
6
7
8
9
10

template<typename _RandomAccessIterator, typename _Compare>
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);
}

四、std::__final_insertion_sort

  • 当所有的__introsort_loop函数都递归调用到触碰了阈值后，每个__introsort_loop函数本身不会立刻执行插入排序，而是直接结束调用，直到所有递归树中的叶节点Intro函数都触碰阈值返回，程序会回到std::__sort内执行下一行的std::__final_insertion_sort，这会对整个数组做一次插入排序
  • 此时整个数组呈现整体有序但局部乱序的状态，故即使插入排序复杂度为$O(n^2)$，但实际上对该序列进行排序并不费时
    • 局部乱序：由于每最多$16$个元素在先前触碰阈值后并未调用插入排序，故为乱序
    • 整体有序：即从左到右的每$16$个（也可能小于$16$）子序列为一组，每组取任意一个元素作为代表，这些代表的值必然是单调的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
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);
}
  • 至于此处的插入排序的实现细节，参考这篇文章

五、排序速度对比

  • 我们使用下面的Python脚本生成100M左右大小的随机数数据用于测试
1
2
3
4
5
6
7

import random

#生成100M数据
dataSize = 100000000
with open("data.txt", "w") as f:
    for _ in range(dataSize):
        f.write(f"{random.randint(1, 1000000)}\n")
  • 进行对比的是我在此处实现的快速排序，测试代码如下
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <fstream>

//从传入的三个索引中确定基准元素，并将三个元素重新置位，将基准放入第三个索引位置，最小值第一个位置，最大值第二个位置
template <typename T>
void SetPivotFromThree(std::vector<T>& _list, size_t _1Idx, size_t _2Idx, size_t _3Idx)
{
    //确保索引顺序
    if (!(_1Idx <= _2Idx && _2Idx <= _3Idx))
        throw std::runtime_error("ERROR: Incorrect order of indices when calling \"SetPivotFromThree\"");

    //确保将最小值放在第一个索引的位置
    if (_list[_2Idx] < _list[_1Idx])
        std::swap(_list[_2Idx], _list[_1Idx]);
    if (_list[_3Idx] < _list[_1Idx])
        std::swap(_list[_3Idx], _list[_1Idx]);

    //然后将剩下的两个元素比较大小，确保中位数在第三个索引位置，最大值在第二个索引位置
    if (_list[_2Idx] < _list[_3Idx])
        std::swap(_list[_2Idx], _list[_3Idx]);
}

//我的快速排序实现
template <typename T>
void MyQuickSort(std::vector<T>& _list, size_t _begin, size_t _end)
{
    //计算传入部分列表的长度
    size_t _length = _end - _begin + 1;
    if (_length <= 1)
        return;
    //因为我们需要至少三个元素才能使用后面的方法进行排序，所以要单独处理两元素情况
    if (_length == 2)
    {
        if (_list[_begin] > _list[_end])
            std::swap(_list[_begin], _list[_end]);
        return;
    }
    // //可以在长度低于某阈值时使用低空间复杂度排序，如插入排序
    // if (_length <= N) { return; }
    
    //计算列表中点位置元素的索引，此变量仅在确定基准时使用一次，不影响后续实际排序时的逻辑
    size_t _mid = (_begin + _end) / 2;
    //将三者中的最小值放入列表_begin索引处，最大值放入_mid，中位数即基准元素放入_end
    SetPivotFromThree(_list, _begin, _mid, _end);
    
    //用两个索引箭头分别从第二个元素和倒数第二个元素位置开始向中间遍历
    size_t _lower = _begin + 1;
    size_t _upper = _end - 1;
    bool _flagL = false;
    bool _flagU = false;
    
    //左箭头碰到比基准大的元素，就可以暂停外部循环而进入内部循环移动右箭头寻找比基准小的元素
    while (true)
    {
        //总数为奇数个时，结束循环的条件为两索引箭头重合，偶数时则为二者大小关系颠倒
        if (_lower >= _upper)
        {
            //将基准元素放到_lower的位置
            //因为_upper递减途中可能会遇到比基准小的元素，而_lower只会停在比基准大的元素处，所以将其换到列表末尾即基准右侧是一定没问题的
            std::swap(_list[_lower], _list[_end]);
            break;
        }

        //将箭头移到两个需要被互换的位置
        if (!_flagL)
        {
            if (_list[_lower] > _list[_end])
                _flagL = true;
            else
                _lower++;
        }
        if (!_flagU)
        {
            if (_list[_upper] < _list[_end])
                _flagU = true;
            else
                _upper--;
        }

        //两个标识都为true时应当进行互换，并为下一轮循环做准备
        if (_flagL && _flagU)
        {
            std::swap(_list[_lower], _list[_upper]);

            _flagL = false;
            _flagU = false;
            _lower++;
            _upper--;
        }
    }

    //此时基准元素位于_lower索引处，对其左右两侧元素递归进行快速排序即可
    MyQuickSort(_list, _begin, _lower - 1);
    MyQuickSort(_list, _lower + 1, _end);
}

int main()
{
    std::vector<int> data;
    std::ifstream file("data.txt");
    if (!file)
    {
        std::cerr << "Failed to open file!\n";
        return 1;
    }

    int num;
    while (file >> num)
        data.push_back(num);

    //测试我的快速排序
    auto start = std::chrono::high_resolution_clock::now();
    MyQuickSort(data, 0, data.size() - 1);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    std::cout << "MyQuickSort time: " << elapsed.count() << " seconds\n";

    //测试std::sort
    start = std::chrono::high_resolution_clock::now();
    std::sort(data.begin(), data.end());
    end = std::chrono::high_resolution_clock::now();
    elapsed = end - start;
    std::cout << "std::sort time: " << elapsed.count() << " seconds\n";
}
  • 将生成好的数据data.txt和上述测试脚本test.cpp放在同一目录下，在cmd中运行以下指令开始测试
1
2

g++ test.cpp
a.exe
  • 我们得到的测试结果如下，可见STL的std::sort运行效率是我写的纯快速排序的接近两倍
1
2

MyQuickSort time: 20.7668 seconds
std::sort time: 10.1644 seconds
编程相关, 高级语言
C++ STL
本文由作者按照 CC BY-NC-SA 4.0 进行授权