排序的应用

1．已知关键字序列{10，80，45，3，65，23，98，8}，试用快速排序算法进行排序，并给出每一趟排序结果。
要求：
（1） 按题目中的顺序输入这个关键字序列，打印输出每一趟排序的结果。
（2） 按升序重新输入这些关键字，重新打印输出，并与（1）的结果做比较。
（3） 按降序重新输入这些关键字，重新打印输出，并与（1）和（2）的结果做比较。

#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
using namespace std;
#define MAXSIZE 100
typedef int KeyType;		/*关键字类型*/
typedef int DataType;
typedef struct{			/*数据元素类型*/KeyType key;		/*关键字*/DataType data;	/*其他数据*/
}SortItem,SqList[MAXSIZE];
int Partition(SqList L,int i,int j);
int QuickSort(SqList L,int low,int upper);
void display(SqList L,int a);
int main(void)
{SqList a;int b[]={10 ,80, 45, 3 ,65, 23, 98, 8};int c[]={3,8,10,23,45,65,80,98};int d[]={98,80,65,45,23,10,8,3};int len=sizeof(b)/sizeof(b[0]);for(int i=0;i<len;i++)a[i].key=b[i];display(a,7);QuickSort(a,0,7);display(a,7);cout<<endl<<"升序"<<endl;for(int i=0;i<len;i++)a[i].key=c[i];QuickSort(a,0,7);display(a,7);cout<<endl<<"降序"<<endl;for(int i=0;i<len;i++)a[i].key=d[i];QuickSort(a,0,7);display(a,7);cout<<"hello word"<<endl;return 0;
}
//快速排序
int Partition(SqList L,int i,int j){SortItem pivot;pivot=L[i];	/*用第1个元素作为基准元素*/while(i<j) { /*从序列两端交替向中央扫描，直至i=j为止*/	/*从右向左扫描，查找第1个关键字小于基准元素的元素*/while(i<j && pivot.key<=L[j].key) j--;if(i<j){L[i]=L[j]; i++;} /*找到第1个小于基准元素的元素*//*从左向右扫描，查找第1个关键字大于等于基准元素的数据元素*/while(i<j && pivot.key>L[i].key ) i++;if(i<j) {L[j]=L[i];j--;}}L[i]=pivot;/*确定枢轴的位置*/return i;
} 
int QuickSort(SqList L,int low,int upper){int pivot;	/*划分后枢轴的位置*/if(low<upper){pivot=Partition(L,low,upper);	/*划分区间*/display(L,7);QuickSort(L,low,pivot-1);/*划分后左子序列递归排序*/QuickSort(L,pivot+1,upper);	/*右子序列递归排序*/}return 0;
} 
void display(SqList L,int a) {for(int i=0;i<=a;i++)cout<<L[i].key<<"   ";cout<<endl;
}

2.已知关键字序列{601，223，417，125，418，391，65，359}，请打印输出基数排序的每一趟结果。

#include <iostream>
#include <stdio.h>
#include <string>
#include <stdlib.h>
using namespace std;
#define MAXSIZE 100
typedef int KeyType;
//数据定义
typedef struct{KeyType key;
}DataType;
void display(DataType L[],int a) ;
//链队列定义
typedef struct QNode{   DataType data;  struct QNode* next;
}LQNode, *PQNode;
typedef struct{ PQNode front, rear;
}LinkQueue; 
//入队
int EnQueue(LinkQueue *Q,DataType e){   PQNode p;p=(PQNode)malloc(sizeof(LQNode));if(!p){printf("内存分配失败，不能完成入队操作！\n");return 0;}p->data=e;p->next=NULL;   Q->rear->next=p;Q->rear=p;return 1;
} 
//出队
int DeQueue(LinkQueue *Q,DataType *e){  PQNode p;if(Q->front==Q->rear){printf("队列已空，不能完成出队操作！\n");return 0;}p=Q->front->next;*e=p->data;Q->front->next=p->next; free(p);if(Q->rear==p)  /*若删的是最后一个结点，移动尾指针*/Q->rear=Q->front;return 1;
}
//初始化队列
int InitQueue(LinkQueue *Q){    Q->front=Q->rear=(PQNode)malloc(sizeof(LQNode));if(!Q->front){printf("初始化队列失败！\n");return 0;}Q->front->next=NULL;return 1;
} 
//判断链队为空
int QueueEmpty(LinkQueue Q){if(Q.front==Q.rear) return 1;else    return 0;
} 
//销毁链表
int DestroyQueue(LinkQueue *Q){ while(Q->front){Q->rear=Q->front->next;free(Q->front);Q->front=Q->rear;}   return 1;
} 
//在进行基数排序时，需要获取关键字的第m位数字值。下面的函数用来提前第m位的数字值。
int digit(KeyType key,int m,int r){/* 获取key的第m位的数字，该数字是r进制的*/int i,d;if(m==0) return key % r;d=r;for(i=1;i<m;i++) d*=r;return ((int)(key/d)%r);
} 
//基数排序
void RadixSort(DataType L[],int n,int m,int r){/* L中的关键字为m位r进制数，L的长度为n */LinkQueue* q;	/*r个链队列的头尾指针存放在q数组中*/int i,j,k;q=(LinkQueue*)malloc(r*sizeof(LinkQueue));for(i=0;i<r;i++) InitQueue(&q[i]);/*初始化r个链队列*/for(i=0;i<m;i++){ /*进行m次分配与收集*/for(j=0;j<n;j++) { 		/*分配*/		k=digit(L[j].key,i,r); EnQueue(&q[k],L[j]);  /*入队操作，见2.5.5节*/}k=0;for(j=0;j<r;j++)		/*收集*/for(;!QueueEmpty(q[j]);k++)DeQueue(&q[j],&(L[k]));for(j=0;j<n;j++)		/*输出每趟基数排序结果*/printf("%d\t",L[j].key);printf("\n\n");}for(i=0;i<r;i++)	DestroyQueue(q);
} 
int main(void)
{DataType dataqq[8];int b[]={60,223,417,125,418,391,65,359};int len=sizeof(b)/sizeof(b[0]);for(int qwer=0;qwer<len;qwer++){dataqq[qwer].key=b[qwer];}display(dataqq,len-1);cout<<endl;RadixSort(dataqq,len,3,10);cout<<"hello word"<<endl;return 0;
}
void display(DataType L[],int a) {for(int i=0;i<=a;i++)cout<<L[i].key<<'\t';cout<<endl;
}

