－快速排序
算法概述：与归并相似，分而治之
void Quicksort ( ElementType A[ ] , int N )
{
if ( n < 2 ) return ;
pivot = 从A[ ] 中选出一个主元；
将 S＝{ A[ ] \ pivot } 分成2个独立子集：
A1 = { a属于S | a <= pivot } 和
A3 = { a属于S | a >= pivot } ;
A[ ] = Quicksort( A1 , N1 )并 { pivot }并Quicksort( A2 , N2 ) ;
}
选主元：
取中位数
ElementType Median3 ( ElementType A[ ] , int Left , int Right )
{
int Center = ( Left + Right ) / 2 ;
if ( A[ Left ] > A[ Center ] )
Swap ( &A[ Left ] ) , &A[ Center ] ) ;
if ( A[ Left ] > A[ Right ] )
Swap ( &A[ Left ] ) , &A[ Right ] ) ;
if ( A[ Center ] > A[ Right ] )
Swap ( &A[ Center ] ) , &A[ Right ] ) ;
Swap ( &A[ Center ] , &A[ Right - 1 ] ) ; // 将pivot藏到右边
return A[ Right - 1 ] ; // 返回主元，它在Right - 1这个位置
}
子集划分
每次选定主元并完成子集划分后，主元插入的位置都是它的最终位置，它一次性放到了正确位置以后都不用移动
如果有元素正好等于pivot，停下来交换？不交换，继续移动指针？比较后选择交换
快速排序问题：该算法用到递归，对于小规模数据（比如小于100的数据）可能还不如插入排序快
所以，当递归的数据规模充分小，则停止递归，直接调用简单排序；在程序中定义一个Cutoff的阈值，小于该值则调用简单算法
算法实现：
void Quicksort ( ElementType A[ ] , int Left , int Right )
{
if ( Cutoff <= Right - Left ) {
Pivot = Median3 ( A , Left , Right ) ;
i = Left ; j = Right - 1 ; // 开始做子集划分
for ( ; ; ) {
while ( A[ ++ i ] < Pivot ) { }
while ( A[ - - j ] > Pivot ) { }
if ( i < j )
Swap ( &A[ i ] , &A[ j ] ) ;
else break ; // 子集划分结束
}
Swap ( &A[ i ] , &A[ Right - 1 ] ) ;
Quicksort ( A , Left , i - 1 ) ;
Quicksort ( A , i + 1 , Right ) ;
}
else
Insertion_Sort ( A + Left , Right - Left + 1 ) ; // 当超过Cutoff阈值，开始用简单排序
}
统一接口：
void Quick_Sort ( ElementType A[ ] , int N )
{
Quicksort( A , 0 , N - 1 ) ;
}
－表排序
待排元素不是简单的数字而是比较大的结构，移动元素步骤不能忽略不计
排序过程中不需要移动原始数据，而是移动指向它们的指针，这样的排序叫间接排序；
定义一个指针数组作为“表”（table），如果仅要求按顺序输出，则输出：
A[ table[0] ], A[ table[1] ], …… , A[ table[N-1] ]
物理排序：
N个数字的排列由若干个独立的环组成
将物理排序独立成若干个独立的操作，开辟一个临时空间，从环中取出一个元素暂时放入该空间，依次将该环中其他元素 一一放置到正确的位置，最后将取出的元素拿出放进环中最后空出来的位置。
最好情况：初始即有序
最坏情况：有N/2个环，每个环包含2个元素，这是需要3N／2次元素移动。（每移动一对元素要走三步）
－基数排序
桶排序 eg：有N个学生，他们的成绩是0到100之间的整数，如何在线性时间内将学生按成绩排序？
0到100之间一共有101（M）个成绩值，给每个成绩值建立一个桶，桶实际上是链表；每输入的一个同学的成绩，就按成绩将该同学放入相对于的链表中
void Bucket_Sort ( ElementType A[ ] , int N )
{
count[ ] 初始化 ;
while ( 读入1个学生成绩grade )
将该学生插入count[ garde ]链表；
for ( i = 0 ; i < M ; i ++ ) { // M是成绩值总数
if ( count[ i ] )
输出整个count [ i ]链表；
}
}
基数排序 eg：假设有N＝10个整数，每个整数的值在0到999之间（于是有M＝1000个不同的值）此时再用桶排序则不合算
基数是进制的基数，如0到999之间的数，最多是三位数，每个位上的基数有10种可能
输入序列：64，8，216，512，27，729，0，1，343，125
用“次位优先”（Least Significant Digit）即优先比较个位
建立0～9十个桶，第一趟排序按照每个数字个位上的数放入相应的桶，第二趟按十位上的数对应放入相应的桶，第三趟比百位数，
时间复杂度 T＝O（P（N＋B））
如果桶的数量足够小，整个复杂度是线性的
多关键字排序，如扑克牌按花色、面值两种关键字排序
多关键字可理解为多位数字，花色是十位，面值是个位
若用主位优先，分为四个桶，再在每个桶里按面值排序
次位排序更为便捷，为面值建立13个桶；将结果合并，然后再为花色建四个桶
－排序算法的比较：
简单排序：简单选择排序、冒泡排序、直接插入排序。
选择排序是跳着交换的，导致其不稳定性；简单排序时间复杂度较高，不过代码较简单，其中冒泡排序和直接插入排序是稳定的
希尔排序平均时间复杂度较低，但它的好坏取决于增量序列，不过最坏情况下时间复杂度依然是N的平方
堆排序和归并排序，理论上，时间复杂度都是 N*logN，其中堆排序的N可能很大，所以某些情况下会比快速排序要慢，且它是不稳定的；归并排序是稳定的，但需要一定空间；
快速排序是递归的，所以需要logN的空间复杂度，最坏情况下时间复杂度是N的平方，是不稳定排序
基数排序某些情况下近乎线性，取决于桶
