从上学接触到编程开始，到工作了几年。有关排序算法的内容反反复复有接触，但是要说每一种排序算法的细节都能说清，那就有难度了。
一来算法难度有深有浅。有比较简单的冒泡，插入，也有复杂的堆排序，快排这些。
二来排序算法实际上成型已久，是个套路的东西。
三来平时工作用不到每一种算法。实际数据不多的时候用冒泡足够了。数据多时，用快排足够了。
关联容器内部有自动排序，序列容器中只有vector，deque的迭代器是随机位置迭代器(RandomAccessIterators)，因此只有vector和deque能使用std::sort()。
后面讲快排会讲为什么sort()必须是随机位置迭代器。
今天看到一个实际工作中经常用到的例子，但是平时没有注意它的原理。
这个例子有助于加深对排序的理解。便是STL里面的sort()算法。
sort()是有策略进行排序。具体规则如下：
// 1.数据量大时Quick Sort（快排）
// 2.分段时数据量小于门槛，改用Inserition Sort（插入排序）
// 3.递归层次太深，改用Heap Sort（堆排序）
里面使用了3种排序。既有复杂度O(n*n)的插入排序，也有复杂度O(nlogn)的快排和堆排序。
先分别来看这3种排序。从简单的插入排序开始吧。
插入排序
假设待排序的序列是a[0..n - 1]，总共n个数据。
1）a[0]是已排序的序列，a[i, n - 1]是未排序的序列。令i = 1。
2）取a[i]插入到有序序列合适位置，使得新序列有序。
3）重复2步骤，直到i == n - 1。
外层循环是从1到n-1，内层循环是找插入位置，无需遍历所有位置，当a[j - 1] < a[j]即可停止，否则继续找位置，同时交换a[j - 1]，a[j]的位置。
void InsertSort(int *a, int count) { if (count <= 1) { return; } for (int i = 1; i < count; ++i) { for (int j = i; j >= 0 && a[j - 1] > a[j]; j--) { swap(a[j - 1], a[j]); } } }
有两层循环，算法复杂度是O(n*n) 。稳定不稳定，取决于中间的判断条件。a[j - 1] > a[j]则是稳定的，条件变成a[j - 1] >= a[j]则是不稳定的。
快速排序
快排的核心是分治法。
1.如果序列S中数据的数量是0或者1。结束。
2.取S中的任意一个数字，当作枢纽v。
3.将S分割成两段L，R，使得L中的元素全部小于等于v，R中的元素全部大于等于v。
4.将L，R递归执行快排。
其中第2步，选取一个数字做枢纽。可以是任意的数字，通常用的是median-of-three。从首尾和中间数中，选择中值。
比如序列：1，4，5，7，9，8，3。那么1，7，3中选3作为枢纽来对序列进行分割。
为了能快速取出中间元素，迭代器必须支持随机位置（RandomAccess）。
三个数取中值的函数，只有画线段标位置，容易看出a，b，c三者的大小关系。
int median(int a, int b, int c) { if (a < b) { if (b < c) { return b; // a < b < c } else { if (a < c) { return c; // a < c <= b } else { return a; // c <= a < b } } } else { if (b < c) { if (a < c) { return a; // b <= a < c } else { return c; // b < c < a } } else { return b; // c <= b <= a } } }
再来看分割算法：
令first指向头元素，last指向尾元素。first向尾端移动，last向头端移动。
当first大于等于枢纽时，停止。当last小于等于枢纽时，停止。
检查first，last是否交错（first >= last），如果交错返回first。如果没有交错，first，last各自向中央移动一个位置。
重复上面的步骤。
最终返回的first是右半部分的起点。左半部分全部小于等于枢纽，右半部分全部大于等于枢纽。
来看代码，RandomAccessIter可以理解成一个普通指针。
int* partition(int *first, int *last, int pivot) { while (true) { while (*first < pivot) first++; while (*last > pivot) last--; if (first >= last) return first; swap(*first, *last); first++; last--; } }
引用：
1.《STL源码剖析》
2.《MoreWindows白话经典算法之七大排序第2版》