浅析sort

前言

相信每个入门的同学都见过这样一个题目:

给定一些整数,将它们从小到大排序后输出

同学们常常会写这样的代码:

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int n,a[1000010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<n;++i)printf("%d ",a[i]);
printf("%d\n",a[n]);
return 0;
}

这里的sort就是我们今天的主角

别看它语句短小,但却无比精悍

$upd:2019.8.28 19:22$ 更新$2.1$部分,增添了”还是//3”一项

$upd:2019.10.17 22:13$ 想卡掉sort的是魔鬼吧(然而还是可以的,尽管并不会卡),那个说是补充的并看不懂感觉这篇文章好理解一些吧,背景的话看这里($Link$)(我战兔最帅了)还有能不能不要老是复读我的话啊?虽然人类的本质是复读机

观察

首先,观察sort的来源(我这里使用了VSCode的速览定义功能)

观察到它包含在stl_algo.h文件中(这一文件包含在algorithm头文件中)

找到其定义为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename _RandomAccessIterator>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;

// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
//start
if (__first != __last)
{
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2);
std::__final_insertion_sort(__first, __last);
}
//end
}//这里吐槽一下C++ STL编写者的码风

看到变量是_RandomAccessIterator(即随机迭代器)

这是个什么东西鸭?其实就是数组、vectordeque这类东西的实现方法

接下来观察到其主体代码是从//start//end的部分,前面可以不管

深入分析

__introsort_loop

这是个什么玩意?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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))//5
{
if (__depth_limit == 0)
{
_GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);//4
return;
}
//1
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition_pivot(__first, __last, __comp);//3
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
//2
}
}

如上是其源码,发现它是一个递归结构

//1到//2

不难看出//1//2之间正是快速排序实现

然而……貌似它只处理了右区间部分?左区间怎么办呢?

别急,我们来重新浏览一下:

它在排完序之后把cut的值付给了last

然后由于它是循环,所以……下一次就是处理左区间了

所以它相比于我们所写的排序优点正是此处

巧妙地将递归换成了循环,虽然复杂度不变,但常数就是大幅提升了

这似乎从一方面解释了sort比手写排序快的原因(借用一个图):

//3

不过这并不能让快排避免退化的危机,只能解决常数问题

然而sort似乎基本没有退化过,这是为什么呢?

首先注意//3处(pivot就是常说的哨兵)

这里的哨兵并没有使用startlast,中部中的任何一个

通过持续跟踪,发现哨兵使用的是三者的中值

这就从一定程度上优化了算法

还是//3

老样子,直接上这一部分的源码:

1
2
3
4
5
6
7
8
9
template<typename _RandomAccessIterator, typename _Compare>
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
_RandomAccessIterator __mid = __first + (__last - __first) / 2;
std::__move_median_first(__first, __mid, (__last - 1), __comp);
return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
}

__move_median_first是用来将三者从小到大排序

__unguarded_partition而不断去交换位置错误的元素,直到first和last指针无有效区域为止

它并不会去做任何一次比较运算(这一点在下文$2.2.2$中也有提及)

那么,为什么能不比较呢?

它由于$2.1.2$的保证(即使用三者的中值),可以得出一定会在超出有效区域之前中止

也就是说,它可以保证不需要比较,可以自动操作,不必考虑越界问题

不比较,又可以进行一定的常数优化

减少常数、运算次数,就是STL编写者的唯一目的 (所以连码风都不管了)

这一算法被称之为分割算法(即原版本说的没看懂的部分,也是对$2.1.2$的一些补充)

//4

这个partial_sort是什么?为什么要用它?

通过调查源码,发现这个partial_sort就是堆排:

那么depth_limit是什么?有何作用?

回到sort本体,发现depth_limit即$\log_2(last-first)$(亦即$\log_2n$)

如果递归次数到达$\log_2n$会怎么样?

退化,在退化之际使用堆排来弥补,可以基本解决退化

这也正是sort不退化的奥秘所在

__final_insertion_sort

这……终极插入排序?(雾)

前面不是排好了么?要它何用?

等等,回到$2.1$的//5处,这个_S_threshold是?

查阅定义得,_S_threshold为$16$,一个常数?

所以说……快排剩了最前面$16$个不排,交给插入排序?

理论上就算退化复杂度也才相当于插入排序啊,为什么呢?

这时就需要复习一下插排的概念了

插排复习

插排原理:每一个元素通过比较,找到应插入位置

