排序
- 1、排序的基本概念
- 2、插入排序
- ①.直接插入排序
- ②.折半插入排序
- ③.希尔排序
- 3、交换排序
- ①.冒泡排序
- ②.快速排序
- 4、选择排序
- ①.简单选择排序
- ②.树形选择排序
- ③.堆排序
- 5、归并排序
- 6、基数排序
- 7、总结
- 8、例题与应用
1、排序的基本概念
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序的目的是为了便于查找。
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序;
反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，必须访问外存，则称此类排序问题为外部排序。
内部排序方法的分类
-
插入排序(直接插入、折半插入、希尔排序)
将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。 -
交换排序(冒泡排序、快速排序)
通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。 -
选择排序(简单选择、树形选择、堆排序)
从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。 -
归并排序
通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。 -
基数排序
不需要进行关键字之间的比较，依据“多关键字”排序的思想，借助“分配”和“收集”两种操作，对单逻辑关键字进行排序的方法。
待排序记录的存储方式：顺序表、链表、地址向量
排序算法效率的评价指标
- 时间效率——排序速度（比较次数与移动次数)
- 空间效率——占内存辅助空间的大小
- 稳定性——A和B的关键字相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。
2、插入排序
插人排序的基本思想是:每一趟将一个待排序的记录，按其关键字的大小插人到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插人为止。
①.直接插入排序
直接插入排序(Straight Insertion Sort)是一种最简单的排序方法，其基本操作是将―条记录插入到已排好序的有序表，从而得到一个新的、记录数量增1的有序表。
直接插入排序算法步骤：
- 设待排序的记录存放在数组r[1…n]中，r[1]是一个有序序列。
- 循环n -1次，每次使用顺序查找法，查找r[i](i=2,…,n）在已排好序的序列r[1…i-1]中的插入位置，然后将r[i]插人表长为i-1的有序序列r[1…i-1]，直到将r[n]插入表长为n-1的有序序列r[1…n-1]，最后得到一个表长为n的有序序列。
//直接插入排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{int key;char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{ElemType *r; //存储空间的基地址int length; //顺序表长度
}SqList; //顺序表类型void InsertSort(SqList &L)
{//对顺序表L做直接插入排序int i,j;for(i=2;i<=L.length;++i)if(L.r[i].key<L.r[i-1].key){ //"<"，需将r[i]插入有序子表L.r[0]=L.r[i]; //将待插入的记录暂存到监视哨中L.r[i]=L.r[i-1]; //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]; //将r[0]即原r[i]，插入到正确位置} //if
} //InsertSortvoid Create_Sq(SqList &L)
{int i,n;cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;cin>>n; //输入个数cout<<"请输入待排序的数据:\n";while(n>MAXSIZE){cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;cin>>n;}for(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}
void show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<endl;
}void main()
{SqList L;L.r=new ElemType[MAXSIZE+1];L.length=0;Create_Sq(L);InsertSort(L);cout<<"排序后的结果为："<<endl;show(L);
}
例：已知待排序记录的关键字序列为{49,38,65,97,76,13,27,49 }，用直接插入排序法进行排序的过程。
直接插入排序特点：
- 稳定排序。
- 算法简便，且容易实现。
- 也适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针。
- 更适合于初始记录基本有序（正序)的情况，当初始记录无序，n较大时，此算法时间复杂度较高，不宜采用。
②.折半插入排序
折半插入排序算法步骤：
- 设待排序的记录存放在数组r[1…n]中，r[1]是一个有序序列。
- 循环n-1次，每次使用折半查找法，查找ri在已排好序的序列r[1…i-1]中的插入位置，然后将r[i插入表长为i-1的有序序列r[1…i-1]，直到将r[n]插入表长为n-l的有序序列r[
1…n-1]，最后得到一个表长为n的有序序列。
//折半插入排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{int key;char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{ElemType *r; //存储空间的基地址int length; //顺序表长度
}SqList; //顺序表void BInsertSort(SqList &L){//对顺序表L做折半插入排序int i,j,low,high,m;for(i=2;i<=L.length;++i){L.r[0]=L.r[i]; //将待插入的记录暂存到监视哨中low=1; high=i-1; //置查找区间初值while(low<=high){ //在r[low..high]中折半查找插入的位置m=(low+high)/2; //折半if(L.r[0].key<L.r[m].key) high=m-1; //插入点在前一子表else low=m+1; //插入点在后一子表}//whilefor(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; //记录后移L.r[high+1]=L.r[0]; //将r[0]即原r[i]，插入到正确位置} //for
} //BInsertSortvoid Create_Sq(SqList &L)
{int i,n;cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;cin>>n; //输入个数cout<<"请输入待排序的数据：\n";while(n>MAXSIZE){cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;cin>>n;}for(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}void show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<endl;
}void main()
{SqList L;L.r=new ElemType[MAXSIZE+1];L.length=0;Create_Sq(L);BInsertSort(L);cout<<"排序后的结果为："<<endl;show(L);
}
折半插入排序特点：
- 稳定排序。
- 因为要进行折半查找，所以只能用于顺序结构，不能用于链式结构。
- 适合初始记录无序、n较大时的情况。
③.希尔排序
希尔排序：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
//希尔排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{int key;char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{ElemType *r; //存储空间的基地址int length; //顺序表长度
}SqList; //顺序表类型void ShellInsert(SqList &L,int dk)
{//对顺序表L做一趟增量是dk的希尔插入排序int i,j;for(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]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[0]即原r[i]，插入到正确位置} //for
}//ShellInsert
void ShellSort(SqList &L,int dt[ ],int t){//按增量序列dt[0..t-1]对顺序表L作t趟希尔排序int k;for(k=0;k<t;++k)ShellInsert(L,dt[k]); //一趟增量为dt[t]的希尔插入排序
} //ShellSortvoid Create_Sq(SqList &L)
{int i,n;cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;cin>>n; //输入个数cout<<"请输入待排序的数据：\n";while(n>MAXSIZE){cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;cin>>n;}for(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}void show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<endl;
}void main()
{SqList L;L.r=new ElemType[MAXSIZE+1];L.length=0;Create_Sq(L);int i,t;//增量数组的长度int *dt=new int[MAXSIZE];//增量数组cout<<"请输入增量个数：\n";cin>>t;for(i=0;i<t;i++){cout<<"第"<<i+1<<"个增量:\n";cin>>dt[i];}ShellSort(L,dt,t);cout<<"排序后的结果为："<<endl;show(L);
}
希尔排序特点：
- 记录跳跃式地移动导致排序方法是不稳定的。
- 只能用于顺序结构，不能用于链式结构。
- 增量序列可以有各种取法，但应该使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1。
- 记录总的比较次数和移动次数都比直接插人排序要少，n越大时，效果越明显。所以适合初始记录无序、n较大时的情况。
3、交换排序
交换排序的基本思想是:两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换，直到整个序列全部满足要求为止。
①.冒泡排序
冒泡排序(Bubble Sort)是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐往上“漂浮”(左移)，或者使关键字大的记录如石块一样逐渐向下“坠落”(右移)。
冒泡排序算法步骤：
- 设待排序的记录存放在数组r[1…n]中。首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即 L.r[1].key>L.r[2].key)，则交换两个记录。然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。
- 然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。
- 重复上述比较和交换过程,第i趟是从L.r[1]到L.r[n-i+l]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。直到在某一趟排序过程中没有进行过交换记录的操作,说明序列已全部达到排序要求，则完成排序。
//冒泡排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{int key;char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{ElemType *r; //存储空间的基地址int length; //顺序表长度
}SqList; //顺序表类型void BubbleSort(SqList &L)
{//对顺序表L做冒泡排序int m,j,flag;ElemType t;m=L.length-1; flag=1; //flag用来标记某一趟排序是否发生交换while((m>0)&&(flag==1)){flag=0; //flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序for(j=1;j<=m;j++)if(L.r[j].key>L.r[j+1].key) {flag=1; //flag置为1，表示本趟排序发生了交换t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t; //交换前后两个记录} //if--m;} //while
} //BubbleSortvoid Create_Sq(SqList &L)
{int i,n;cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;cin>>n; //输入个数cout<<"请输入待排序的数据:\n";while(n>MAXSIZE){cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;cin>>n;}for(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}void show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<endl;
}void main()
{SqList L;L.r=new ElemType[MAXSIZE+1];L.length=0;Create_Sq(L);BubbleSort(L);cout<<"排序后的结果为："<<endl;show(L);
}
例：
冒泡排序特点：
- 稳定排序。
- 可用于链式存储结构。
- 移动记录次数较多，算法平均时间性能比直接插人排序差。当初始记录无序，n较大时,此算法不宜采用。
②.快速排序
快速排序（ Quick Sort〉是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻)记录的一次交换，消除多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。
快速排序算法步骤：
- 选择待排序表中的第一个记录作为枢轴,将枢轴记录暂存在r[0]的位置上.附设两个指针 low和high，初始时分别指向表的下界和上界（第一趟时，low= 1; high= L.length; ).
- 从表的最右侧位置依次向左搜索，找到第一个关键字小于枢轴关键字pivotkey 的记录,将其移到low处。具体操作是:当low<high时，若high所指记录的关键字大于等于pivotkey，则向左移动指针high(执行操作–high);否则将high所指记录移到low所指记录。
- 然后再从表的最左侧位置,依次向右搜索找到第一个关键字大于pivotkey的记录和枢轴记录交换。具体操作是:当low<high时，若low所指记录的关键字小于等于pivotkey，则向右移动指针low(执行操作++low);否则将low所指记录与枢轴记录交换。
- 重复步骤②和③，直至 low与high相等为止。此时low或high 的位置即为枢轴在此趟排序中的最终位置，原表被分成两个子表。
在上述过程中，记录的交换都是与枢轴之间发生，每次交换都要移动3次记录，可以先将枢轴记录暂存在r[0]的位置上，排序过程中只移动要与枢轴交换的记录，即只做r[low]或r[high]的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。
//快速排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{int key;char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{ElemType *r; //存储空间的基地址int length; //顺序表长度
}SqList; //顺序表类型int Partition(SqList &L,int low,int high)
{ //对顺序表L中的子表r[low..high]进行一趟排序，返回枢轴位置int pivotkey;L.r[0]=L.r[low]; //用子表的第一个记录做枢轴记录pivotkey=L.r[low].key; //枢轴记录关键字保存在pivotkey中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]; //将比枢轴记录大的记录移到高端}//whileL.r[low]=L.r[0]; //枢轴记录到位return low; //返回枢轴位置
}//Partitionvoid QSort(SqList &L,int low,int high)
{ //调用前置初值：low=1; high=L.length;//对顺序表L中的子序列L.r[low..high]做快速排序int pivotloc;if(low<high){ //长度大于1pivotloc=Partition(L,low,high); //将L.r[low..high]一分为二，pivotloc是枢轴位置QSort(L,low,pivotloc-1); //对左子表递归排序QSort(L,pivotloc+1,high); //对右子表递归排序}
} //QSortvoid QuickSort(SqList &L)
{//对顺序表L做快速排序QSort(L,1,L.length);
} //QuickSortvoid Create_Sq(SqList &L)
{int i,n;cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;cin>>n; //输入个数cout<<"请输入待排序的数据:\n";while(n>MAXSIZE){cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;cin>>n;}for(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}void show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<endl;
}int main(void)
{SqList L;L.r=new ElemType[MAXSIZE+1];L.length=0;Create_Sq(L);QuickSort(L);cout<<"排序后的结果为："<<endl;show(L);
}
例：已知待排序记录的关键字序列为{49,38,65,97,76,13,27,49}，用快速排序法进行排序的过程。
例：
快速排序特点：
- 记录非顺次的移动导致排序方法是不稳定的。
- 排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用于链式结构。
- 当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序、n较大时的情况。
4、选择排序
选择排序的基本思想是:每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已排序的记录序列的最后，直到全部排完为止。
①.简单选择排序
简单选择排序也称作直接选择排序
简单选择排序算法步骤：
- 设待排序的记录存放在数组r[l…n]中。第一趟从r[1]开始，通过n-1次比较，从n个记录中选出关键字最小的记录，记为r[k，交换r[1]和r[k]。
- 第二趟从r[2]开始,通过n-2次比较,从n-l个记录中选出关键字最小的记录，记为r[k],交换r[2]和r[k]。
- 依次类推，第i趟从r[i]开始，通过n-i次比较，从n-i+tl个记录中选出关键字最小的记录，记为r[k]，交换r[i]和r[k]。
- 经过n-1趟，排序完成。
//简单选择排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{int key;char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{ElemType *r; //存储空间的基地址int length; //顺序表长度
}SqList; //顺序表类型void SelectSort(SqList &L)
{ //对顺序表L做简单选择排序int i,j,k;ElemType t;for(i=1;i<L.length;++i) { //在L.r[i..L.length] 中选择关键字最小的记录k=i; for(j=i+1;j<=L.length;++j)if(L.r[j].key<L.r[k].key) k=j; //k指向此趟排序中关键字最小的记录if(k!=i) {t=L.r[i];L.r[i]=L.r[k];L.r[k]=t;} //交换r[i]与r[k] } //for
} // SelectSortvoid Create_Sq(SqList &L)
{int i,n;cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;cin>>n; //输入个数cout<<"请输入待排序的数据:\n";while(n>MAXSIZE){cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;cin>>n;}for(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}void show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<endl;
}void main()
{SqList L;L.r=new ElemType[MAXSIZE+1];L.length=0;Create_Sq(L);SelectSort(L);cout<<"排序后的结果为："<<endl;show(L);
}
例：已知待排序记录的关键字序列为{ 49,38,65,97,49,13,27,76}，给出用简单选择排序法进行排序的过程。
简单选择排序特点：
- 就选择排序方法本身来讲，它是一种稳定的排序方法，但例子所表现出来的现象是不稳定的，这是因为上述实现选择排序的算法采用“交换记录”的策略所造成的，改变这个策略，可以写出不产生“不稳定现象”的选择排序算法。
- 可用于链式存储结构。
- 移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插人排序快。
②.树形选择排序
树形选择排序(Tree Selection Sort):又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。借助有n个叶子结点的完全二叉树，两两比较选最小。这个过程可用一颗有n个叶子结点的完全二叉树表示。
③.堆排序
堆排序（Heap Sort）是一种树形选择排序，在排序过程中，将待排序的记录r[1…n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大（或最小)的记录。
堆的定义：
n个元素的序列{k1,k2,…,kn}称之为堆，当且仅当满足以下条件时:
- ki≥k2i且ki≥k2i+1(大顶堆)
- 或ki≤k2i且 ki≤k2i+1(小顶堆)
若将和此序列对应的一维数组(即以一维数组做此序列的存储结构)看成是一个完全二叉树，则堆实质上是满足如下性质的完全二叉树:树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。
- 按堆的定义将待排序序列r[ 1…n]调整为大根堆（这个过程称为建初堆)，交换r[1]和r[n],则r[n]为关键字最大的记录。
- 将r[ 1…n-1]重新调整为堆,交换r[1]和r[n-1]，则r[n-1]为关键字次大的记录。
- 循环n-1次，直到交换了r[1]和r[2]为止，得到了一个非递减的有序序列r[ 1…n]。
调整堆
先看一个例子，图（ a)是个堆，将堆顶元素97和堆中最后–个元素38交换后，如图( b)所示。由于此时除根结点外，其余结点均满足堆的性质，由此仅需自上至下进行一条路径上的结点调整即可。首先以堆顶元素38和其左、右子树根结点的值进行比较，由于左子树根结点的值大于右子树根结点的值且大于根结点的值，则将38和76交换;由于38替代了76之后破坏了左子树的“堆”，则需进行和上述相同的调整，直至叶子结点，调整后的状态如图( c )所示。重复上述过程，将堆顶元素76和堆中最后一个元素27交换且调整，得到如图( d）所示新的堆。
上述过程就像过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，称此方法为“筛选法”。
筛选法调整堆：
从r[2s]和r[2s+I]中选出关键字较大者，假设r[2s]的关键字较大，比较r[s]和r[2s]的关键字。
- 若r[s].key> =r[2s].key，说明以r[s]为根的子树已经是堆，不必做任何调整。
- 若r[s].key<r[2s].key，交换r[s]和r[2s]。交换后，以r[2s+I]为根的子树仍是堆,如果以r[2s]为根的子树不是堆，则重复上述过程，将以r[2s]为根的子树调整为堆，直至进行到叶子结点为止。
//筛选法调整堆
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{int key;char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{ElemType *r; //存储空间的基地址int length; //顺序表长度
}SqList; //顺序表类型void HeapAdjust(SqList &L,int s,int m)
{ //假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大根堆ElemType rc;int j;rc=L.r[s];for(j=2*s;j<=m;j*=2){ //沿key较大的孩子结点向下筛选if(j<m&&L.r[j].key<L.r[j+1].key) ++j; //j为key较大的记录的下标if(rc.key>=L.r[j].key) break; //rc应插入在位置s上L.r[s]=L.r[j]; s=j; }L.r[s]=rc; //插入
} //HeapAdjustvoid Create_Sq(SqList &L)
{int i,n;cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;cin>>n; //输入个数cout<<"请输入待调整的数据:\n";while(n>MAXSIZE){cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;cin>>n;}for(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}
void show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<endl;
}
void main()
{SqList L;L.r=new ElemType[MAXSIZE+1];L.length=0;Create_Sq(L);HeapAdjust(L,1,L.length);cout<<"调整后的结果为："<<endl;show(L);
}
建初堆
要将一个无序序列调整为堆，就必须将其所对应的完全二叉树中以每一结点为根的子树都调整为堆。显然，只有一个结点的树必是堆，而在完全二叉树中，所有序号大于[n/2]的结点都是叶子,因此以这些结点为根的子树均已是堆。这样，只需利用筛选法,从最后一个分支结点|n/2]开始，依次将序号为|n/2]、[n/2]-1…、1的结点作为根的子树都调整为堆即可。
对于无序序列r[1…n]，从i=n/2开始，反复调用筛选法HeapAdjust (L,in)，依次将以r团],r[i-1],…,r[1]为根的子树调整为堆。
//建初堆
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{int key;char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{ElemType *r; //存储空间的基地址int length; //顺序表长度
}SqList; //顺序表类型//用算法8.7 筛选法调整堆
void HeapAdjust(SqList &L,int s,int m)
{ //假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大根堆ElemType rc;int j;rc=L.r[s];for(j=2*s;j<=m;j*=2){ //沿key较大的孩子结点向下筛选if(j<m&&L.r[j].key<L.r[j+1].key) ++j; //j为key较大的记录的下标if(rc.key>=L.r[j].key) break; //rc应插入在位置s上L.r[s]=L.r[j]; s=j; }L.r[s]=rc; //插入
} //HeapAdjustvoid Create_Sq(SqList &L)
{int i,n;cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;cin>>n; //输入个数cout<<"请输入数据:\n";while(n>MAXSIZE){cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;cin>>n;}for(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}void CreatHeap(SqList &L)
{//把无序序列L.r[1..n]建成大根堆int i,n;n=L.length;for(i=n/2;i>0;--i) //反复调用HeapAdjust HeapAdjust(L,i,n);
} //CreatHeap
void show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<endl;
}void main()
{SqList L;L.r=new ElemType[MAXSIZE+1];L.length=0;Create_Sq(L);CreatHeap(L);cout<<"建立成堆的序列为："<<endl;show(L);
}
例：
已知无序序列为{49,38,65,97,76,13,27,49}，用“筛选法”将其调整为一个大根堆,给出建堆的过程。
堆排序算法的实现：
//排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{int key;char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{ElemType *r; //存储空间的基地址int length; //顺序表长度
}SqList; //顺序表类型//用算法8.7 筛选法调整堆
void HeapAdjust(SqList &L,int s,int m)
{ //假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大根堆ElemType rc;int j;rc=L.r[s];for(j=2*s;j<=m;j*=2){ //沿key较大的孩子结点向下筛选if(j<m&&L.r[j].key<L.r[j+1].key) ++j; //j为key较大的记录的下标if(rc.key>=L.r[j].key) break; //rc应插入在位置s上L.r[s]=L.r[j]; s=j; }L.r[s]=rc; //插入
}//HeapAdjust
void Create_Sq(SqList &L)
{int i,n;cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;cin>>n; //输入个数cout<<"请输入待排序的数据:\n";while(n>MAXSIZE){cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;cin>>n;}for(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}//用算法8.8 建初堆
void CreatHeap(SqList &L)
{//把无序序列L.r[1..n]建成大根堆int i,n;n=L.length;for(i=n/2;i>0;--i) //反复调用HeapAdjust HeapAdjust(L,i,n);
} //CreatHeapvoid HeapSort(SqList &L)
{ //对顺序表L进行堆排序 int i;ElemType x;CreatHeap(L); //把无序序列L.r[1..L.length]建成大根堆 for(i=L.length;i>1;--i){ x=L.r[1]; //将堆顶记录和当前未经排序子序列L.r[1..i]中最后一个记录互换 L.r[1]=L.r[i]; L.r[i]=x; HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大根堆 }//for
}//HeapSort
void show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<endl;
}
void main()
{SqList L;L.r=new ElemType[MAXSIZE+1];L.length=0;Create_Sq(L);HeapSort(L);cout<<"排序后的结果为："<<endl;show(L);
}
例：对建好的大根堆进行排序
堆排序特点：
- 是不稳定排序。
- 只能用于顺序结构，不能用于链式结构。
- 初始建堆所需的比较次数较多，因此记录数较少时不宜采用。堆排序在最坏情况下时间复杂度为O(nlog2n)，相对于快速排序最坏情况下的O(n2)而言是一个优点，当记录较多时较为高效。
5、归并排序
归并排序(Merging Sort)就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为⒉-路归并，2-路归并最为简单和常用。下面以2-路归并为例，介绍归并排序算法。
归并排序算法的思想是:
假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到⌈n/2⌉ 个长度为2或1的有序子序列;再两两归并，……，如此重复、直至得到一个长度为n的有序序列为止。
归并排序算法步骤：
2-路归并排序将R[low…high]中的记录归并排序后放入T[low.high]中。当序列长度等于1时，递归结束，否则:
- 将当前序列一分为二，求出分裂点mid =⌊(low+high)/2⌋;
- 对子序列R[low…mid]递归，进行归并排序，结果放入S[low…mid]中;
- 对子序列R[mid + 1…high]递归，进行归并排序，结果放入S[mid + 1…high]中;
- 调用算法Merge，将有序的两个子序列S[low…mid]和 S[mid +1…high]归并为一个有序的序列T[low…high]。
//归并排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{int key;char *otherinfo;
}RedType;typedef struct
{RedType *r;int length;
}SqList;void Create_Sq(SqList &L)
{int i,n;cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;cin>>n; //输入个数cout<<"请输入待排序的数据:\n";while(n>MAXSIZE){cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;cin>>n;}for(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}//相邻两个有序子序列的归并
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{ //将有序表R[low..mid]和R[mid+1..high]归并为有序表T[low..high] int i,j,k;i=low; j=mid+1;k=low; while(i<=mid&&j<=high){ //将R中记录由小到大地并入T中 if(R[i].key<=R[j].key) T[k++]=R[i++]; else T[k++]=R[j++]; } while(i<=mid) //将剩余的R[low..mid]复制到T中 T[k++]=R[i++]; while(j<=high) //将剩余的R[j.high]复制到T中 T[k++]=R[j++];
}//Merge void MSort(RedType R[],RedType T[],int low,int high)
{ //R[low..high]归并排序后放入T[low..high]中 int mid;RedType *S=new RedType[MAXSIZE];if(low==high) T[low]=R[low]; else{ mid=(low+high)/2; //将当前序列一分为二，求出分裂点mid MSort(R,S,low,mid); //对子序列R[low..mid] 递归归并排序，结果放入S[low..mid] MSort(R,S,mid+1,high); //对子序列R[mid+1..high] 递归归并排序，结果放入S[mid+1..high] Merge(S,T,low,mid,high); //将S[low..mid]和S [mid+1..high]归并到T[low..high] }//else
}// MSort void MergeSort(SqList &L)
{ //对顺序表L做归并排序 MSort(L.r,L.r,1,L.length);
}//MergeSort
void show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<endl;
}
void main()
{SqList R;R.r=new RedType[MAXSIZE+1];R.length=0;Create_Sq(R);MergeSort(R);cout<<"排序后的结果为："<<endl;show(R);
}
例：已知待排序记录的关键字序列为{49,38,65,97,76,13,27}，给出用2-路归并排序法进行排序的过程。
归并排序特点：
- 是稳定排序。
- 可用于链式结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。
6、基数排序
借助多关键字排序的思想对单逻辑关键字进行排序。即:用关键字不同的位值进行排序。
“多关键字”排序
例:对一副扑克牌该如何排序?
若规定花色和面值的顺序关系为:
花色:
面值:2<3<4<5<6<7<8<9<10<J<Q<K<A
则可以先按花色排序，花色相同者再按面值排序;也可以先按面值排序，面值相同者再按花色排序。
多关键字排序的实现方法通常有两种:
最高位优先法MSD (Most Significant Digit first)
最低位优先法LSD (Least Significant Digit first)
//基数排序
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAXNUM_KEY 8 //关键字项数的最大值
#define RADIX 10 //关键字基数，此时是十进制整数的基数
#define MAX_SPACE 10000
typedef char KeysType; //定义关键字类型为字符型
typedef int InfoType; //定义其它数据项的类型
typedef struct
{ KeysType keys[MAXNUM_KEY]; //关键字 InfoType otheritems; //其他数据项 int next;
}SLCell; //静态链表的结点类型
typedef struct
{ SLCell r[MAX_SPACE]; //静态链表的可利用空间，r[0]为头结点 int keynum; //记录的当前关键字个数 int recnum; //静态链表的当前长度
}SLList; //静态链表类型
typedef int ArrType[RADIX]; //指针数组类型void InitList(SLList *L)
{ //初始化静态链表L（把数组D中的数据存于L中）char c[MAXNUM_KEY],c1[MAXNUM_KEY];int i,j,n,max; //max为关键字的最大值 max=-10000;cout<<"请输入数据个数，不超过"<<MAX_SPACE<<"个。\n";cin>>n;while(n>MAX_SPACE){cout<<"您输入的个数超过上限，请重新输入，不超过"<<MAX_SPACE<<"个。\n";cin>>n;}int *D=new int[n];cout<<"请输入"<<n<<"个排排序的数据：\n";for(i=0;i<n;i++){cin>>D[i];if(max<D[i])max=D[i];}(*L).keynum=(int)(ceil(log10(max)));(*L).recnum=n;for(i=1;i<=n;i++){itoa(D[i-1],c,10); //将10进制整型转化为字符型,存入c for(j=strlen(c);j<(*L).keynum;j++) //若c的长度<max的位数,在c前补'0' {strcpy(c1,"0");strcat(c1,c);strcpy(c,c1);}for(j=0;j<(*L).keynum;j++)(*L).r[i].keys[j]=c[(*L).keynum-1-j];}
}int ord(char c)
{ //返回k的映射(个位整数)return c-'0';
}
void Distribute(SLCell *r,int i,ArrType &f,ArrType &e)
{ //静态链表L的r域中记录已按（keys[0], …, keys[i-1]）有序 //本算法按第i个关键字keys[i]建立RADIX个子表，使同一子表中记录的keys[i]相同。 //f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录int j,p;for(j=0;j<RADIX;++j) f[j]=0; //各子表初始化为空表 for(p=r[0].next;p;p=r[p].next){ j=ord(r[p].keys[i]); //ord将记录中第i个关键字映射到[0..RADIX-1] if(!f[j]) f[j]=p; else r[e[j]].next=p; e[j]=p; //将p所指的结点插入第j个子表中 }//for
}//Distribute int succ(int i)
{ //求后继函数return ++i;
}
void Collect (SLCell *r,int i,ArrType &f,ArrType &e)
{ //本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成一个链表 //e[0..RADIX-1]为各子表的尾指针int j,t;for(j=0;!f[j];j=succ(j)); //找第一个非空子表，succ为求后继函数 r[0].next=f[j];t=e[j]; //r[0].next指向第一个非空子表中第一个结点 while(j<RADIX-1){ for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j)) ; //找下一个非空子表 if(f[j]) {r[t].next=f[j];t=e[j];} //链接两个非空子表 }//while r[t].next=0; //t指向最后一个非空子表中的最后一个结点
}//Collect void RadixSort(SLList &L)
{ //L是采用静态链表表示的顺序表 //对L做基数排序，使得L成为按关键字自小到大的有序静态链表，L.r[0]为头结点int i;ArrType f,e;for(i=0;i<L.recnum;++i) L.r[i].next=i+1; L.r[L.recnum].next = 0; //将L改造为静态链表 for(i=0;i<L.keynum;++i) { //按最低位优先依次对各关键字进行分配和收集 Distribute(L.r,i,f,e); //第i趟分配 Collect(L.r,i,f,e); //第i趟收集 }//for
} // RadixSortvoid print(SLList L)
{ //按数组序号输出静态链表int i,j;for(i=1;i<=L.recnum;i++){for(j=L.keynum-1;j>=0;j--)cout<<L.r[i].keys[j];cout<<endl;}
}
void Sort(SLList L,int adr[])
{ //求得adr[1..L.length]，adr[i]为静态链表L的第i个最小记录的序号int i=1,p=L.r[0].next;while(p){adr[i++]=p;p=L.r[p].next;}
}
void Rearrange(SLList *L,int adr[])
{ //adr给出静态链表L的有序次序，即L.r[adr[i]]是第i小的记录。//本算法按adr重排L.r，使其有序。算法10.18(L的类型有变) int i,j,k;if(adr[i]!=i){j=i;(*L).r[0]=(*L).r[i]; //暂存记录(*L).r[i]while(adr[j]!=i){ //调整(*L).r[adr[j]]的记录到位直到adr[j]=i为止k=adr[j];(*L).r[j]=(*L).r[k];adr[j]=j;j=k; //记录按序到位 }(*L).r[j]=(*L).r[0];adr[j]=j;}
}void main()
{SLList l;int *adr;InitList(&l);RadixSort(l);adr=new int[l.recnum];Sort(l,adr);Rearrange(&l,adr);cout<<"排序后(重排记录):\n";print(l);
}
7、总结
8、例题与应用
实现快速排序
#include<bits/stdc++.h>
using namespace std;typedef struct
{int key;char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{ElemType *r;int length;
}SqList;
//对顺序表的子表进行一趟排序，返回枢轴位置
int Division(SqList &L,int low,int high)
{ int pivotkey;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[low]=L.r[0];return low;
}
//对顺序表做快速排序
void QSort(SqList &L,int low,int high)
{ int pivotloc;if(low<high){ pivotloc=Division(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high);}
}
//进行快速排序
void QuickSort(SqList &L)
{QSort(L,1,L.length);
}
//输入待排序的数据
void Create_Sq(SqList &L)
{int i,n;cout<<"\t源码实现\t"<<endl;cout<<"请输入待排序的10个数据:\n";for(i=1;i<=10;i++){cin>>L.r[i].key;L.length++;}
}
//输出排序好的数据
void Show(SqList L)
{int i;for(i=1;i<=L.length;i++)cout<<L.r[i].key<<" ";
}int main(void)
{SqList L;L.r=new ElemType[11];L.length=0;Create_Sq(L);QuickSort(L);cout<<"排序后的结果为："<<endl;Show(L);
}
#include<bits/stdc++.h>
using namespace std;int main(void)
{int L[10];int i;cout<<"\tSTL实现\t"<<endl;cout<<"请输入待排序的10个数据:\n";for(i=0;i<10;i++)cin>>L[i];sort(L,L+10);cout<<"排序后的结果为："<<endl;for(i=0;i<10;i++)cout<<L[i]<<" ";return 0;}
