之前以为sort的实现就是随机化快排,看来我还是太naive了

sort 用了 Introspective Sort(内省排序):

  • 数据量大时,采用Quick Sort(快速排序),分段递归
  • 一旦分段后的数据量小于某个阈值,采用Insertion Sort(插入排序)
  • 若递归层数过深,则采用Heap Sort(堆排序)

insert_sort

插入排序
复杂度O(n^2) 但在这里的期望复杂度为 O(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
const int threshold = 16;   //阈值

template<class Iterator,class T>
inline void unguarded_linear_insert(Iterator last,T val)
{
Iterator next = last;
--next;
while (val < *next)
{
*last = *next;
last = next;
--next;
}
*last = val;
}

template<class Iterator,class T>
inline void linear_insert(Iterator first,Iterator last)
{
T val = *last;
if(val < *first)
{
while(last != first) *(last--) = *last
*first = val;
}
else
unguarded_linear_insert(last,val);
}

template<class Iterator>
void insert_sort(Iterator first,Iterator last)
{
for(Iterator it = first+1; it != last; ++it)
linear_insert(first,i);
}

template<class Iterator>
void unguarded_insert_sort(Iterator first,Iterator last)
{
for(Iterator it = first; it != last; ++it)
unguarded_linear_insrt(it,*it);
}

template<class Iterator>
void final_insertion_sort(Iterator first,Iterator last)
{
if(last - first > threshold)
{
insert_sort(first,first+thershold);
unguarded_insert_sort(first+thershold,last);
}
else
insert_sort(first,last);
}

quick_sort

快速排序,平均复杂度 O(nlog(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
//三点分值,返回序列的 首,中,尾三个元素的中值作为轴
template<class T>
inline const T _median(const T& l,const T& m,const T& r)
{
if(l < m)
if(m < r)
return m;
else if(l < r)
return r;
else
return l;
else
if(l < r)
return l;
else if(m < r)
return r;
else
return m;
}

template<class Iterator,class T>
Iterator partition(Iterator first,Iterator last,T pivot)
{
for(;;)
{
while(*first < pivot) ++first;

--last;
while(pivot < *last) --last;

if(!(first < last)) return first;

swap(first,last);
++first;
}
}

heap_sort

堆排序
自己的写法,没有按写
复杂度O(nlog(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
template<class Iterator>
inline void shift_down(Iterator first,Iterartor last)
{
int root = 0,son;
for(;;)
{
son = 2*root + 1;
if(first+son >= last) reutrn;
if((first+son+1 < last) && *(first+son) < *(first+son+1)) ++son;
if(*(first+root) < *(first+son))
swap(first+root,first+son);
else
return;
}
}

template<class Iterator>
inline void make_heap(Iterator first,Iterartor last)
{
for(Iterator it=first + (last - first - 2)/2;it >= first;--it)
shift_down(it,last);
}

template<class Iterator>
inline void sort_heap(Iterator first,Iterartor last)
{
for(Iterator it=last-1;it > first;--it)
{
if(*first == *it) break;
swap(first,it);
shift_down(first,it+1);
}
}

template<class Iterator>
inline void heap_sort(Iterator first,Iterartor last)
{
make_heap(first,last);
sort_heap(first,last);
}

intro_sort

内省排序,上述排序的综合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int threshold = 16;   //阈值

template<class Iterator,class Size>
void intro_sort(Iterator first,Iterator last,Size dep_limit)
{
while(last - first > threshold)
{
if(dep_limit == 0) //递归层数超出限制
{
heap_sort(first,last);
return ;
}
--dep_limit;
Iterator cut = partition(first,last,
_median(*first,*(first+(last-first)/2),*(last-1)));

introsort_loop(cut,last,dep_limit);
//introsort_loop(first,cut,dep_limit);
last = cut; //这是模板库的实现
}
}

sort

sort的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class Size>
inline Size _lg(Size n) // log2(n)
{
Size i;
for(i=0;n>1;n>>=1) ++i;
return i;
}

template<class Iterator>
inline void sort(Iterator first,Iterator last)
{
if(first != last)
{
intro_sort(first,last,,_lg(last - first)*2);
final_insertion_sort(first,last);
}
}

C++11之后,所有情况下sort的复杂度为O(nlog(n))