- 论坛徽章:
- 0
|
_Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions
这行的代码的意思不就是_Ideal=_Ideal*(3/4);么?
那么不就应该是允许division log(4/3)(N)次么? 为什么是1.5 log2(N) divisions
怎么看这两个数都不相等啊
完整代码:
template<class _RanIt,
class _Diff> inline
void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal)
{ // order [_First, _Last), using operator<
_Diff _Count;
for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
{ // divide and conquer by quicksort
_STD pair<_RanIt, _RanIt> _Mid =
_Unguarded_partition(_First, _Last);
_Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions
if (_Mid.first - _First < _Last - _Mid.second)
{ // loop on second half
_Sort(_First, _Mid.first, _Ideal);
_First = _Mid.second;
}
else
{ // loop on first half
_Sort(_Mid.second, _Last, _Ideal);
_Last = _Mid.first;
}
}
if (_ISORT_MAX < _Count)
{ // heap sort if too many divisions
_STD make_heap(_First, _Last);
_STD sort_heap(_First, _Last);
}
else if (1 < _Count)
_Insertion_sort(_First, _Last); // small
} |
|