数据结构课程设计-排序.docx

《数据结构课程设计-排序.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计-排序.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计-排序 一、问题描述 1、排序问题描述 排序是计算机程序设计的一种重要操作，他的功能是将一组任意顺序数据元素（记录），根据某一个（或几个）关键字按一定的顺序重新排列成为有序的序列。简单地说，就是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。 本次课程设计主要涉及几种常用的排序方法，分析了排序的实质，排序的应用，排序的分类，同时进行各排序方法的效率比较，包括比较次数和交换次数。我们利用java语言来实现本排序综合系统，该系统包含了：插入排序、交换排序、选择排序、归并排序。其中包括： （1）插入排序的有关算法：不带监视哨的直接插入排序的实现； （2）交换排序有关算法：

2、冒泡排序、快速排序的实现； （3）选择排序的有关算法：直接选择排序、堆排序的实现； （4）归并排序的有关算法：2-路归并排序的实现。 2、界面设计模块问题描述 设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。 二、问题分析 本人设计的是交换排序，它的基本思想是两两比较带排序记录的关键字，若两个记录的次序相反则交换这两个记录，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有冒泡排序和快速排序。 冒泡排序的基本思想是：将待排序的数组看作从上到下排列，把关键字值较小的记录看作“较轻的

3、”，关键字值较大的纪录看作“较重的”，较小关键字值的记录好像水中的气泡一样，向上浮；较大关键字值的纪录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，并且所有的石块都沉到了水中，排序就结束了。 冒泡排序的步骤： 1)置初值i=1； 2)在无序序列r0,r1,，rn-i中，从头至尾依次比较相邻的两个记录rj 与rj+1（0 0) /逆序时，交换 temp = rj; rj = rj + 1; rj + 1 = temp; cm1.setMvn(cm1.getMvn()+3); /移动次数加3; flag = true; 3.快速排序的程序流程图（1） 4.快速排序的程序流程图（2） 5.快速

4、排序算法设计 public int partition(int i,int j) RecordNode pivot=ri; /第一个记录作为支点记录 while(i i; j-) rj = rj - 1; ri = x; this.curlen+; /输出数组元素 public void display() for (int i = 0; i = 0 & temp.getKey().compareTo(rj.getKey() 0) temp = rj; rj = rj + 1; rj + 1 = temp; cm1.setMvn(cm1.getMvn()+3); flag = true; /

5、快速排序算法 public int partition(int i,int j) RecordNode pivot=ri; while(i0) ri=rj; i=j; j=2*i+1; else j=high+1; ri=temp; public void heapSort() int n=this.curlen; RecordNode temp; for(int i=n/2-1;i=0;i-) sift(i,n); for(int i= n-1;i0;i-) temp=r0; r0=ri; ri=temp; sift(0,i); /归并排序算法 public void merge(Recor

6、dNode r,RecordNode order,int h,int m,int t) int i=h,j=m+1,k=h; while(i=m&j=t) if(ri.getKey().compareTo(rj.getKey()=0) orderk+=ri+; else orderk+=rj+; while(i=m) orderk+=ri+; while(j=t) orderk+=rj+; public void mergepass(RecordNode r,RecordNode order,int s,int n) int p=0; while(p+2*s-1=n-1) merge(r, o

7、rder, p, p+s-1, p+2*s-1); p+=2*s; if(p+s-1n-1) merge(r, order, p, p+s-1, n-1); else for(int i=p;i=n-1;i+) orderi=ri; public void mergeSort() int s=1; int n=this.curlen; RecordNode temp= new RecordNoden; while(sn) mergepass(r,temp,s,n); display(); s*=2; mergepass(temp,r,s,n); display(); s*=2; /测试类 public class KCSJ_Sort_1 static SeqList ST = null; public static void createSearchList() throws Exception ST=new SeqList(20); Scanner sc=new Scanner(System.in); System.out.print(请输入排序表的表长:); int n=sc.nextInt(); KeyType k= new KeyTypen;