3.已知学生综合成绩表的数据元素类型为：
struct grade{
int id; /学号/
fload score; /综合成绩/
}
要求：
（1） 模拟建立一个学生成绩表（初始学号和成绩为无序状态）；
（2） 采用直接插入法，按成绩从高到底排序，并输出学号、成绩和名次。
（3） 采用归并排序，按学号输出成绩列表。

#include <iostream>
#include <stdio.h>
#include <string>
#include <stdlib.h>#include <iomanip>
using namespace std;
#define MAXSIZE 100
typedef int KeyType;
//成绩结构体 
struct grade{int id;			/*学号*/float score;	/*综合成绩*/
};
//直接插入排序
void InsertSort(grade L[],int n){int i,j;grade p;for(i=1;i<n;i++)	{p=L[i];for(j=i-1;j>=0 && p.score<L[j].score;j--)L[j+1]=L[j];L[j+1]=p;	/*插入*/}
} 
//归并排序 
void MergeTwo(grade L[],int low,int mid,int upper){grade* p;/*临时存放归并结果的临时数组*/int low1=low; int low2=mid+1; int pos=0; p=(grade*)malloc((upper-low+1)*sizeof(grade));while(low1<=mid && low2<=upper)/*两个子序列归并*/p[pos++]=(L[low1].score<=L[low2].score) ? L[low1++] : L[low2++];/*将两个子序列尚未处理完的部分复制到p中*/for(;low1<=mid;low1++,pos++)	p[pos]=L[low1];for(;low2<=upper;low2++,pos++)	p[pos]=L[low2];/*归并完成，p中数据元素复制回L*/for(pos=0,low1=low;low1<=upper;pos++,low1++) L[low1]=p[pos];free(p);
} 
//一趟归并排序算法
void Merge(grade L[],int len,int n){int i;for(i=0;i+2*len-1<n;i+=2*len)MergeTwo(L,i,i+len-1,i+2*len-1);if(i+len-1<n)/*对余下的两个子序列归并*/MergeTwo(L,i,i+len-1,n-1);for(i=0;i<n;i++)		/*输出每趟归并的结果*/printf("%.2f\t",L[i].score);printf("\n\n");
} 
//二路归并排序算法
void MergeSort(grade L[],int n){int i;for(i=1;i<n;i*=2)Merge(L,i,n);
} 
void display(grade L[],int a);
int main()
{int a[]={1901,1902,1903,1904,1905,1906};float b[]={99,98,60,30,66.66,99.99};int i=0;int len=sizeof(a)/sizeof(a[0]);grade qq[len];for(i;i<len;i++){qq[i].id=a[i];qq[i].score=b[i];}display(qq,len);InsertSort(qq,len);cout<<"直接插入排序"<<endl;
//	cout<<"名次"<<'\t';
//	for(int z=1;z<=len;z++)
//	cout<<z<<'\t';
//	cout<<endl;
//	display(qq,len);MergeSort(qq,len);cout<<"归并排序"<<endl;display(qq,len);return 0;}
//显示成绩 
void display(grade L[],int a) {cout<<"id"<<"     "; for(int i=a-1;i>-1;i--){cout<<L[i].id<<'\t';}cout<<endl;cout<<"score"<<"  "; for(int i=a-1;i>-1;i--){printf("%.2f", L[i].score);cout<<'\t';}	cout<<endl;
}

支持可以关注我哦，持续分享编写的代码。