一、问题描述
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.冒泡排序算法设计
public void bubbleSort() {
RecordNode temp; //辅助结点
boolean flag = true; //是否交换的标记
for (int i = 1; i < this.curlen && flag; i++) { //有交换时再进行下一趟，最多n-1趟flag = false; //假定元素未交换
for (int j = 0; j < this.curlen - i; 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.快速排序算法设计
public int partition(int i,int j) {
RecordNode pivot=r[i]; //第一个记录作为支点记录
while(iwhile(ij--;
}
if(ir[i]=r[j]; //将比支点记录关键字值小的记录向前移动
i++;
}
while(i0){
i++;
}
if(ir[j]=r[i]; //将比支点记录关键字值大的记录向后移动
j--;
}
}
r[i]=pivot; //支点记录到位
return i; //返回支点位置
}
public void qSort(int low,int high){
if(lowint pivotloc=partition(low,high);
qSort(low,pivotloc-1);
qSort(pivotloc+1,high);
}
}
public void quickSort(){
qSort(0,this.curlen-1);
}
五、详细程序清单
package KCSJ_Sort;
import java.util.Scanner;
//记录结点类
class RecordNode {
private Comparable key;
private Object element;
public Object getElement() {
return element;
}
public void setElement(Object element) {
this.element = element;
}
public Comparable getKey() {
return key;
}
public void setKey(Comparable key) {
this.key = key;
}
public RecordNode(Comparable key) {
this.key = key;
}
public RecordNode(Comparable key, Object element) {
