不小心一个问题引出了这么复杂事，今天我们把这个问题结束吧，现在我们来看看标准库的sort为什么会这么快：
———————————–
//如果不明白Mid3回头去看看我们的快排原理，这就是三数中值法找枢纽元素。这里有一点需要注意，_Ranlt表示随机迭代器，而迭代器就是指针的泛化，他是链接容器和算法的纽带，所以下面要是看到_Ranlt就直接把他当指针就好。_DEBUG_LT这个宏大家可能不明白，简单说这个宏的意义就是判断两个数大小，_DEBUG_LT（x,y) = x<y，这里有个东西叫等价，等讲STL的时候就明白了是怎么回事
template<class _RanIt>inline
void _Med3(_RanIt _First, _RanIt _Mid, _RanIt _Last)
{
if (_DEBUG_LT(*_Mid, *_First))
_STD iter_swap(_Mid, _First);
if (_DEBUG_LT(*_Last, *_Mid))
{
_STD iter_swap(_Last, _Mid);
if (_DEBUG_LT(*_Mid, *_First))
_STD iter_swap(_Mid, _First);
}
}
//将大数组划分成小数组，分别对每个小数组实施快排
template<class _RanIt>inline
void _Median(_RanIt _First, _RanIt _Mid, _RanIt _Last)
{
if (40 <_Last – _First)
{
size_t _Step = (_Last – _First + 1) / 8;
_Med3(_First, _First + _Step, _First + 2 * _Step);
_Med3(_Mid – _Step, _Mid, _Mid + _Step);
_Med3(_Last – 2 * _Step, _Last – _Step, _Last);
_Med3(_First + _Step, _Mid, _Last – _Step);
}
else
_Med3(_First, _Mid, _Last);
}
//_Unguarded_partition，这个函数是快排的重点，大家应该看到这个函数返回pair，pair也是STL里面的一部分，顾名思义，他就是表示一对的意思，所以里面自然储存两个数，在这里是两个指针，为了进一步排序。
template<class _RanIt>inline
pair<_RanIt, _RanIt>
_Unguarded_partition(_RanIt _First, _RanIt _Last)
{
_RanIt _Mid = _First + (_Last – _First) / 2;
_Median(_First, _Mid, _Last – 1);
_RanIt _Pfirst = _Mid;
_RanIt _Plast = _Pfirst + 1;
while (_First <_Pfirst&
&
!_DEBUG_LT(*(_Pfirst – 1), *_Pfirst)&
&
!(*_Pfirst <*(_Pfirst – 1)))
–_Pfirst;
while (_Plast <_Last
&
&
!_DEBUG_LT(*_Plast, *_Pfirst)
&
&
!(*_Pfirst <*_Plast))
++_Plast;
_RanIt _Gfirst = _Plast;
_RanIt _Glast = _Pfirst;
for (;
;
)
{
for (;
_Gfirst <_Last;
++_Gfirst)
if (_DEBUG_LT(*_Pfirst, *_Gfirst))
;
else if (*_Gfirst <*_Pfirst)
break;
else
_STD iter_swap(_Plast++, _Gfirst);
for (;
_First <_Glast;
–_Glast)
if (_DEBUG_LT(*(_Glast – 1), *_Pfirst))
;
else if (*_Pfirst <*(_Glast – 1))
break;
else
_STD iter_swap(–_Pfirst, _Glast – 1);
if (_Glast == _First &
&
_Gfirst == _Last)
return (pair<_RanIt, _RanIt>(_Pfirst, _Plast));
if (_Glast == _First)
{
if (_Plast != _Gfirst)
_STD iter_swap(_Pfirst, _Plast);
++_Plast;
_STD iter_swap(_Pfirst++, _Gfirst++);
}
else if (_Gfirst == _Last)
{
if (–_Glast != –_Pfirst)
_STD iter_swap(_Glast, _Pfirst);
_STD iter_swap(_Pfirst, –_Plast);
}
else
_STD iter_swap(_Gfirst++, –_Glast);
}
}
//前面的工作都准备好，最后就是排序，从下面的代码中，我们可以看出，标准库里的sort其实就是我们前两讲里面的算法的综合运用，当数据很大的时候我们使用快快，所以在一遍遍的划分后当每个片段的数据到达一定的数量的时候就开始使用堆排，又在数据小于一定数量的时候就用插排，再加上整个过程都使用迭代器（指针），所以这中间没有数据复制，自然也就没有调用operator=，所以效率就很高了。
template<class _RanIt,
class _Diff>inline
void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal)
{
_Diff _Count;
for (;
_ISORT_MAX <(_Count = _Last – _First) &
&
0 <_Ideal;
)
{
pair<_RanIt, _RanIt>_Mid =
_Unguarded_partition(_First, _Last);
_Ideal /= 2, _Ideal += _Ideal / 2;
if (_Mid.first – _First <_Last – _Mid.second)
{
_Sort(_First, _Mid.first, _Ideal);
_First = _Mid.second;
}
else
{
_Sort(_Mid.second, _Last, _Ideal);
_Last = _Mid.first;
}
}
if (_ISORT_MAX <_Count)
{
_STD make_heap(_First, _Last);
_STD sort_heap(_First, _Last);
}
else if (1 <_Count)
_Insertion_sort(_First, _Last);
// small
}
//主要的功能都是在_sort里面，这里其实只是提供一个借口而已
template<class _RanIt>inline
void sort(_RanIt _First, _RanIt _Last)
{
_DEBUG_RANGE(_First, _Last);
_Sort(_Unchecked(_First), _Unchecked(_Last), _Last – _First);
}
————————————–
看到标准库的实现后大家是不是明白为什么标准库的效率這么高了呢？因为我们的实现是通过容器来实现的，我们用了大量的复制，所以这中间浪费了太多的时间，而标准库里的却是通过指针来实现，所以他的效率才会这么高。
接下来我们继续类模板吧，为STL打给基础，如果不明白模板这东西，STL保证会看得云里雾里的。
=============
回复D直接查看目录
原文始发于微信公众号（
C/C++的编程教室
）：第四十八讲 排序算法（3）
|