实验七．排序.docVIP

南昌大学实验报告 学生姓名： 唐建雄 学 号： 800606166 专业班级： 计算机软件064班 实验类型：□ 验证 □ 综合 □ 设计 □ 创新 实验日期： 2007.12.28 实验成绩： 一．实验名称 实验七．排序 二．实验目的　　 １.掌握各种排序的定义及其基本运算 ２.掌握排序的使用方法 三．　实验内容 １.用直接排序法对序列排序 2.用直折半插入法对序列排序 3.用起泡排序法对序列排序 4.用选择排序法对序列排序 四．实验步骤 #include stdlib.h #include ctime #include iostream.h void CreatStable(int a[], int n) {//利用随机函数产生一个含有n个整数的数组a[]，元素为a[1],…,a[n]。 int i; srand(time(0)); for(i=0;i=n;i++) a[i]=rand()%1000; } void disp(int a[],int low,int high) {//显示数组元素a[low],...,a[high]; int i; for(i=low;i=high;i++) couta[i] ; coutendl; } void InsertSortA(int a[ ],int n) {//对数组a[]的前n个元素采用直接插入排序进行排序5 for(int i=2;i=n;i++) if(a[i]a[i-1]) { a[0]=a[i]; a[i]=a[i-1]; for(int j=i-2;a[0]a[j];--j) a[j+1]=a[j]; a[j+1]=a[0]; } } void BinInsertSort(int a[ ], int n) {//对数组a[]的前n个元素采用折半插入排序进行排序 for(int i=2;i=n;i++) { a[0]=a[i]; int low=1,high=i-1; while(low=high) { int m=(low+high)/2; if(a[0]a[m])high=m-1; else low=m+1; } for(int j=i-1;j=high;--j)a[j+1]=a[j]; a[high+1]=a[0]; } } void BubbleSort(int a[ ], int n) {//对数组a[]的前n个元素采用起泡排序进行排序 for(int i=1;in;i++) for(int j=1;j=n-i;j++) if(a[j]a[j+1]) { a[0]=a[j]; a[j]=a[j+1]; a[j+1]=a[0]; } } int SelectMinkey(int a[],int n,int i) { int k=i; for(int j=i+1;j=n;j++) if(a[j]a[k]) k=j; return k; } void SelectionSort(int a[ ], int n) {//对数组a[]的前n个元素采用简单选择排序进行排序 for(int i=1;in;++i){ int j=SelectMinkey(a,n,i); if(i!=j){a[0]=a[i];a[i]=a[j];a[j]=a[0];} } } void main() {//验证上述函数的主函数。 int *pn,n; cout序列的元素个数为:; cinn; pn=new int[n+1]; CreatStable(pn, n); cout原始序列为:; disp(pn,1,n); InsertSortA(pn, n); cout进行直接插入排序序列:; disp(pn,1,n); int *qn,m; cout序列的元素个数为:; cinm; qn=new int[m+1]; CreatStable(qn, m); cout原始序列为:; disp(qn,1,m); BinInsertSort(qn, m); cout进行折半插入排序序列:; disp(qn,1,m); int *p,k; cout序列的元素个数为:; cink; p=new int[k+1]; CreatStable(p, k); cout原始序列为:; disp(p,1,k); BubbleSort(p, k); cout进行起泡排序序列:; disp(p,1,k); int *q,h; cout序列的元素个数为:; c