其特点:最好情况(基本有序)复杂度$O(n)$

这样就可以理解了,快排保证了前$16$个元素基本有序,但非完全有序

所以,这样只要$O(n)$就可以排好最左边$16$个

分析

以为这就结束了?想的太简单了

观察__final_insertion_sort源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
}

可以看到,又调用了两个插入排序,它们分别的代码:

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>
void
__insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
if (__first == __last) return;

for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
if (__comp(*__i, *__first))
{
typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);
}
else
std::__unguarded_linear_insert(__i, __comp);
}
}
1
2
3
4
5
6
7
8
9
10
11
template<typename _RandomAccessIterator, typename _Compare>
inline void
__unguarded_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;

for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i, __comp);
}

此时此刻,您的内心一定是崩溃的

这里就不贴__unguarded_linear_insert的代码了,只需要知道其作用

其作用是找到应插入的位置并插入(无底洞啊,不建议自己查看)

而如果,当前值要插在前头,直接让其他的后移

理论上和普通插排毫无区别实际也是,但是略微对常数有所优化

__unguarded_insertion_sort__insertion_sort有何区别?又有什么用?

貌似是省去了if的判断句?

仅此而已?!

对,仅此而已。

但是为什么可以去掉呢?

因为这一排序是建立在最左边永远是最小值的基础上的

不仅是__unguarded_insertion_sort__unguarded_partition,事实上,所有的以__unguarded开头的函数

都不会考虑越界!

而众所周知,比较函数是很耗时的,因此常数会有较大提升

效率

我们从各种操作入手分析

首先,经典插排,$2N$次比较,$3N$次赋值,$N$次减法,$N$次自减。

其次,__insertion_sort

分两种情况:

每次第一分支,即if语句执行情况,$N+1$次比较,$N+1$次赋值,$3N$次自减/加(注意:此处$+1$这类常数不可忽略)

每次第二分支,即else语句执行情况,$N+1$次比较,$2N$次赋值,$N$次自减

那么假设二者出现概率相同,则平均为$N+1$次比较,$1.5N+0.5$次赋值,$2N$次自减

可以看到,少了$N-1$次比较,$1.5N-0.5$次赋值,$N$次减法,多了$N$次自减

而且,已知比较时间开销很大,赋值小一些,而减法、自减基本不耗时

__unguarded_insertion_sort则是$N$次比较,$2N$次赋值和$N$次自减(与每次第二分支时间复杂度基本相同)

不过,在$N$很大时,$+1$的常数也会很大,这也是一直没有省略的原因

(以上复杂度请自行证明)

您:……看个文章还要自证???

其他

既然__unguarded_insertion_sort的时间要小得多,那么为什么不直接用呢?

不知道读者有没有注意到2.2.2最后有一行加粗的字体

这一行字解释了为什么不能直接用__unguarded_insertion_sort排序

等等,如何保证在__insertion_sort后,全局最小值在左边呢?

先回到__introsort_loop,它在什么情况下会返回呢?

一是区域小于等于16(即_S_threshold),二是超过depth_limit,也就是$\log_2n$

而由快排定义可知,左边区间的所有数据一定比右边小(也可参考图):

所以,如果是第一种情况,就可以得出最小值在左边

如果是第二种情况,那么最左边的区间会调用堆排序,所以这段区间的最小值一定位于最左端。再加上左边区间所有的数据一定比右边小,那么最左边的数据一定是全局最小值

其他

至此,我们完成了对sort的初步探究(仅是初步)

那么,是不是所有容器都能使用sort呢?

并不是,主要有vectorlist、数组可以使用

unordered_开头的容器只有前向迭代器,然而在1中已经说过,只有随机迭代器才能使用sort

而,mapsetpriority_queue这类自带排序的当然是用不了了

queuestack这类则因为它们对出口和入口做了限制,无法排序

list呢?它的迭代器是双向迭代器,也不行

不过不必担心,众所周知,list自带list::sort,虽然不能用std,但可以自己使用

万万没想到啊,一个小小的sort居然有这么多优化

不得不说,C++ STL编写者真的把编译器的效率压榨了不少,真是视效率如生命啊!

试问:有多少人能够自己写出像STL这样好的库?

这正是C++优点所在(并未引战)

什么?平板电视?反正平板电视也没sort

这倒是让我想起一个东西:平方根倒数速算法

下一个迫害来源,万♂恶♂之♂源

0%