文章目录
排序
1.基本概念
排序（sorting）又称分类，将一组杂乱无章的数据按一定规律排列起来。即将无序序列排成一个有序序列（由小到大或由大到小）的运算。
2.分类
我们可以看到排序的分类非常多：
-
按存储介质可分为：
-
内部排序：数据量不大，数据在内存，无需内外存交换数据
-
外部排序：数据量较大，数据在外存（文件排序）
外部帕西时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂的多。
-
-
按比较器个数可分为：
- 串行排序：单处理机（同一时刻比较一对元素）
- 并行排序：多处理机（同一时刻比较多对元素）
-
按主要操作可分为：
- 比较排序：通过比较来决定元素间的相对次数，由于其时间复杂度不能突破O ( n log n ) ，因此也称为非线性时间比较类排序。
- 基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置。它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
-
按稳定性可分为：
- 稳定排序：能够使任何数值相等的元素，排序以后相对次序不变
- 非稳定性排序：不是稳定排序的方法。
- 排序的稳定性只对结构型数据排序有意义。例如：
- 排序方法是否稳定，并不能衡量一个排序算法的优劣。
- 按辅助空间可分为：
- 原地排序：辅助空间量为O(1)的排序方法（所占的辅助空间与参与排序的数据量大小无关），通常意义上的排序，都是指的原地排序。
- 非原地排序：辅助空间量超过O(1)的排序方法。
- 按自然性可分为：
- 自然排序：输入数据越有序，排序的速度越快的排序方法
- 非自然排序：不是自然排序的方法。
- 按排序所需工作量
- 简单的排序方法：T(n)=O(n2)
- 基数排序：T(n)=O(d.n)
- 先进的排序方法：T(n)=O(nlogn)
2.存储结构
记录序列以顺序表存储:
#define MAXSIZE 20 //设记录不超过20个
typedef int KeyType; //设关键字为整形量（int型）
Typedef struct{ //定义每个记录（数据元素）的结构
KeyType key; //关键字
InofType otherinfo; //其他数据项
}RedType;//Record Type
Typedef struct{ //定义顺序表的结构
RedType r[MAXSIZE +1]; //存储顺序表的向量
//r[0]一般作哨兵或缓冲区
int length; //顺序表的长度
}SqList;
一.插入排序
【基本思想】：每步把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
【基本操作】：
- 在有序序列中插入一个元素，保持序列有序，有序长度不断增加。
- 起初，a[0]是长度为1的子序列。然后，逐将a[1]至a[n-1]插入到有序子序列中。
【有序插入方法】：
- 在插入a[i]前，数组a的前半段（a[0]a[i-1]）是有序段，后半段（a[i]a[n-1]）是停留于输入次序的无序段。
- 插入a[i]使a[0]~a[i-1]有序，也就是要为a[i]找到有序位置 j（0<= j <= i），将a[i]插入在a[j]的位置上。
那么，这个插入位置可以在哪呢？
那么，怎么找到这个插入位置呢？
根据插入的方法，我们将插入排序分为以下三种：
1.1直接插入排序
直接插入排序(Straight Insertion Sort)——采用顺序查找法查找插入位置。
【算法思想】
在顺序查找法中我们使用哨兵来提高查找效率，这里同样可以使用：
【算法实现】
void InsertSort(SqList *L){
int i,j;//i表示当前无序部分的第一个元素，j表示寻找插入位置过程中的下标
//依次将R[2]~R[n]插入到前面已排序序列，R[1]为默认排好序的序列，R[0]作为哨兵不存放元素
for(i=2; i<=L->length; i++){
if(L.r[i]key < L.r[i-1].key){//插入前先比较，若当前i比前一位置的大，直接插入有序表中；若小，需将L.r[i]插入有序子表
L.r[0]=L.r[i]; //复制为哨兵
for(j=i-1; L->R[0]<L->R[j]; --j){//从后往前查找待插入位置
L.r[j+1]=L.r[j]; //向后挪位
}
L.r[j]=L.r[0]; //复制到插入位置,即将哨兵上的元素赋值到插入位置
}
}
}
假定初始序列为{ 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 } ，初始时49可以视为一个已排好序的子序列，按照上述算法进行直接插入排序的过程如下图所示，括号内是已排好序的子序列。
【性能分析】
实现排序的基本操作有两个：
（1）“比较”序列中两个关键字的大小
（2）“移动”记录。
-
时间复杂度
- 最佳情况：T(n) = O(n) （数组有序的情况下）
- 最坏情况：T(n) = O(n2) （数组逆序的情况下）
- 平均情况：T(n) = O(n2) 耗时差不多是最坏情况的一半
原始数据越接近有序，排序速度越快。所以，要提高查找速度：
- 减少元素的比较次数
- 减少元素的移动次数
-
空间复杂度：O(1)（仅用了一个辅助单元：哨兵）
-
稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
-
适用性：直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
1.2折半插入排序
查找插入位置时采用折半查找法
【算法思想】
- 比较查找：当high<low时，此时的mid即是要插入的位置，查找比较停止，当前下标[0]~high的位置都小于要插入的数，实际上如果有与要插入的数相等的也在这个区间范围里；同时从low开始到有序区最后一个数都大于要插入的数。
- 后移：将low和其后面的元素统一向后移动一位，腾出位置来（这时，有序区就扩充了一个位置）
- 插入到正确的位置：即high+1所对应的位置
当要插入的数=low=high=mid时，考虑到稳定性，为了能让原本在后面的要插入的数排序之后还在后面，所以此时我们应该将要插入的数插入到high值的后面，也就是令left=mid+1.
【算法实现】
void BInsertSort(SqList &L){
for(i=2;i<=L.length;++i){//依次插入第2~第n个元素
if(L.r[i]key < L.r[i-1].key){//插入前先比较，若当前i比前一位置的大，直接插入有序表中；若小，需将L.r[i]插入有序子表
L.r[0]=L.r[i]; //复制为哨兵
low=1;high=i-1; //采用折半查找法查找插入位置
while(low<=high){
mid=(low+high)/2;
if(L.r[0].key<L.r[mid].key) high=mid-1;//如果哨兵位置比中间位置的值小，就在左半区查找
else low=mid+1;//否则就在右半区查找
}
}
for(int j=i-1;j >high; j--){
L.r[j+1]=L.r[j];
}
L.r[high+1]=L.r[i];
}
}
【性能分析】
（1）比较次数
折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快；
- 它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第 i 个对象时，需要经过⌊log_2i⌋+1次关键吗比较。才能确定它的插入位置；
- 当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差；
- 在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少
（2）移动次数
折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列
- 减少了比较次数，但没有减少移动次数
- 平均性能优于直接插入排序
时间复杂度
- 最佳情况：T(n) = O(n) （数组有序的情况下）
- 最坏情况：T(n) = O(n2) （数组逆序的情况下）
- 平均情况：T(n) = O(n2) 耗时差不多是最坏情况的一半
虽然折半查找的效率比顺序查找的高，但还是被元素的移动拖了后腿，导致最终的时间复杂度都和直接插入排序一样。
- 空间复杂度：O(1)
- 是一种稳定的排序方法
前面我们提到：直接插入排序在基本有序，待排序的记录个数较少的情况下效率比较高。那么，有比折半插入排序还快的吗？怎么才能想办法让排序基本有序，或每比较一次就移动一大步呢？
希尔排序来啦~
1.3希尔排序
现将整个待排序记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
它与插入排序的不同之处在于，它会优先比较距离较远的元素。
特点：①缩小增量②多遍插入排序
希尔增量 gap=length/2
希尔排序的增量序列的选择与证明是个数学难题，希尔增量序列{n/2,(n/2)/2…1}是比较常用的，也是希尔建议的增量，但其实这个增量序列不是最优的。
- 增量序列必须是递减的，最后一个必须是1
- 增量序列应该是互质的
【算法思想】这里重要的是理解分组思想，每一个组其实就是一个插入排序，相当于进行多次插入排序。
①先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。
②然后将gap逐渐减小重复上述分组和排序的工作。
③当到达gap=1时，所有元素在统一组内排好序。
【算法实现】
/*对顺序表L作希尔排序*/
void ShellSort(SqList *L,int dalta[],int t){
//按增量序列dlta[0..t-1]对顺序表L做希尔排序
for(k=0;k<t;++k)
Shelllnsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序
}//ShellSort
void Shelllsert(SqList &L,int dk){
//对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子
for(i=dk+1;i<=L.length;i++)
if(r[i].key < r[i-dk].key){
r[0]=r[i];
for(j=i-dk;j>0 && (r[0].key < r[j].key))
j=j-dk;
r[j+dk]=r[j];
r[j+dk]=r[0];
}
}
【性能分析】
希尔排序算法效率与增量序列的取值有关（简单了解一下）
-
时间复杂度：由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度约为O(n1.25)~O(1.6n1.25)——经验公式。要好于直接排序的O(n2)。
-
空间复杂度：O(1)（仅用了常数个辅助单元）
-
稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
-
适用性：希尔排序算法仅适用于线性表为顺序存储的情况，不宜在链式存储结构上实现。
二.选择排序
2.1简单选择排序
简单选择排序法(Simple Selection Sort) 就是在待排序的数据中选出最大（小）的元素放在其最终的位置。
【算法思想】
①首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
②再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
③重复上诉操作，共进行n-1趟排序后，排序结束。
【算法实现】
void SelectSort(SqList *L){
int i,j,min;
for(i=0; i<L->length-1;i++){ //一共进行n-1趟
min = i; //记录最小元素位置
for(j=i+1; j<L->length; j++){
if(L->R[j] < L->R[min]){ //在R[i...n-1]中选择最小的元素
min = j; //更新最小元素位置
}
}
if(min !=i){
swap(L->R[i], L->R[min]); //swap函数移动元素3次
}
}
}
【性能分析】
-
时间复杂度
移动次数：
- 最好的情况是移动0 次，此时对应的表已经有序；
- 最坏的情况：元素移动的操作次数很少，不会超过3(n-1)次
比较次数：元素间比较的次数与序列的初始状态无关，选择排序所需进行的“比较”次数都相同，始终是n ( n − 1 ) / 2 次，因此时间复杂度始终是O(n2)。
-
空间复杂度：O(1)（仅用了常数个辅助单元）
-
稳定性：不稳定
2.2堆排序
堆排序(Heap Sort)是对简单选择排序进行的一种改进。
堆的定义
从堆的定义可以看出，堆实质是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大根堆(如下图所示)；或者每个结点的值都小于或等于其左右孩子结点的值，称为小根堆。
若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值（次大值）……如此反复，使得能得到一个有序序列，这个过程称之为堆排序。
【算法思想】
那么：如何由一个无序序列建成一个堆？
①调整为堆
- 单结点的二叉树是堆；
- 在完全二叉树中所有以叶子结点（序号 i> n/2）为根的子树是堆。
这样，我们只需依次将以序号为n/2，n/2-1,……，1的结点为根的子树均调整为堆即可。即：对应由n个元素组成的无序序列，“筛选”只需从第n/2个元素开始。
由于堆实质上是一个线性表，那么我们可以顺序存储一个堆
②输出堆顶元素到顺序表
③重复调整，输出
如何在输出堆顶元素后，调整剩余元素为一个新的堆？
以小根堆为例：
①输出堆顶元素之后，以堆中最后一个元素替代之；
②然后将根结点值与左，右子树的根结点值进行比较，并与其中小者进行交换；
③重复上诉操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为筛选。
可以看出：
对一个无序序列反复筛选就可以得到一个堆；即从一个无序序列建堆的过程就是一个反复筛选的过程。
下面以一个实例介绍建一个小根堆的过程：
由以上分析知：
若对一个无序序列建成堆，然后输出根；重复该过程就可以由一个无序序列输出有序序列。实质上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。
【算法实现】
//建立大根堆算法
void BuildMaxHeap(ElemType A[], int len){
for(int i=len/2; i>0; i--){ //从i=[n/2]~1，反复调整堆
HeadAdjust(A, i, len);
}
}
/*函数HeadAdjust将元素k为根的子树进行调整，使之成为一个大根堆*/
void HeadAdjust(ElemType A[], int k, int len){
A[0] = A[k]; //A[0]暂存子树的根节点
for(i=2*k; i<=len; i*=2){ //沿key较大的子结点向下筛选
if(i<len && A[i]<A[i+1]){ //i为key较大的记录的下标
i++; //取key较大的子节点的下标
}
if(A[0] >= A[i]){
break; //筛选结束
}else{
A[k] = A[i]; //将A[i]调整到双亲结点上
k = i; //修改k值，以便继续向下筛选
}
}
A[k] = A[0]; //被筛选结点的值放入最终位置
}
调整的时间与树高有关，为O ( h )。在建含n个元素的堆时，关键字的比较总次数不超过 4n，时间复杂度为 O(n)，这说明可以在线性时间内将一个无序数组建成一个堆。
下面是堆排序算法：
//堆排序算法如下：
void HeapSort(elem R[]){ //对R[1]到R[n]进行堆排序
int i;
//从第一个非叶子结点来建初始堆，然后将堆顶放在最后一个元素
for(i=n/2; i>=1; i--)
HeapAdjust(R,i,n); //建初始堆
//重新调整堆
for(i=n; i>1; i--){ //进行n-1趟排序
Swap(R[1],R[i]); //根与最后一个元素交换
HeapAdjust(R,1,i-1); //对R[1]到R[i-1]重新建堆
}
}
同时，堆也支持插入操作
对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作。大根堆的插入操作示例如下图所示：
【性能分析】
- 时间复杂度：
- 初始化堆所需时间不超过O(n)
- 排序阶段（不含初始堆化）
- 一次重新堆化所需时间不超过O(log n)
- n-1次循环所需时间不超过O(nlog n)
- 平均时间复杂度Tw(n)=O(nlog n)=O(nlog n)
堆排序的时间主要耗费在建初始堆时进行的反复筛选上。建堆时间为O ( n ) ，之后有n − 1次向下调整操作，每次调整的时间复杂度为O ( h )，故在最好、最坏和平均情况下，堆排序的时间复杂度为O(nlog_2 n)。
-
空间复杂度：O(1)（仅用了一个记录大小交换用的辅助存储空间）
-
稳定性：进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法。
-
适用性：堆排序适合关键字较多的情况(如n>1000)。例如，在1亿个数中选出前100个最大值？首先使用一个大小为100的数组，读入前100个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中100个数即为所求。
三.交换排序
两两比较，如果发生逆序则交换，直到所有记录都排好序为止。
3.1冒泡排序
在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序。——基于简单的交换思想
如下图所示，n趟需要比较n-1趟，第m趟需要比较n-m次：
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；
那么，如何提高效率呢？
一旦某一趟比较时不出现记录交换，就说明已经排好序了，就可以结束本算法。所以在算法中我们可以用一个flag来作为本趟冒泡是否发生交换的标志。
【算法思想】
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
【算法实现】
void BubbleSort(SqList *L){//冒泡排序算法
int i, j, m;
bool flag = true; //交换时的临时存储，表示本趟冒泡是否发生交换的标志
for(m=0; m< L->length-1 && flag==true; m++){ //总共需m趟
flag = false;
for(j=1; j<=L->length-m; j++){ //一趟冒泡过程
if(L.r[j].key > L.r[j+1].key){ //若为逆序
x=L.r[j];
L.r[j]=L.r[j+1];
L.r[j+1]=x; //交换
flag = true; //发生交换，flag置为1，若本趟没发生交换，flag保持为0
}
}
if(flag == false){
return; //本趟遍历后没有发生交换，说明表已经有序,下一趟循环不会被执行
}
}
}
【性能分析】
-
时间复杂度
- 最好的时间复杂度是O(n)
- 最坏的时间复杂度是O(n2)
- 平均时间复杂度是O(n2)
-
空间复杂度：O(1)（仅用了常数个辅助单元）
-
稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
3.2快速排序
这里是排序算法的重点了，非常重要！
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
【特点】
- 从待排序区间任选一个数，作为基准值(pivot)；
- Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；
- 采用分治递归思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1（每个小区间的元素只剩一个），代表已经有序， 或者小区间的长度 == 0，代表没有数据。
【算法思想】
①每一趟的子表形成是采用从两头向中间交替式逼近法，直到low=high停止，可以划分为两个子表：一开始把中间元素放到哨兵位置，后面就空了，于是从前面low位置搬一个（大于哨兵的）到high位置，此时low位置空了，再去high搬一个到low位置…
②由于每趟中对各子表的操作都相似，可采用递归算法
【算法实现】
void main(){
QSort(L,1,L.length);
}
//对顺序表L快速排序
void QSort(SqList &L,int low,int high){ //初始时，low=1,high=length
//接下来依次划分：
if(low<high){ //长度大于1
pivotloc = Partition(L,low,high); //先找到中心点元素的位置
//将L.r[low...high]一分为二为两个子表，pivotloc为基准值排好序的位置
QSort(L,low,pivotloc-1); //对低子表递归排序
QSort(L,pivptloc=1，high); //对高子表递归排序
}
}
//找中心点的位置
int Partition(SqList &L,int low,int high){
L.r[0]=L.r[low];//先将第一个元素放到哨兵位置
pivotkey=L.r[low].key;//并作为基准值
while(low<high){//当loe和high重合停止循环
while(low<high && L.r[high].key >=pivotkey) --high;
L.r[low]=L.r[high];//low位置空了，找一个满足条件的high放到low位置去
while(low<high && L.r[low].key<=pivotkey) ++low;
L.r[high]=L.r[low];//high位置空了，找一个满足条件的low放到low位置去
}
L.r[low]=L.r[0];//这时将哨兵即中心点元素放到low与high重合的位置
return low;//返回中心点所在位置
}
【性能分析】