排序
一、什么是排序
将一组杂乱无章的数据按照一定规律顺次排列起来的运算。
注：如果参与排序的数据节点包含多个数据域，那么排序往往是针对其中某个域而言。比如学生有学号、成绩、身高等。
排序的应用非常广泛，比如excel中、文件中、二分法查找等都有用到排序，因此很有必要研究排序。
二、排序的分类
- 按数据存储介质分：
内部排序：数据量不大，数据在内存，无需内外存交换数据
外部排序：数据量很大，数据在外存，需要分批调入数据进内存排序
- 按比较器个数：
串行排序：同一时刻比较一对元素
并行排序：同一时刻比较多对元素
- 按主要操作：
比较排序：插入排序、交换排序、选择排序、归并排序
基数排序：不比较元素大小，仅仅根据元素本身的取值确定其有序位置？？
- 按辅助空间：
原地排序：辅助空间用量为O(1)，即所占的辅助存储空间与参加排序的数据量大小无关。
非原地排序：辅助空间用量超过O(1)，与上相反。
- 按稳定性可分为：
稳定排序：数值相等的元素排序之后相对次序不变，比如A原本在A‘前，排序后A依旧在A‘前。
非稳定排序：与上相反。
排序的稳定性只对结构类型数据排序有意义。
- 按自然性可分为：
自然排序：刚开始很多部分就有序了
非自然排序：与上相反。
接下来讨论顺序结构、内部排序、串行排序的比较排序。
注意：以下所有讨论的数组a，a[0]都作为哨兵，用来存储中间比较值。
三、插入排序
（1）直接插入排序
基本思想：
在插入a[i]前，数组a的前半段（a[1]~a[i-1]）是有序段，后半段(a[i]~a[n-1])是停留与输入次序的“无序段”
插入a[i]使a[0]~a[i-1]有序，也就是要为a[i]找到有序位置j，将a[i]插入在a[j]的位置上。
过程分析：
程序如下：
一个一个比较：
#include<stdio.h> #define length 11 #define MaxInt 30000 int main() { int a[length+1]={MaxInt,3,5,10,16,7,32,83,23,54,29,96}; int i,j; printf("原先顺序\n"); for(i=1;i<length;i++) printf("%d ",a[i]); printf("\n"); for(i=2;i<=length;i++) { if(a[i]<a[i-1])//判断是否要移动 { a[0]=a[i]; for(j=i-1;a[0]<a[j];j--)//找需要插入的位置 a[j+1]=a[j]; //循环结束，j就为要插入的位置 a[j+1]=a[0]; //因为循环执行完后j还要-1 } } printf("之后顺序\n"); for(i=1;i<length;i++) printf("%d ",a[i]); return 1; }
折半比较：
#include<stdio.h> #define length 11 #define MaxInt 30000 int main() { int a[length+1]={MaxInt,3,5,10,16,7,32,83,23,54,29,96}; int i,j; int low,high,mid; printf("原先顺序\n"); for(i=1;i<length;i++) printf("%d ",a[i]); printf("\n"); for(i=2;i<=length;i++) { a[0]=a[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(a[0]<a[mid]) high=mid-1; else low=mid+1; }//循环结束，high+1则为插入位置 for(j=i-1;j>=high+1;j--) a[j+1]=a[j]; a[high+1]=a[0]; } printf("之后顺序\n"); for(i=1;i<length;i++) printf("%d ",a[i]); return 1; }
（2）希尔排序
前面都是每进行一次比较，就移动一格；而希尔排序则是一次移动一大格。
基本思想：
先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
因此需要一个增量序列，增量序列必须是递减的，最后一个必须是1，增量序列内应该也是互质的。至于如何选择最好的增量序列，目前数学家还没有找到。
过程分析：
关键程序：
void ShellSort(Sqlist &L, int dlta[],int t)//希尔排序 { //L是有哨兵的顺序序列，dlta是增量序列，t是增量序列元素个数。 //比如上图增量序列就可以为[5,3,1] for(k=0;k<t;k++) Shellnsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序 } void Shellnesert(Sqlist &L,int dk) { //对顺序表L进行一趟增量dk的Shell排序，dk为步长因子 for(i=dk+1;i<=L.length;++i)//i=dk+1的原因看图，length不包括哨兵 if(r[i].key<r[i-dk].key]) { r[0]=r[i]; for(j=i-dk;r[0].key<r[j].key;j=j-dk)//实际上还是直接插入排序 r[j+dk]=r[j]; r[j+dk]=r[0];//因为结束是j-dk } }
四、交换排序
（1）冒泡排序
冒泡排序大一老师讲过，不细讲，直接上程序
#include<stdio.h> #define MAXINT 30000 #define length 10 int main() { int a[length+1]={MAXINT,44,33,55,11,6,8,5,7,4,3}; int i,j,t; for(i=1;i<=length-1;i++) for(j=1;j<=length-i;j++) { if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } for(i=1;i<length+1;i++) printf("%d ",a[i]); return 1; }
（2）快速排序
基本思想：
任取一个元素（常取第一个）为中心
所有比它小的元素一律前放，比它大的元素一律后返，形成左右两个子表；
对各个子表重新选择中心元素并依此规则调整
直到每个子表的元素只剩一个
过程分析图解：
后面两个子表递归即可
程序：
void main() { QSort(L,1,L.Length); } void QSort(SqList &L,int low,int high) { if(low<high)//长度大于1 pivotloc=Partition(L,low,high); //将[low,high]一分为二，pivotloc为中心点位置，同时排好子表顺序 QSort(L,low,pivotloc-1);//对低子表递归排序 QSort(L,pivotloc+1,high);//对高子表递归排序 } int Partition(SqList &L,int low,int 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]; hile(low<high && L.r[low].key<=pivotkey) low++; L.r[high]=L.r[low]; } L.r[low]=L.r[0];//high也行 return low; //high也行 }
五、选择排序
（1）简单选择排序
基本思想：
在待排序的数据中选出最大（小）的元素放在其最终的位置，总共需要n-1趟。
程序：
void SelectSort(SqList &K) { int k; for(i=1;i<L.length;i++) { k=i;//假设当前最小下标就为i for(j=i+1;j<=L.length;j++) if(L.r[j].key<L.r[k].key) k=j;//记录最小值的位置 if(k!=i) L.r[i]与L.r[k]交换值 } }
（2）堆排序
堆排序我实在想不出目前有什么用，以后用到再说。
六、归并排序
基本思想：
将两个或两个以上的有序子序列“归并”为一个有序序列。
过程分析：
程序：略。
七、基数排序
过程分析：
（只）常用于对多数据域的时候排序。比如对一个学生，既要排序数学成绩，但数学成绩得按照学号大小又要进行一次排序
八、 排序总结表