============================================================= 文章中谈及的排序算法包括：冒泡排序；选择排序；插入排序；快速排序； 希尔排序；堆排序；归并排序；基数排序。 注：头文件“array.h”内容是线性表的建立与线性表中元素的输出。线性表 中的元素的输入是从 1 空间开始的，0 空间作为中间变量或者作为暂存单元。每 一个排序算法的程序都包含头文件“array.h” ，运行前需要先生成“array.h”头文 件， 运行时头文件与排序的源文件必须在同一个文件夹下。建议不要在同一个工 作空间同进运行多个排序算法的源文件，否则编译器会报错。 头文件 array.h 的代码---------------------------------------------------------------------------#define N 100 typedef int datatype; typedef struct{//定义线性表结构 datatype elem[N]; int length; }SeqList; void create_array(SeqList *list)//创建线性表 { list->length=0;//初始化 datatype x; printf("*-----输入一组随机数(以结束!)-----*\n\n"); scanf("%d",&x); while(x)//输入线性表元素 { list->length++; list->elem[list->length]=x; scanf("%d",&x); } } void out(SeqList *s)//输出线性表元素 { int i; printf("\n*-----输入的随机数排序结果如下-----*\n\n"); for(i=1;i<=s->length;i++) printf("%5d",s->elem[i]); printf("\n\n"); } 大多数排序算法都有两个基本操作：(1)比较两个关键字的大小；(2)改变指 向记录的指针或移动记录本身。 冒泡排序算法------------------------------------------------------------------------------------(1)从下往上：第 1 趟扫描从记录的 R[1..n]的底部向上依次比较相邻的两个气泡 的重量，若发现轻者在下，重者在上，则交换二者的位置。第 1 趟完毕后， “最 轻” 的气泡就飘浮到该区间的顶部。 2 趟扫描的记录为 R[2..n]， 第 扫描完毕后 “次
轻”的气泡飘浮到 R[2]的位置上。以此类推，直至 R[1..i]变为新的有序区。 #include #include"array.h" /*--------------------------------------------------*/ //从上往下的冒泡排序算法 void sort(SeqList *list) { int i,j; for(i=1;ilength;i++) for(j=1;j<=list->length-i;j++) //从小到大排序 if(list->elem[j]>list->elem[j+1]) {//0空间作为中间变量进行前后交换 list->elem[0]=list->elem[j];// list->elem[j]=list->elem[j+1]; list->elem[j+1]=list->elem[0]; } } /*--------------------------------------------------*/ void main()//检测算法的正确性 { SeqList range; create_array(&range); sort(&range); out(&range); } ------------------------------------------------------------------------------------------------------(2)从上往下：第 1 趟扫描从记录的 R[1..n]的顶部向下依次比较相邻的两个气泡 的重量，若发现重者在上，轻者在下，则交换二者的位置。第 1 趟完毕后， “最 重” 的气泡就沉到该区间的底部。 2 趟
扫描的记录为 R[1..n-1]， 第 扫描完毕后 “次 重”的气泡飘浮到 R[n-1]的位置上。以此类推，直至 R[i..n]变为新的有序区。 #include #include"array.h" /*--------------------------------------------------*/ //从下往上的冒泡排序算法 void sort(SeqList *digit) { int i,j; for(i=1;ilength-1;i++) for(j=digit->length;j>i;j--) //从小到大排序 if(digit->elem[j]elem[j-1]) {//0空间作为中间变量进行前后交换 digit->elem[0]=digit->elem[j];
digit->elem[j]=digit->elem[j-1]; digit->elem[j-1]=digit->elem[0]; } } /*--------------------------------------------------*/ //检测算法的正确性 void main() { SeqList range; create_array(&range); sort(&range); out(&range); } 选择排序算法------------------------------------------------------------------------------------第 i 趟排序开始进行， 当前有序区和无序区分别为 R[1..i-1]和 R[i..n](1≤i≤n-1)， 该趟排序则是从当前无序区中选择出关键字最小的记录 R[k]， 将它与无序区的第 1 个记录 R[i]交换，使 R[1..i]和 R[i+1..n]分别变为新的有序区和新的无序区。 #include #include"array.h" /*--------------------------------------------------*/ //选择排序算法 void sort(SeqList *digit) { int i,j,k; for(i=1;ilength;i++) { k=i;//记录下标 for(j=i+1;j<=digit->length;j++) if(digit->elem[k]>digit->elem[j]) k=j;//记录较小值的下标 if(k!=i)//非本身则交换 {//0空间作为中间变量进行交换 digit->elem[0]=digit->elem[k]; digit->elem[k]=digit->elem[i]; digit->elem[i]=digit->elem[0]; } } } /*--------------------------------------------------*/ //检测算法的正确性 void main() { SeqList range;
create_array(&range); sort(&range); out(&range); } 插入排序算法------------------------------------------------------------------------------------每次将一个待排序的记录， 按其关键字大小插入到前面已经排好的子文件中的适 当位置，直到全部记录插入完成为止。 #include #include"array.h" /*--------------------------------------------------*/ //插入排序算法 void sort(SeqList *r) { int i,j; for(i=2;i<=r->length;i++) if(r->elem[i]elem[i-1]) { r->elem[0]=r->elem[i];//置为空间 for(j=i-1;r->elem[0]elem[j];j--) r->elem[j+1]=r->elem[j];//从后往前移位 r->elem[j+1]=r->elem[0];//置为适当位置 } } /*--------------------------------------------------*/ //检测算法的正确性 void main() { SeqList range; create_array(&range); sort(&range); out(&range); } 快速排序算法------------------------------------------------------------------------------------在 R[low..high]中任选择一个记录作为基准，以引基准将当前无序区划分为左或 右两个较小的区间 R[low..pivotpos-1]和 R[pivotpos+1..high]，并使左边子区间中 所有记录的关键字均小于等于基准记录， 右边的子区间中所有记录的关键字均大 于等于基
准记录。通过递归调用快速排序对左、右两个子区间 R[low..pivotpos-1 和 R[pivotpos+1..high]排序。 #include #include"array.h" /*--------------------------------------------------*/ //快速排序算法
int sort(SeqList *t,int low,int high) { t->elem[0]=t->elem[low];//置为空间 while(lowelem[high]>=t->elem[0]) high--;//比空间值大则往前 t->elem[low]=t->elem[high];//比空间值小时传给low while(lowelem[low]<=t->elem[0]) low++;//比空间值小则往后 t->elem[high]=t->elem[low];//比空间值大时传给high } t->elem[low]=t->elem[0]; return low;//返回空间值存放的位置 } void qsort(SeqList *r,int low,int high) { int mid; if(lowd t ? 1( d t ? d t ?1 ... ? d 2 ? d 1 ) ， 即所有的记录放在同一组中进行直接插入排序为止。
#include #include"array.h"
/*--------------------------------------------------*/ //希尔排序算法 void sort(SeqList *R,int d) { int i,j; for(i=d+1;i<=R->length;i++) if(R->elem[i]elem[i-d]) { R->elem[0]=R->elem[i];//R[0]是暂存空间，非哨兵 j=i-d; do//查找R[i]的插入位置 { R->elem[j+d]=R->elem[j];//后移 j=j-d;//查找前一记录 }while(j>0&&R->elem[0]elem[j]); R->elem[j+d]=R->elem[0]; } } void ssort(SeqList *R) { int mark=R->length;//增量初值 do { mark=mark/3+1;//下一增量 sort(R,mark); }while(mark>1); } /*--------------------------------------------------*/ //检测算法的正确性 void main() { SeqList range; create_array(&range); ssort(&range); out(&range); } 堆排序算法---------------------------------------------------------------------------------------将初始文件 R[1..n]建成一个大根堆；将无序区的堆顶记录 R[1]和该区间的最后 一个记录交换，然后将新的无序区调整为大根堆。如此反复，执行 n-1 趟排序得 到有序区 R[1..n]。 #include #include"array.h" /*--------------------------------------------------*/
//堆排序算法 void sort(SeqList *R,int low,int high) {//调整为大根堆 int large;//记录左右孩子的较大者 R->elem[0]=R->elem[low];//调整结点置为空间 for(large=2*low;large<=high;large*=2) { if(largeelem[large]elem[large+1]) large++;//记录当前左
右孩子的较大者 if(R->elem[0]>=R->elem[large]) break;//不大于调整结点则结束 R->elem[low]=R->elem[large]; low=large;//记录新的调整结点 } R->elem[low]=R->elem[0]; } void built(SeqList *R) {//构造大根堆 int i; for(i=R->length/2;i>0;i--) sort(R,i,R->length);//调整为堆 } void hsort(SeqList *R) { int i; built(R);//建立初始堆 for(i=R->length;i>1;i--) {//交换堆顶和最后一个记录 R->elem[0]=R->elem[1]; R->elem[1]=R->elem[i]; R->elem[i]=R->elem[0]; sort(R,1,i-1);//重新调整为堆 } } /*--------------------------------------------------*/ //检测算法的正确性 void main() { SeqList range; create_array(&range); hsort(&range); out(&range); }
归并排序算法------------------------------------------------------------------------------------(1)自底向上：第 1 趟归并排序时，将待排序的文件 R[1..n]看作是 n 个长度为 1 的有序子文件，将这些子文件两两归并，若 n 为偶数，则得到 ? n / 2 ? 个长度为 2 的有序子文件；若 n 为奇数，则最后一个子文件轮空(不参与归并)，因此本趟归 并完后，前 ? n / 2 ? -1 个有序文件长度为 2，但最后一个子文件长度仍为 1；第 2 趟归并则是将第 1 趟归并所得到的 ? n / 2 ? 个有序的子文件两两归并，如此反复， 直到最后得到一个长度为 n 的有序文件为止。 #include #include #include"array.h" /*--------------------------------------------------*/ //归并排序的迭代算法 void sort(SeqList *R,int low,int m,int high) { int i=low,j=m+1,p=0;//初始化 SeqList *T;//局部向量 if(high-low+1>0) T=(SeqList *)malloc(sizeof(SeqList)); while(i<=m&&j<=high)//两子文件非空时取其小者输出到T上 T->elem[p++]=(R->elem[i]<=R->elem[j])?R->elem[i++]:R->elem[j++]; while(i<=m)//第个子文件非空则复制剩余记录到T中 T->elem[p++]=R->elem[i++]; while(j<=high)//第个子文件非空则复制剩余记录到T中 T->elem[p++]=R->elem[j++]; for(p=0,i=low;i<=high;p++,i++) R->elem[i]=T->elem[p];//归并完成后再复制到R中 } void pass(SeqList *R,int n) {//进行一次归并排序 int i; for(i=1;i+2*n-1<=R->length;i=i+2*n) //归并长度为n的两个相邻的子文件 sort(R,i,i+n-1,i+2*n-1); if(i+n-1length;i*=2) pass(R,i);
} /*--------------------------------------------------*/ //检测算法的正确性 void main() { SeqList range; create_array(&range); msort(&range); out(&range); } ------------------------------------------------------------------------------------------------------(2)自顶向下：将当前区间一分为二，求分裂点 mid ? ?( low ? high ) / 2 ? ；递归地对 两个子区间 R[low..mid]和 R[mid+1..high]进行归并排序；将已排序的两个子区间 R[low..mid]和 R[mid+1..high]归并为一个序的区间 R[low..high]。 #include #i
nclude #include"array.h" /*--------------------------------------------------*/ //归并排序的递归算法 void sort(SeqList *R,int low,int m,int high) { int i=low,j=m+1,p=0;//初始化 SeqList *T;//局部向量 if(high-low+1>0) T=(SeqList *)malloc(sizeof(SeqList)); while(i<=m&&j<=high)//两子文件非空时取其小者输出到T上 T->elem[p++]=(R->elem[i]<=R->elem[j])?R->elem[i++]:R->elem[j++]; while(i<=m)//第个子文件非空则复制剩余记录到T中 T->elem[p++]=R->elem[i++]; while(j<=high)//第个子文件非空则复制剩余记录到T中 T->elem[p++]=R->elem[j++]; for(p=0,i=low;i<=high;p++,i++) R->elem[i]=T->elem[p];//归并完成后再复制到R中 } void msort(SeqList *R,int low,int high) {//进行二路归并排序 int mid; if(low } } /*--------------------------------------------------*/ //检测算法的正确性 void main() { SeqList range; create_array(&range); msort(&range,1,range.length); out(&range); } 基数排序算法------------------------------------------------------------------------------------设置若干个箱子，从低位到高位的每位都依次对 K j ( j ? d ? 1, d ? 2 ,..., 0 ) 进行分配 与收集：依次扫描排序的记录 R[0],R[1],…,R[n-1]，把关键字等于 k 的记录全都 装到第 k 个箱子里(分配)，然后按序号依次将各非空的箱子首尾接起来(收集)。 #include #include #define Radix 10 #define KeySize 5//整型变量最高位数 #include"array.h" typedef struct node{//定义队列结点 datatype data; struct node *next; }QueueNode; typedef struct{ QueueNode *front,*rear; }LinkQueue; //初始化链队列 void InitQueue(LinkQueue *s) { s->front=s->rear=NULL; } //判断链队列为空 int EmptyQueue(LinkQueue *s) { if(s->front==NULL) return 1; else return 0; } //入队列 void InQueue(LinkQueue *s,datatype x) {
QueueNode *p;//初始化新的结点 p=(QueueNode *)malloc(sizeof(QueueNode)); p->data=x; p->next=NULL; if(EmptyQueue(s))//新结点插入空队列 s->front=s->rear=p; else//链队列非空则插入队尾 { s->rear->next=p; s->rear=p; } } //出队列 datatype OutQueue(LinkQueue *s) { datatype x; QueueNode *p; if(!EmptyQueue(s)) {//队非空时则出队列 p=s->front; x=p->data; s->front=p->next; if(s->rear==p)//出队列结点为队头 s->rear=NULL; free(p);//删除已出队列的结点 return x; } } /*--------------------------------------------------*/ //基数排序算法 void sort(SeqList *p,LinkQueue R[],int j) { int i,k; j=KeySize-j;//确定关键字从个位起的位数 for(i=1;i<=p->length;i++) {//依次扫描R[i]，将其入队 p->elem[0]=p->elem[i]; for(k=1;kelem[0]=p->elem[0]/10; p->elem[0]=p->elem[0]%10;//取关键字的第j位数字 InQueue(&R[p->elem[0]],p->elem[i]);//将R[i]入队 } } void collect(SeqList *p,LinkQueue R[])
{/
/收集非空链队的记录 int i=1,j; for(j=0;jelem[i++]=OutQueue(&R[j]); } void rsort(SeqList *list) { LinkQueue R[Radix];//10个为链队列的基数 int i; for(i=0;i=0;i--) { sort(list,R,i);//分配 collect(list,R);//收集 } } /*--------------------------------------------------*/ //检测算法的正确性 void main() { SeqList range; create_array(&range); rsort(&range); out(&range); } ※本文中提及的排序算法在 CSDN 上在源码，下载地址如下： https://www.wendangku.net/doc/8b16251865.html,/detail/KingWTD/2120240 =============================================================
