1、概述

排序算法是算法中的重点，排序过的数据，特别容易查找，不管是实际工作还是面试都会用到它。

现实生活中，字典需要排序，书籍索引需要排序，磁盘目录需要排序，名片需要排序等等。任何数据只要你想快速查找，就需要进行排序。

排序算法有很多种，比如冒泡排序、选择排序、插入排序、快速排序、堆排序。其中堆排序我们在整理 heap 时已经进行整理了，今天主要是对 STL 中的 sort 排序进行整理。而 sort 排序又会用到快速排序等其它一些排序算法，这里就按个，由简到难的进行介绍。

2、partial_sort/partial_sort_copy

partial_sort 局部排序，这个算法接受一个 middle 迭代器（位于序列 [first, last) 之内 ），然后重新安排 [first, last)，使序列中 （middle-first）个最小元素以递增顺序排序，置于[first, middle）。其余元素放置在 [middle, last) 中，不保证有任何特定顺序。

partial_sort 的任务是找出 (middle-first) 个最小元素，我们可以把 (middle-first） 组织成一个 max-heap，然后将 [middle, last) 中的每一个元素拿来与 max-heap 的最大值比较，如果小于该最大值，就互换位置并重新保持 max-heap 的状态。这样走到最后，[first, middle) 中的元素肯定就是最小的 (middle-first) 个元素，这时候用 sort_heap() 将 [first, middle) 做一次排序，就得到最后的结果。代码如下：

template<class RandomAccessIterator>
inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,  RandomAccessIterator last)
{
	__partial_sort( first, middle, last, value_type(first));
}

template<class RandomAccessIterator, class T>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last,   T*)
{
	make_heap(first, middle);
	//以下的 i < last 判断操作，只适用于 random iterator
	for( RandomAccessIterator i = middle; i < last; ++i)
	{
		if( *i < *first)
			__pop_heap(first, middle, i, T(*i), distance_type(first));
	}
	
	sort_heap(first,middle);    	
}

其中用到的 make_heap、sort_heap、__pop_heap 在整理 heap 时整理过了，大家可以去看看。

partial_sort_copy 和 partial_sort 的行为完全相同，只不过前者不改变原有数据的结构，把排序后的结构置于另一块空间中。这个其实就是从大数据中查找前100大或者小的数据，也叫 Top N 问题。

3、Insertion Sort（插入排序）

插入排序以双层循环的形式进行。外循环遍历整个序列，每次迭代决定出一个子区间；内循环是对这个子区间进行操作，子区间默认是排好序的，新插入的元素与最后的元素进行比较，如果大于就进行交换，然后再向前去比较，如果大于就进行交换，直到小于或等于，序列排序完毕。

插入排序的复杂度为 O(N²)，但当数据量很少时，有着不错的效果。STL 并不开放 insertion sort，所以函数名称都加上双下划线。代码如下：

template<class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
	if( first == last ) 
		return;
		
	for(RandomAccessIterator i = first + 1; i != last; ++i)	//外循环
		__linear_insert( first, i, value_type(first)); 		//形成的子区间
}


template<class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first, RandomAccessIterator last, T*)
{
	T value = *last;
	if( value < *first)	//因为这个区间已经排好序，如果小于最小值，那么直接放最前面，之前的都往后移动一位
	{
		copy_backward(first, last, last+1); 		//整个区间向右移动一个位置
		*first = value;
	}
	else
		__unguarded_linear_insert( last, value);	//内循环
}

template<class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value)
{
	RandomAccessIterator next = last;
	--next;
	//内循环的逻辑，直到满足条件
	while( value < *next )
	{
		*last = *next ;	//两者进行交换
		last = next;	//调整迭代器
		--next;
	}
	
	*last = value;
}

上述函数之所以命名为 unguarded_x 是因为，value 必然不小于子区间内的最小元素（前面已经判断了），所以不需要进行是否超出边界的判断，所以称为 unguarded_。

稍后介绍的函数，有 unguarded_ 为前缀的，同样是因为在特定条件下，边界条件的检验可以省略。

4、Quick Sort（快速排序）

在大量数据的情况下，插入排序效率就有点慢了。而 Quick Sort 是目前已知最快的排序算法，平均复杂度为O（N logN），最坏的情况下将达到 O(N²)。

快速排序的主要思想是：取序列中的任一元素当做基准点 V（也叫枢轴），将序列分割为 L，R 两段，使 L 内的每一个元素都小于或等于 V，R内的每一个元素都大于或等于 V。然后对L,R递归执行快速排序。

