数据结构课程设计排序.docx
- 文档编号:11769944
- 上传时间:2023-06-02
- 格式:DOCX
- 页数:22
- 大小:122.12KB
数据结构课程设计排序.docx
《数据结构课程设计排序.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计排序.docx(22页珍藏版)》请在冰点文库上搜索。
数据结构课程设计排序
一、问题描述
1、排序问题描述
排序是计算机程序设计的一种重要操作,他的功能是将一组任意顺序数据元素(记录),根据某一个(或几个)关键字按一定的顺序重新排列成为有序的序列。
简单地说,就是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。
本次课程设计主要涉及几种常用的排序方法,分析了排序的实质,排序的应用,排序的分类,同时进行各排序方法的效率比较,包括比较次数和交换次数。
我们利用java语言来实现本排序综合系统,该系统包含了:
插入排序、交换排序、选择排序、归并排序。
其中包括:
(1)插入排序的有关算法:
不带监视哨的直接插入排序的实现;
(2)交换排序有关算法:
冒泡排序、快速排序的实现;
(3)选择排序的有关算法:
直接选择排序、堆排序的实现;
(4)归并排序的有关算法:
2-路归并排序的实现。
2、界面设计模块问题描述
设计一个菜单式界面,让用户可以选择要解决的问题,同时可以退出程序。
界面要求简洁明了,大方得体,便于用户的使用,同时,对于用户的错误选择可以进行有效的处理。
二、问题分析
本人设计的是交换排序,它的基本思想是两两比较带排序记录的关键字,若两个记录的次序相反则交换这两个记录,直到没有反序的记录为止。
应用交换排序基本思想的主要排序方法有冒泡排序和快速排序。
冒泡排序的基本思想是:
将待排序的数组看作从上到下排列,把关键字值较小的记录看作“较轻的”,关键字值较大的纪录看作“较重的”,较小关键字值的记录好像水中的气泡一样,向上浮;较大关键字值的纪录如水中的石块向下沉,当所有的气泡都浮到了相应的位置,并且所有的石块都沉到了水中,排序就结束了。
冒泡排序的步骤:
1)置初值i=1;
2)在无序序列{r[0],r[1],…,r[n-i]}中,从头至尾依次比较相邻的两个记录r[j]与r[j+1](0<=j<=n-i-1),若r[j].key>r[j+1].key,则交换位置;
3)i=i+1;
4)重复步骤2)和3),直到步骤2)中未发生记录交换或i=n-1为止;
要实现上述步骤,需要引入一个布尔变量flag,用来标记相邻记录是否发生交换。
快速排序的基本思想是:
通过一趟排序将要排序的记录分割成独立的两个部分,其中一部分的所有记录的关键字值都比另外一部分的所有记录关键字值小,然后再按此方法对这两部分记录分别进行快速排序,整个排序过程可以递归进行,以此达到整个记录序列变成有序。
快速排序步骤:
1)设置两个变量i、j,初值分别为low和high,分别表示待排序序列的起始下标和终止下标。
2)将第i个记录暂存在变量pivot中,即pivot=r[i];
3)从下标为j的位置开始由后向前依次搜索,当找到第一个比pivot的关键字值小的纪录时,则将该记录向前移动到下标为i的位置上,然后i=i+1;
4)从下表为i的位置开始由前向后依次搜索,当找到第一个比pivot的关键字值大的记录时,则将该记录向后移动到下标为j的位置上;然后j=j-1;
5)重复步骤3)和4),直到i==j为止;
6)r[i]=pivot.
三、数据结构描述
快速排序和冒泡排序都属于内部排序,快速排序是不稳定的排序,而冒泡排序是稳定的排序。
内部排序是指带排序序列完全存放在内存中进行的排序过程,这种方法适合数量不太大的数据元素的排序。
四、算法设计
1.冒泡排序的程序流程图
2.冒泡排序算法设计
publicvoidbubbleSort(){
RecordNodetemp;//辅助结点
booleanflag=true;//是否交换的标记
for(inti=1;i flag=false;//假定元素未交换 for(intj=0;j cm[1].setCpn(cm[1].getCpn()+1);//比较次数加1 if(r[j].getKey().compareTo(r[j+1].getKey())>0){//逆序时,交换 temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; cm[1].setMvn(cm[1].getMvn()+3);//移动次数加3; flag=true; } } } } 3.快速排序的程序流程图 (1) 4.快速排序的程序流程图 (2) 5.快速排序算法设计 publicintpartition(inti,intj){ RecordNodepivot=r[i];//第一个记录作为支点记录 while(i while(i j--; } if(i r[i]=r[j];//将比支点记录关键字值小的记录向前移动 i++; } while(i i++; } if(i r[j]=r[i];//将比支点记录关键字值大的记录向后移动 j--; } } r[i]=pivot;//支点记录到位 returni;//返回支点位置 } publicvoidqSort(intlow,inthigh){ if(low intpivotloc=partition(low,high); qSort(low,pivotloc-1); qSort(pivotloc+1,high); } } publicvoidquickSort(){ qSort(0,this.curlen-1); } 五、详细程序清单 packageKCSJ_Sort; importjava.util.Scanner; //记录结点类 classRecordNode{ privateComparablekey; privateObjectelement; publicObjectgetElement(){ returnelement; } publicvoidsetElement(Objectelement){ this.element=element; } publicComparablegetKey(){ returnkey; } publicvoidsetKey(Comparablekey){ this.key=key; } publicRecordNode(Comparablekey){ this.key=key; } publicRecordNode(Comparablekey,Objectelement){ this.key=key; this.element=element; } } //关键字类型类 classKeyTypeimplementsComparable privateintkey; publicKeyType(){ } publicKeyType(intkey){ this.key=key; } publicintgetKey(){ returnkey; } publicvoidsetKey(intkey){ this.key=key; } publicStringtoString(){ returnkey+""; } publicintcompareTo(KeyTypeanother){ intthisVal=this.key; intanotherVal=another.key; return(thisVal -1: (thisVal==anotherVal? 0: 1)); } } //比较与移动次数类 classCopareMoveNum{ privateintcpn; privateintmvn; publicintgetCpn(){ returncpn; } publicvoidsetCpn(intcpn){ this.cpn=cpn; } publicintgetMvn(){ returnmvn; } publicvoidsetMvn(intmvn){ this.mvn=mvn; } } //顺序排序表类 classSeqList{ CopareMoveNum[]cm; privateRecordNode[]r; privateintcurlen; publicRecordNode[]getRecord(){ returnr; } publicvoidsetRecord(RecordNode[]r){ this.r=r; } publicSeqList(intmaxSize){ this.r=newRecordNode[maxSize]; this.curlen=0; this.cm=newCopareMoveNum[3]; for(inti=0;i<3;i++){ this.cm[i]=newCopareMoveNum(); this.cm[i].setCpn(0); this.cm[i].setMvn(0); } } //求顺序表中的数据元素个数并由函数返回其值 publicintlength(){ returncurlen;// } publicvoidinsert(inti,RecordNodex)throwsException{ if(curlen==r.length){ thrownewException("顺序表已满"); } if(i<0||i>curlen){ thrownewException("插入位置不合理"); } for(intj=curlen;j>i;j--){ r[j]=r[j-1]; } r[i]=x; this.curlen++; } //输出数组元素 publicvoiddisplay(){ for(inti=0;i System.out.print(""+r[i].getKey().toString()); } System.out.println(); } //不带监视哨的直接插入排序算法 publicvoidinsertSort(){ RecordNodetemp; inti,j; for(i=1;i temp=r[i]; cm[0].setMvn(cm[0].getMvn()+1); for(j=i-1;j>=0&&temp.getKey().compareTo(r[j].getKey())<0;j--){ cm[0].setCpn(cm[0].getCpn()+1); r[j+1]=r[j]; cm[0].setMvn(cm[0].getMvn()+1); } r[j+1]=temp; cm[0].setMvn(cm[0].getMvn()+1); } } //冒泡排序算法 publicvoidbubbleSort(){ RecordNodetemp; booleanflag=true; for(inti=1;i flag=false; for(intj=0;j cm[1].setCpn(cm[1].getCpn()+1); if(r[j].getKey().compareTo(r[j+1].getKey())>0){ temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; cm[1].setMvn(cm[1].getMvn()+3); flag=true; } } } } //快速排序算法 publicintpartition(inti,intj){ RecordNodepivot=r[i]; while(i while(i j--; } if(i r[i]=r[j]; i++; } while(i i++; } if(i r[j]=r[i]; j--; } } r[i]=pivot; returni; } publicvoidqSort(intlow,inthigh){ if(low intpivotloc=partition(low,high); qSort(low,pivotloc-1); qSort(pivotloc+1,high); } } publicvoidquickSort(){ qSort(0,this.curlen-1); } //简单选择排序算法 publicvoidselectSort(){ RecordNodetemp; for(inti=0;i intmin=i; for(intj=i+1;j cm[2].setCpn(cm[2].getCpn()+1); if(r[j].getKey().compareTo(r[min].getKey())<0){ min=j; } } if(min! =i){ temp=r[i]; r[i]=r[min]; r[min]=temp; cm[2].setMvn(cm[2].getMvn()+3); } } } //堆排序算法 publicvoidsift(intlow,inthigh){ inti=low; intj=2*i+1; RecordNodetemp=r[i]; while(j if(j j++; } if(temp.getKey().compareTo(r[j].getKey())>0){ r[i]=r[j]; i=j; j=2*i+1; } else{ j=high+1; } } r[i]=temp; } publicvoidheapSort(){ intn=this.curlen; RecordNodetemp; for(inti=n/2-1;i>=0;i--){ sift(i,n); } for(inti=n-1;i>0;i--){ temp=r[0]; r[0]=r[i]; r[i]=temp; sift(0,i); } } //归并排序算法 publicvoidmerge(RecordNode[]r,RecordNode[]order,inth,intm,intt){ inti=h,j=m+1,k=h; while(i<=m&&j<=t){ if(r[i].getKey().compareTo(r[j].getKey())<=0){ order[k++]=r[i++]; } else{ order[k++]=r[j++]; } } while(i<=m){ order[k++]=r[i++]; } while(j<=t){ order[k++]=r[j++]; } } publicvoidmergepass(RecordNode[]r,RecordNode[]order,ints,intn){ intp=0; while(p+2*s-1<=n-1){ merge(r,order,p,p+s-1,p+2*s-1); p+=2*s; } if(p+s-1 merge(r,order,p,p+s-1,n-1); } else{ for(inti=p;i<=n-1;i++){ order[i]=r[i]; } } } publicvoidmergeSort(){ ints=1; intn=this.curlen; RecordNode[]temp=newRecordNode[n]; while(s mergepass(r,temp,s,n); display(); s*=2; mergepass(temp,r,s,n); display(); s*=2; } } } //测试类 publicclassKCSJ_Sort_1{ staticSeqListST=null; publicstaticvoidcreateSearchList()throwsException{ ST=newSeqList(20); Scannersc=newScanner(System.in); System.out.print("请输入排序表的表长: "); intn=sc.nextInt(); KeyType[]k=newKeyType[n]; System.out.print("请输入排序表中的关键字序列: "); for(inti=0;i k[i]=newKeyType(sc.nextInt()); } for(inti=0;i RecordNoder=newRecordNode(k[i]); ST.insert(i,r); } } publicstaticvoidmain(String[]args)throwsException{ Scannersc=newScanner(System.in); //System.out.println("创建顺序查找表"); //createSearchList(); while(true){ System.out.println("***************欢迎进入排序系统***************\n"); System.out.println("★1直接插入排序2.冒泡排序3.快速排序★\n"); System.out.println("★4.直接选择排序5堆排序6.归并排序★\n"); System.out.println("★0.退出★\n"); System.out.println("***********************************************\n"); System.out.print("请输入选择(0-6): "); inti=sc.nextInt(); switch(i){ case1: System.out.println("---不带监视哨直接插入排序---"); System.out.println("创建顺序排序表"); createSearchList(); ST.insertSort(); System.out.print("排序结果: "); ST.display(); System.out.println("比较次数为: "+ST.cm[0].getCpn()); System.out.println("移动次数为: "+ST.cm[0].getMvn()); break; case2: System.out.println("---冒泡排序---"); System.out.println("创建顺序排序表"); createSearchList(); ST.bubbleSort(); System.out.print("排序结果: "); ST.display(); System.out.println("比较次数为: "+ST.cm[1].getCpn()); System.out.println("移动次数为: "+ST.cm[1].getMvn()); break; case3: System.out.println("---快速排序---"); System.out.println("创建顺序排序表"); createSearchList(); ST.quickSort(); System.out.print("排序结果: "); ST.display(); break; case4: System.out.print("---简单选择排序---"); System.out.println("创建顺序排序表"); createSearchList(); ST.selectSort(); System.out.print("排序结果: "); ST.display(); System.out.println("比较次数为: "+ST.cm[2].getCpn()); System.out.println("移动次数为: "+ST.cm[2].getMvn()); break; case5: System.o
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 排序