山东大学面向对象第二次实验排序实验报告

面向对象实验报告

排序

学院：计算机科学与技术学院学号：************

姓名：*** 班级：**级**班

一、 实验要求

1. 可以对任何简单类型和任意对象进行排序； 2. 可以支持升序、降序、字典排序等多种顺序要求； 3. 可以随意增加排序算法和顺序要求，保证其他程序不修改； 4. 减少程序代码中逻辑上的冗余；

5. 至少用两种方案编程实现该程序包，并说明两个方案的优缺点； 6. 提交设计报告，包括：使用UML设计的类图；主要程序代码说明；方

案优缺点比较。

二、 实验环境

Eclipse、JDK6.0、windows7。

三、 需求分析

需要实现各种排序算法，各种排序要求。而且要便于后来的对排序算法和排序要求的添加。尽量减少代码的冗余。两种实现方案。

四、 类的设计

方案一： UML设计类图

代码说明：

主要利用java的 Comparator类实现对象的比较和多种顺序。在Sort类的构造方法的参数列表中包含需要排序的数组和Comparator比较器对象。因为参数列表中的数组类型是Object，所以支持基本类型和任意类型的对象进行比较。

想要增加排序算法，只需继承Sort 类，然后在新类中编写相应的排序算法即可。

因为排序方式是由comparator比较器对象中的compare方法决定的，所以想使用什么样的顺序只需改写comparator中的compare方法即可。

具体实现代码如下： /* BubbleSort */

import java.util.Comparator;

public class BubbleSort extends Sort {

public BubbleSort(Object[] a,Comparator b) {

super(a,b);

public Object[] sort() {

Object temp;

int n=a.length; for(int j=0;j

for(int i=0;i

if(b.compare(a[i],a[i+1])==1) {

}

temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;

}

this.b=b;

} }

}

}

return a;

/* InsertSort */

import java.util.Comparator; public class InsertSort extends Sort {

public InsertSort(Object[] a, Comparator b) {

public Object[] sort() {

int n=a.length; for(int i=1;i

Object temp=a[i];

}

super(a, b);

int j;

for(j=i-1;j>=0&&b.compare(temp, a[j])==1;j--) {

}

}

}

}

a[j+1]=a[j];

a[j+1]=temp;

return a;

/* QuickSort */

import java.util.Comparator; public class QuickSort extends Sort {

public QuickSort(Object[] a, Comparator b) {

public Object[] sort() }

super(a, b);

// TODO Auto-generated constructor stub

{

private int getMiddle(Object[] list,int low,int high) {

Object tmp = list[low]; while(low

while(low

}

list[low]=list[high];

while(low

}

list[low]=tmp;

}

list[high]=list[low];

low++; high--;

}

quickSort(a,0,a.length-1); return a;

}

return low;

private void quickSort(Object[] list,int low,int high) {

if(low

}

}

int middle = getMiddle(list,low,high); quickSort(list,low,middle-1); quickSort(list,middle+1,high);

}

方案二： UML设计图：

代码说明：

主要利用java的Comparable接口实现。在Sort类的构造方法里将接收的任意类型数组转化成为Comparable类型，需要什么排序类型就继承Comparable相应的实现类。通过实现compareTo方法实现比较和排序。想增加排序方法，新建一个类继承Sort即可。想新增排序方式，新增一个继承类让排序类实现即可。 具体实现代码：

排序类类似方案一，去除Comparator改为实现接口，并实现compareTo方法 接口：

Public abstract class Compa implements Comparable {

protect Object a,b; public int compareTo();

}

/* ascOrder */

public class Asc extends Compa {

public Object[] Asc(); public int compareTo() { }; }

/* descOrder */

public class Desc extends Compa {

public Object[] Desc(); public int compareTo() { }; }

//具体实现 //具体实现

/* dictionartOrder */

public class Dic extends Compa {

public Object[] Dic (); public int compareTo() { }; }

//具体实现

五、 两种排序方案的比较

第一种方案利用了工厂类的思想，使用排序方法前只需要构造相应的comparator比较器。不过如果排序算法较多，相对应的子类就会很多，这样就增加了类的复杂程度，不利于维护。同时这种排序方案效率不高。

第二种方案通过继承接口的不同的实现类实现不同顺序的排序。不过这样实现的结构相对复杂，且效率不高。

这两种方案的共同缺点是效率不高，因为这两种方案都没有区别基本数据类型和对象数据类型，而只是统一地用了同一种排序方案。但优点是很好地重用了排序算法，真正做到了同样的算法绝不写第二遍的目标，但是在实际运用中，效率问题却也是不可忽视的。

/* dictionartOrder */

public class Dic extends Compa {

public Object[] Dic (); public int compareTo() { }; }

//具体实现

五、 两种排序方案的比较

第一种方案利用了工厂类的思想，使用排序方法前只需要构造相应的comparator比较器。不过如果排序算法较多，相对应的子类就会很多，这样就增加了类的复杂程度，不利于维护。同时这种排序方案效率不高。

第二种方案通过继承接口的不同的实现类实现不同顺序的排序。不过这样实现的结构相对复杂，且效率不高。

这两种方案的共同缺点是效率不高，因为这两种方案都没有区别基本数据类型和对象数据类型，而只是统一地用了同一种排序方案。但优点是很好地重用了排序算法，真正做到了同样的算法绝不写第二遍的目标，但是在实际运用中，效率问题却也是不可忽视的。

本文来源：https://www.bwwdw.com/article/wdy8.html