快速排序的精神在于将大区间分割为小区间，分段排序。每一个小区间排序完成后，串接起来的大区间也就完成了排序。最坏的情况发生在分割时产生了一个空的子区间，那完全没有达到预期的效果。为了避免这种情况 STL 采用 median-of-three（三点中值）的做法，即取整个序列的首、尾、中央三个地方的元素，以这三者中的中间值作为基准点。为了快速去除中央位置的元素，显然迭代器必须能够随机定位，即RandomAccessIterator。

template <class T>
inline const T& __median(const T& a, const T& b, const T& c)
{
	if( a < b )
	{
		if( b < c ) 		//a<b<c
			return b;
		else if( a < c)		// a < b, b >= c, a<c
			return c;
		else
			return a;
	}
	else if( a < c)			// c > a >= b
		return a;
	else if( b < c)			// a >= b, a >= c, b < c
		return c;
	else
		return b;
}

分割 L 和 R 子区间的方法不只一种，这里先叙述一个简单又有狼嚎成效的做法。令头端迭代器 first 向尾部移动，尾端迭代器 last 向头部移动。当 *first 大于或等于基准点时就停下来，当 *last 小于或等于基准点时也停下来，然后检验两个迭代器是否交错。如果 first 仍然在左而 last 仍然在右，就将两者元素互换，然后各自调整一个位置（向中央逼近），在继续进行相同的行为。如果发现两个迭代器交错了（!(first < last)）,表示整个序列已经调整完毕，以此时的 first 为轴，将序列分为左右两半。代码如下：

template<class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first, RandomAccessIterator last, T pivot)
{
	while( true)
	{
		while( *first < pivot )		// first 找到 >= pivot 的元素就停下来
			++first;

		--last;						//调整迭代器
		while( *last > pivot)		// last 找到 <= pivot 的元素就停下来
			--last;

		if( !(first < last))		//如果交错，结束循环
			return first;
		
		iter_swap(first, last);		//大小值交换
		++first;					//调整迭代器
	}
}

还有一种是：假设基准点的迭代器为 base，先令头端迭代器 first 向尾部移动，当 *first 大于或等于基准点时就停下来，用基准点的数据跟 *first的数据进行交换，令base = first。然后令尾端迭代器 last 向头部移动，当 *last 小于或等于基准点时停下来，用基准点的数据跟 *last 的数据进行交换，令base = last。重复上面的动作，直到 first == last。此时 base = first = last，base元素所在的位置就是它应该在的位置，以后就不必排序了，base就是 L 的尾端，base+1 就是 R 的头端。代码如下：

template<class RandomAccessIterator>
RandomAccessIterator __unguarded_partition2(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator base)
{
	while( true)
	{
		while( *first < *base )		// first 找到 >= pivot 的元素就停下来
			++first;

		iter_swap(first, base);		// *first 与 基准点的值进行交换
		base= first;				//调整 base 迭代器
		
		--last;						//调整 last 迭代器
		while( *last > *base)		// last 找到 <= pivot 的元素就停下来
			--last;

    	if(  first == last )		//如果相等，结束循环
			return base;			
    	
    	iter_swap(last, base);		// *last 与 基准点的值进行交换
		base = last; 				//调整 base 迭代器
	}
}

按照上面两种方式的分割，quick_sort 也可以写为两种方式：

//对应上面第一种分割
template<class RandomAccessIterator>
inline void quick_sort( RandomAccessIterator first,  RandomAccessIterator last)
{
	while( last - first > 1 )
	{
		//对当前序列进行快速排序
		RandomAccessIterator cur = __unguarded_partition(first, last, T(__median(*first, *(first+(last-first)/2),*(last-1))));
		//对右子区间进行排序
		quick_sort(cur, last);
		//对左子区间进行排序
		last = cur;
	}
}

//对应上面第二种分割
template<class RandomAccessIterator>
inline void quick_sort2( RandomAccessIterator first,  RandomAccessIterator last)
{
	while( last - first > 1 )
	{
		//对当前序列进行快速排序
		RandomAccessIterator cur = __unguarded_partition2(first, last, T(__median(*first, *(first+(last-first)/2),*(last-1))));
		//对右子区间进行排序
		quick_sort2(cur+1, last);
		//对左子区间进行排序
		last = cur；
	}
}

5、SGI STL sort

sort 使用的是综合 quick sort 及其它排序算法的优点的一个算法。当面对一个只有十来个元素的小型序列，如果使用像Quick Sort 这样复杂而需要大量运算的排序法，会产生许多的函数递归调用，这样效率反而会比较低。鉴于这种情况，sort 会评估序列的大小，然后决定使用 Quick Sort 或者 insertion sort。

之前还说过不当的基准点选择，会导致Quick Sort算法的性能下降， sort 中当分割行为有恶化的倾向时，转而使用 heap sort，使效率维持在heap sort 的 O( N log N)。这种方法叫做 Introspective Sorting（内省式排序），简称 IntroSort。

