数据结构内部排序算法笔记
数据结构也快要结课了，在复习的时候发现排序算法挺多而且很多并不熟悉，所以决定写一篇博客复习一下这些算法。
先列一下排序算法的目录吧：
以下所指的数据类型为：
typedef int KeyType;
typedef struct{
KeyType key;
InfoType otherinfo; //其他数据项
}RedType;
typedef struct{
RedType r[MAXSIZE+1]; //r[0]闲置或作哨兵
int length;
}SqList;
一、插入排序
直接插入排序
思想： 将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。即：先将第一个记录看作有序的，然后从第二个记录起和第一个比较、插入，这样就得到了一个有两个记录的有序表；然后再将第三个记录和已得到的有序表进行比较、插入......一直到整个序列有序。
算法：
void InsertSort(SqList &L){
//对顺序表L进行直接插入排序
for(int i=2;i<=L.length;++i){
if(L.r[i].key<L.r[i-1].key){ //将L.r[i]插入到有序表中
L.r[0]=L.r[i]; //复制“哨兵”
L.r[i]=L.r[i-1];
for(j=i-2;L.r[0].key<L.r[j].key;--j)
L.r[j+1]=L.r[j]; //记录后移
L.r[j+1]=L.r[0]; //插入到正确位置
}
}
}
分析： 时间复杂度为O(n2)，比较次数最少为n-1次（不需要移动），最多为（n+2)(n-1)/2次（记录为逆序的时候），最多移动次数也达到最大值
(n+4)(n-1)/2。直接插入排序是稳定的，适用于n较小的情况。
希尔排序
思想： 先将整个排排序的序列分割成若干个序列（并不是连续的几个记录，而是相隔dk的记录）分别进行直接插入排序，完成后再将全体记录进行排序。过程是：先取dk作为增量，将记录分为{R[1],R[1+dk],R[1+2dk},...},{R[2],R[2+dk,R[2+2dk],...]}....，再将每个序列进行直接插入排序，一趟后每个小序列有序；待每个序列有序后，再次取更小的dk，重复上述过程，直至dk减到1（dk不是连续的数，应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况）为止。
算法：
void ShellInsert(SqList &L,int dk){
//对顺序表L进行一趟希尔插入排序。
//相对于直接插入排序：
// 前后记录位置的增量是dk，不是1；
// r[0]是暂存单元，不是哨兵。当j<=0时，插入位置已找到。
for(int i=dk+1;i<=L.length;i++){
if(L.r[i].key<L.r[i-dk].key){ //需将L.r[i]插入到有序增量子表中
L.r[0]=L.r[i]; //暂存在L.r[0]中
int j=i-dk；
for(j=i-dk;(j>0)&&(L.r[0].key<L.r[j].key);j-=dk){
L.r[j+dk]=L.r[j]; //记录后移
L.r[j+dk]=L.r[0]; //插入，不可将r[j+dk]改为r[i]
}
}
}
void ShellSort(SqList &L,int dlta[],int t){
//按增量序列dlta[0..t-1]对顺序表L作希尔排序，t为排序的趟数
for(int k=0;k<t;k++){
ShellInsert(L,dlta[k]); //一趟增量为dlta[k]的插入排序
}
}
分析： 希尔排序的时间复杂度与增量序列的选取有关，目前还没有人求得一种最好的增量序列。希尔排序时间复杂度的下界是n(log2n)。希尔排序没有快速排序算法快O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(n2)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单.此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。希尔排序是非稳定的。
折半插入排序
思想： 折半插入排序是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。过程是：在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
算法：
void BInsertSort(SqList &L){
//对顺序表L作折半插入排序
for(int i=2;i<=L.length;++i){
L.r[0]=L.r[i]; //将L.r[i]暂存到L.r[0]
int low=1;
int high=i-1;
while(low<=high){ //在r[low..high]中折半查找有序插入的位置
int m=(low+high)/2; //折半
if(L.r[0].key<L.r[m].key) high=m-1; //插入点在低半区
else low=m+1; //插入点在高半区
}//while
for(int j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; //记录后移
L.r{high+1]=L.r[0] //插入
}//for
}
分析： 折半插入排序所需附加存储空间和直接插入排序相同（一个），仅减少了关键字间的比较次数，而记录移动次数不变，因此折半插入排序的时间复杂度仍为O(n2)。
二、快速排序
思想： 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字都比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。过程是：假设待排序的序列为{L.r[s],L.r[s+1],...,L.r[t]},首先任意选取一个记录（通常选第一个记录L.r[s]）作为枢轴（pivot），将所有关键字比它小的记录都安置在它的位置之前，将所有关键字比它大的都放置在它之后，枢轴记录最后所落的位置为i作分界线，将原序列分割为{L.r[s],L.r[s+1],...,L.r[i-1]}和{L.r[i+1],L.r[i+2],...,L.r[t]}。这个过程称为一趟。做法是：设两个指针low和high，枢轴记录的关键字为pivotkey，1、先从high开始向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录交换，2、然后从low开始向后搜索找到第一个关键字大于pivotkey的记录和枢轴记录交换；重复这两步直至low=high为止。
算法：
void Partition(SqList &L,int low,int high){
//交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位，并返回其所在位置，
//此时在它之前（后）的记录均小于（大于）它。
L.r[0]=L.r[low] //用子表的第一个记录作枢轴记录
int 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[low]=L.r[0]; //枢轴记录到位
return low; //返回枢轴位置
}
分析： 快速排序的平均时间为T(n)=knlnn(平均时间复杂度为O(nlogn)),n为待排序序列中记录的个数，k为某个常数，就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。最坏情况时间复杂度为O(n2),辅助存储空间O(logn)。快速排序也是不稳定的。
三、选择排序
简单选择排序
思想： 每一趟在n-i+1(i=1,2,...,n-1)个记录中选出关键字最小的记录，并与第i个记录交换之。一趟的操作为令i从1至n-1，进行n-1趟选择排序操作。
算法：
void SelectSort(SqList &L){
for(int i=1;i<L.length;i++){ //选择第i小的记录，并交换到位
j=SlectMinKey(L,i); //在L.r[i...L.length]间选择关键字最小的值
if(i!=j){ //与第i个记录交换
int temp=L.r[i];
L.r[i]=L.r[j];
L.r[j]=temp;
}
}
}
分析： 简单选择排序是不稳定的排序，记录移动的次数最小是0，最大是3(n-1)，关键字之间的比较次数为n(n-1)/2，时间复杂度是O(n2)。
树形选择排序
思想： 首先对n个记录的关键字进行两两比较，然后再n/2个较小的关键字之间再进行两两比较，如此反复直至找到最小关键字的记录为止。
算法：
略
分析： 除最小关键字之外，每选择一个次小的关键字仅需要进行log2n次比较，时间复杂度为O(nlogn)，但是有辅助存储空间大和最大值进行多余比较的缺点。
堆排序
定义： 左右子树都不小于结点小（小根堆）或者都不大于结点（大根堆）。
思想： 若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素中的次小值，如此反复即可得到一个有序序列。
算法：
typedef SqList HeapType; //堆采用顺序表存储表示
void HeapAdjust(HeapType &H,int s,int m){
//已知H.r[s...m]中记录的关键字除H.r[s].key外均满足堆的定义，本函数调整H.r[s]的关键字，使H.r[s...m]成为一个大根堆
int rc=H.r[s];
for(int j=2*s;j<=m;j*=2){ //沿关键字较大的孩子结点向下筛选
if(j<m&&H.r[j].key<H.r[j+1].key) ++j; //j为关键字较大的记录的下标
if(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){
for(int i=H.length/2;i>0;--i){ //把H.r[1...L.length]建成大根堆
HeapAdjust(H,i,H.length);
}
for(int i=H.length;i>1;--i){ //将堆顶记录与当前未经排序子序列H.r[1...i]中最后一个记录互相交换
int temp=H.r[1];
H.r[1]=H.r[i];
H.r[i]=temp;
HeapAdjust(H,1,i-1); //将H.r[1...i-1]重新调整为大根堆
}
}
分析： 只需要一个辅助存储空间，每个待排序的记录仅占一个存储空间。对于记录较少的文件并不值得提倡，最坏的情况下时间复杂度也为O(nlogn)，也是不稳定的。
四、归并排序
思想： 将两个或两个以上的有序表合成一个新的有序表。一趟归并排序的操作是调用n/2h次算法Merge将SR[1..n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，并存放在TR[1..n]中。
算法：
void Merge (RcdType SR[],RcdType TR[],int i,int m,int n){
int j,k;
for (j=m+1,k=i;i<=m&&j<=n;++k) {
if(SR[i].key<=SR[j].key) TR[k] = SR[i++];
else TR[k] = SR[j++];
}
if (i<=m){
while(k<=n&&i<=m) TR[k++]=SR[i++];
}
if (j<=n){
while(k<=n&&j<=n) TR[k++]=SR[j++];
}
} // Merge
void MSort(RcdType SR[],RcdType &TR1[],int s,int t){
//将SR[s..t]归并排序为TR1[s...t]
if(s==t) TR1[s]=SR[s];
else{
m=(s+t)/2; //将SR[s..t]平分为SR[s..m]和SR[m+1..t]
MSort(SR,TR2,s,m); //递归的将SR[s..m]归并为有序的TR2[s..m]
MSort(SR,TR2,m+1,t); //递归的将SR[m+1..t]归并为有序的TR2[m+1..t]
Merge(TR2,TR1,s,m,t); //将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
}
}
void MergeSort(SqList &L){ //归并排序
MSort(L.r,L.r,1,L.length);
}
分析：归并排序是稳定的，所需辅助空间和待排记录等数量，时间复杂度为O(nlogn)，需要进行log2n趟。
五、基数排序
顺序基数排序
**思想：**基数排序起源于箱(桶)排序，设置若干个箱子(桶),依次扫描待排序的记录,A[1],A[2],…,A[n],把关键字为k的记录放在第k个箱子里,按序号将非空的箱子里的记录收集起来。但如果如果关键字位数太大，这样做空间复杂性和时间复杂性都太大。具体操作是先设待排记录A的关键字最大是figure位的正整数。然后1、从最低位(个位)开始，扫描关键字的pass位,把等于0的插入Q[0],…,等于9的插入Q[9]。2、将Q[0],…,Q[9]中的数据依次收集到A[]中。最后pass+1直到figure，重复执行1，2两步。
算法：
int RADIX(int k,int p){
//取关键字k 的第p位，p从1开始
return((k/pow10(p-1))%10);
}
void radixsort(int figure, QUEUE &A){
QUEUE Q[10];
records data;
int pass,r,i; //pass用于位数循环,r取位数
for(pass=1;pass<=figure;pass++){
for(i=0;i<=9;i++){
MAKENULL(Q[i])； //把10个队列置空
while(!EMPTY(A)) {
data=FRONT(A); //取A中元素dada，
DEQUEUE(A);
r=RADIX(data.key,pass); //计算data的关键字的第pass位的值r
ENQUEUE(data,Q[r]); //放入队列Q[r]中
}//while
}//for
}//for
}//radixsort
分析： 基数排序是稳定的，设关键字位数为d，则时间复杂性为O(dn)，考虑到d是一个常数，时间复杂性为O(n)，空间复杂性O(n)。
各种排序算法的比较
放一张老师的课件：
