# Victory_Defeat 的博客

### 浅析sort

posted on 2019-08-28 12:52:58 | under 算法 |

# 0.前言

#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;
}

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

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

# 1.观察

 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编写者的码风

# 2.深入分析

## 2.1 __introsort_loop

 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
}
}

### 2.1.3 还是//3

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 __final_insertion_sort

### 2.2.2 分析

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);
}

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);
}
}
 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_insertion_sort__insertion_sort有何区别？又有什么用？

### 2.2.3 效率

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

（以上复杂度请自行证明）

# 3.其他

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

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

list呢？它的迭代器是双向迭代器，也不行