如果我们令某个大小以下的序列滞留在 “几近排序但尚未完成” 的状态，最后在以一次 Insertion Sort 将所有这些 “几近排序但尚未竟全功” 的子序列做一次完整的排序，其效率一般认为会比 “将所有子序列彻底排序” 更好。

千呼万唤的 STL sort 代码如下：

template<class RandomAccessIterator>
inline void sort( RandomAccessIterator first, RandomAccessIterator last)
{
	if( first != last)
	{
		//把序列排序成 “几近排序但尚未完成” 的状态
		__introsort_loop(first, last, value_type(first), __lg(last-first)*2);
		//在做一次快速排序，是序列达到想要的效果
		__final_insertion_sort(first, last);
	}
}

//__lg 用来控制分割恶化的情况
//找出 2^k <= n 的最大值 k
template<class Size>
inline Size __lg( Size n)
{
	Size k;
	for( k =0; n>1;n>>=1)
		++k;
		
	return k;
}

当元素个数为40时，__introsort_loop de 最后一个参数是 5*2，意思是最多允许分割10层。

//注意，本函数内许多迭代器运算，只适用于RandomAccess Iterators
template<class RandomAccessIterator, class T, class Size>
void __introsort_loop( RandomAccessIterator first,  RandomAccessIterator last, T*, Size depth_limit)
{
	//__stl_threshold 是个全局常数，稍早定义为const int 16
	while( last - first > __stl_threshold )
	{
		if( depth_limit == 0)
		{
			partial_sort(first, last, last);	//至此，分割恶化，改用 heapsort
			return;
		}
		
		--depth_limit;
		RandomAccessIterator cut = __unguarded_partition( first, last, T(__median(*first, *(first+(last-first)/2), *(last-1))));
		//对右半段递归进行sort
		__introsort_loop(cut, last, value_type(first), depth_limit);
		//对做半段进行排序，只不过使用的是while循环
		last = cut;
	}
}

当 __introsort_loop() 结束， [first, last) 内有多个 “元素个数少于16” 的子序列，每个子序列都有相当程度的排序，但尚未完全排序。回到母函数 sort，在进入 __final_insertion_sort()。代码如下：

template<class RandomAccessIterator>
void __final_insertion_sort( RandomAccessIterato first, RandomAccessIterato last)
{
	if( last - first > __stl_threshold)
	{
		__insertion_sort(first, first+__stl_threshold);
		__unguarded_insertion_sort(first + __stl_threshold, last);
	}
	else
		__insertion_sort(first, last);
}

首先判断元素个数是否大于 16。如果答案为否，就调用 __insertion_sort() 加以处理。如果答案为是，就将 [first, last) 分割为长度 16 的一段子序列，和另一段剩余子序列，在针对两个子序列分别调用 __insertion_sort 和 __unguarded_insertion_sort。

__unguarded_insertion_sort 的代码如下：

template<class RandomAccessIterator>
inline void __unguarded_insertion_sort( RandomAccessIterator first, RandomAccessIterator last)
{
	__unguarded_insertion_sort_aux(first, last, value_type(first));   	
}

template<class RandomAccessIterator, class T>
inline void __unguarded_insertion_sort_aux( RandomAccessIterator first, RandomAccessIterator last, T*)
{
	for(RandomAccessIterator i = first; i != last; ++i)
		__unguarded_linear_insert( i, T(*i));	//内循环	
}

6、merge_sort（归并排序）

merge_sort 的原理是 “分治法” 的一个典型的应用。将一个大的序列，分解成小的序列，然后对小的序列进行操作，在把小的序列进行合并。

首先，将区间对半分割，左右两段各自排序，在利用 inplace_merge 重新组合为一个完整的有序序列。对半分割的操作可以递归进行，直到每一小段的长度为 0 或 1，那么该小段也就自动完成了排序。代码如下：

template<class BidirectionalIter>
void mergesort( BidirectionalIter first,
				BidirectionalIter last)
{
	typename iterator_traits<BidirectionalIter>::difference_type n = distance(first, last);
	
	if( n == 0 || n == 1)
		return;
	else
	{
		BidirectionalIter mid = first + n/2;
		mergesort(first, mid);
		mergesort(mid, last);
		inplace_merge(first, mid, last);
	}
}

Merge sort 的复杂度为O（N log N）。虽然这和 Quick Sort 是一样的，但因为 Merge Sort 需借用额外的内存，而且在内存你之间移动数据也会耗费不少时间，所以 Merge sort 的效率比不上 Quick sort。

好了排序就整理到这里了，还有冒泡跟选择排序没有整理，之后有机会吧，五一了不知道大家都去哪里玩了？

感谢大家，我是假装很努力的YoungYangD（小羊）。

参考资料：
《STL源码剖析》