SGI STL中的sort源码

[TOC]

# 实现原理
STL中的sort不是普通的快排，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序；而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。

# 内省式排序 `Introsort`
不当的基准选择会导致不当的分割，会使快速排序恶化为 O(n^2)。David R.Musser于1996年提出一种混合式排序算法：Introspective Sorting（内省式排序），简称IntroSort，其行为大部分与上面所说的median-of-three Quick Sort完全相同，但是当分割行为有恶化为二次方的倾向时，能够自我侦测，转而改用堆排序，使效率维持在堆排序的 O(nlgn)，又比一开始就使用堆排序来得好。

# 代码
```
template<typename RandomAccessIterator, typename Compate>
inline void sort(RandomAccessIterator first, RandomAccessIterator last, Compate comp)
{
	if (first != last)
	{
		__introsort_loop(first, last, __lg(last - first) * 2,comp);
		__final_insertion_sort(first, last,comp);
	}

}
```
std::__introsort_loop 便是上面介绍的内省式排序，其第三个参数中所调用的函数 __lg() 便是用来控制分割恶化情况，具体功能类似求lg(n)（取下整），意味着快速排序的递归调用最多 2*lg(n) 层。

## 内省式 __introsort_loop
```
template<typename _RandomAccessIterator,typename _Size, typename _Compare>
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
{
	while (__last - __first > __stl_threshold)
	{
		if (__depth_limit == 0)
		{
			std::partial_sort(__first, __last, __last,__comp);//分割恶化，使用heap sort
			return;
		}
		--__depth_limit;
		//选择一个枢纽决定分割点，并且将分割点落到__cut身上。
		_RandomAccessIterator __cut = __unguarded_partition(
			__first, 
			__last,
			__median(*__first, *(__first + (__last - __first)/2), *(__last-1),__comp),
			__comp);

//对右半部分进行递归sort
		__introsort_loop(__cut, __last, __depth_limit, __comp);
		__last = __cut;
		//现在回到while，准备对左半部分递归sort

}
}
```
- 首先判断元素规模是否大于阀值_S_threshold，_S_threshold是一个常整形的全局变量，值为16，表示若元素规模小于等于16，则结束内省式排序算法，返回sort函数，改用插入排序 __final_insertion_sort。
- 若元素规模大于_S_threshold，则判断递归调用深度是否超过限制。若已经到达最大限制层次的递归调用，则改用堆排序。代码中的 __partial_sort 即用堆排序实现。
- 若没有超过递归调用深度，则调用函数 __unguarded_partition_pivot 对当前元素做一趟快速排序，并返回基准位置。
- 快排之后，再递归对右半部分调用内省式排序算法。然后回到while循环，对左半部分进行排序。源码写法和我们一般的写法不同，但原理是一样的，这是很明显的尾递归优化，需要注意。

## 快速排序（分区）

```
const int __stl_threshold = 16;
template<typename _RandomAccessIterator, typename _T, typename _Compare>
_RandomAccessIterator __unguarded_partition(
	_RandomAccessIterator __first, _RandomAccessIterator __last,
	_T __pivot, _Compare __comp)
{
	while (true)
	{
		--__last;
		while (__comp(*__first, __pivot) && __first<__last) ++__first;
		while (__comp(__pivot, *__last) && __first<__last) --__last;
		if (!(__first < __last)) return __first;
		std::iter_swap(__first, __last);
		++__first;
	}
}

//求lg(N),控制分割恶化的情况
template<typename Size>
Size __lg(Size n)
{
	Size k;
	for (k = 0; n > 1; n >>= 1) k++;
	return k;
}
```

