1如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。如果按内部排序过程中所需的工作量来区分，则分为3类：（1）简单的排序方法，其时间复杂度为O（n2）；（2）先进的排序方法，其时间复杂度为O(nlogn);(3)基数排序，其时间复杂度为O(d.n)
2.直接插入排序，时间复杂度为O(n2),方法简单适合记录数量比较小的时候。
voidInsertSort(SqList &L)
{
//对顺序表L作直接插入排序
for(i =2;i<=L.length;++i)
{
if(LT(L.r[i].key,L.r[i-1].key))
{
L.r[0] = L.r[i]; //复制为哨兵
L.r[i] = L.r[i-1];
for(j = i-2;LT(L.r[0].key,L.r[j].key;--j)
L.r[j+1] = L.r[j];//记录后移
L.r[j+1] = L.r[0];//插入到正确位置
}
}
}
3.折半插入排序算法(减少了关键字间的比较次数，记录移动次数和存储空间不变，故时间复杂度O(n2))
voidBinsertSort(SqList &L)
{
//对顺序表L作折半插入排序
for(i = 2;i<=L.length;++i)
{
L.r[0] = L.r[i]; //将L.r[i]暂存到L.r[0]
low = 1;high = i-1;
while(low<=high)
{
m = (low+high)/2;//折半
if(LT(L.r[0].key,L.r[m].key))high = m-1;//插入点在低半区
else low = m +1;
}
for(j =i-1;j>=high+1;--j) L.r[j+1] = L.r[j];//记录后移
L.r[high+1] = L.r[0];
}
}
4.希尔排序基本思想是先将整个待排序记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。特点是子序列的构成不是简单地“逐段分割”而是将相隔某个“增量”的记录组成一个子序列。
5.冒泡排序：若初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；反之，若初始序列为“逆序”序列，则需进行n-1趟排序，则需进行n(n-1)/2次比较，并作等数量级的记录移动。因此，总的时间复杂度为O(n2)
6.快速排序是对冒泡排序的一种改进。目前被认为是最好的一种内部排序方法，在所有同数量级O(nlogn)的排序方法中，其平均性能最好。
intPartition (SqList &L,int low,int high)
{
//交换顺序表L中子表r[low……high]的记录，枢轴记录到位，并返回其所在位置，此时再它之前的记录均不大于它
L.r[0]= L.r[low];//用子表的第一个记录作枢轴记录
pivotkey= L.r[low].key;//枢轴记录关键字
while(low<high)//从表的两端交替地向中间扫描
{
while(low<high&&L.r[high].key>=pivotkey) –high;
L.r[low] = L.r[high]; //将比枢轴记录小的记录移到低端
while(low<high &&L.r[low].key<=pivotkey) ++low;
L.r[high] = L,r[low]; //将比枢轴记录大的记录移到高端
}
L.r[ow]=L.r[0];//枢轴记录到位
returnlow;//返回枢轴位置
}
voidQSort(SqList &L,int low,int high)
{
//对顺序表L中的子序列L.r[low……high]作快速排序
if(low<high)
{
pivotloc = Partition(L,low,high);//将L.r[low……high]一分为二
QSort(L,low,pivotloc-1);//对低子表递归排序，pivotloc是枢轴位置
QSort(L,pivotloc+1,high) ;//对高子表递归排序
}
}
voidQuickSort(SqList &L)
{
//对顺序表L作快速排序
QSort(L,1,L.length);
}
1. 堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占用一个存储空间。在最坏情况下，时间复杂度为O(nlogn)。相对于快速排序来说，这是堆最大优点。
2. TypedefSqList HeapType;//堆采用顺序表存储表示
void HeapAdjust(HeapType&H,int s,int m)
{
//已知H.r[s..m]中记录的关键字除H,r[s].key之外均满足堆的定义，本函数调整H.r[s]的关键字，使H.r[s//m]成为一个大顶堆
rc =H.r[s];
for(j =2*s;j<=m;j*=2)//沿key较大的孩子结点向下筛选
{
if(j<m&<(H.r[j].key,H.r[j+1].key)) ++j;//j为key较大的记录的下标
if(!LT(rc.key,H.r[j].key))break;//rc应插入在位置s上
H.r[s]= H.r[j]; s = j;
}
H.r[s] = rc;
}
void HeapSort(HeapType &H)
{
//对顺序表H进行堆排序
for(i = H.length/2;i>0;--i)//把H.r[1…H.length]建成大顶堆
HeapAdjust(H,i,H.length);
for(i = H.length;i>1;--i)
H.r[1]? àH.r[i];//将堆顶记录和当前未经排序子序列Hr[1..i]中最后一个记录相互交换
}
3. 归并排序，与快速排序和堆排序相比，归并排序的最大特点是它是一种稳定的排序方法。但是一般很少利用2-路归并排序法进行内部排序。
4. 基数排序主要是通过关键字间的比较和移动记录这两种操作，而实现基数排序不需要进行记录关键字间的比较。有分配和收集两个操作，对于n个记录(每个记录含d个关键字)进行链式基数排序的时间复杂度为O(n +rd)
5. 各种排序算法的比较
（1） 从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。
（2） 简单排序包括希尔排序之外的所有插入排序，起泡排序和简单选择排序，其中以直接插入排序最简单，当序列中的记录“基本有序”或n值较小时，它是最佳的排序方法。因此常将它和其他的排序方法诸如快速排序、归并排序等结合。
（3） 基数排序适用于n值很大而关键字较小的序列。
（4） 从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O（n2）的简单排序法也是稳定的。快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。
原文：http://blog.csdn.net/woailvmengmeng/article/details/19341421