## 三点中值
```
//三值中值
template<typename T,typename Compare>
T __median(T& a, T& b, T& c, Compare comp)
{
	if (comp(a, b))
		if (comp(b, c))
			return b;
		else if (comp(a, c))
			return c;
		else
			return a;
	else if (comp(a, c))
		return a;
	else if (comp(b, c))
		return c;
	else
		return b;
}

//template<typename _RandomAccessIterator,typename _Compare>
//inline void __pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_RandomAccessIterator __result,)
//template<typename _RandomAccessIterator,typename _Compare>
//void __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator, _Compare __comp)
//{
//	std::make_heap(__first, __middle);
//	for (_RandomAccessIterator i = middle; i < __last; ++i)
//	{
//		if (*i < *first)
//		{
//			__pop_heap(__first, __middle,__comp);
//		}
//		std::sort_heap(__first, __middle,__comp);
//	}
//}

```
## 插入排序（__final_insertion_sort）
```

template<typename _RandomAccessIterator, typename T,typename _Compare>
inline void __unguarded_linear_insert(_RandomAccessIterator __last, T __value,_Compare __comp)
{
	_RandomAccessIterator next = __last;
	--next;
	//一旦不再出现逆转对，停止循环
	while (__comp(__value, *next))
	{
		*__last = *next;
		__last = next;
		--next;
	}
	*__last = __value;
}

template<typename _RandomAccessIterator, typename _Compare>
inline void __linear_insert(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
	typename std::iterator_traits<_RandomAccessIterator>::value_type value = *__last;
	if (__comp(value, *__first)) //比头还要小
	{
		std::copy_backward(__first, __last, __last + 1);
		*__first = value;
	}
	else
		__unguarded_linear_insert(__last, value,__comp);
}

template<typename _RandomAccessIterator, typename _Compare>
inline void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
	if (__first == __last) return;
	for (_RandomAccessIterator i = __first + 1; i != __last; ++i)
	{
		__linear_insert(__first, i, __comp);
		//[first,i)已排序的区间。
	}
}

template<typename _RandomAccessIterator, typename _Compare>
inline void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
	for (_RandomAccessIterator i = __first; i != __last; ++i)
	{
		__unguarded_linear_insert(i, *i, __comp);
	}
}

template<typename _RandomAccessIterator,typename _Compare>
inline void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare comp)
{
	if (__last - __first > __stl_threshold)
	{
		__insertion_sort(__first,__first+__stl_threshold, comp);
		__unguarded_insertion_sort(__first + __stl_threshold, __last, comp);
	}
	else
		__insertion_sort(__first, __last, comp);
}

```
# 测试例子
```
void testIterSort()
{
	std::function<void(int&)> print = [](int &x) { std::cout << x << " "; };
	std::function<bool(int&, int&)> comp = [](const int& x, const int& y) {return x < y; };
	int *a = SortTestHelper::generateRandomArray(10, 0, 10);
	std::vector<int> v(a,a+ 10);
	//for_each(v.begin(), v.end(), print);
	iter_sort::sort(v.begin(), v.end(), comp);
	std::cout << "\n";
	//iter_sort::__unguarded_partition_pivot(v.begin(), v.end(),comp);
	//std::nth_element(v.begin(), v.begin() + 5, v.end(),std::greater<int>()); //不做全排序
	for_each(v.begin(), v.end(), print);
	std::cout << "\n";
}
```
# 参考RW_STL sort算法
```
namespace rw_sort {
	template<typename RandomAccessIterator, typename Compate>
	inline void __quick_sort_loop(RandomAccessIterator first, RandomAccessIterator last, Compate comp)
	{
		while (last - first > __stl_threshold)
		{
			//midian
			RandomAccessIterator cut = ::__unguarded_partition(
				first
				, last
				, sgi_sort::__median(*first, *(first + (last - first) / 2), *(last - 1),comp)
				, comp);
			if (cut - first >= last - cut)
			{
				__quick_sort_loop(cut, last,comp);
				last = cut;
			}
			else
			{
				__quick_sort_loop(first, cut,comp);
				first = cut;
			}
		}
	}

template<typename RandomAccessIterator, typename Compate >
	inline void sort(RandomAccessIterator first, RandomAccessIterator last, Compate comp)
	{
		if (first != last)
		{
			__quick_sort_loop(first,last,comp);
			sgi_sort::__final_insertion_sort(first, last, comp);
		}
	}

template<typename RandomAccessIterator>
	inline void sort(RandomAccessIterator first, RandomAccessIterator last)
	{
		if (first != last)
		{
			__quick_sort_loop(first, last, _comp);
			//sgi_sort::__final_insertion_sort(first, last, _comp);
		}
	}
}
```

本算法不包含sgi sort中的内省排序算法。

参考[STL::sort函数实现](https://www.cnblogs.com/AlvinZH/p/8682992.html)

Simon 's Blog

导航

OHH,最近发表

这里随便填填,没事