数据结构排序实验报告.doc

《数据结构》课程设计报告
实验五 排序

一、需求分析：
本演示程序用C++6.0编写，完成各种排序的实现，对输入的一组数字实现不同的排序方法，对其由小到大顺序输出。
（1）分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法进行编写。
（2）、对存储的函数即输入的数字进行遍历。
（3）、初始化函数对输入的数字进行保存。
（4）、主函数实现使用者操作界面的编写，对输入、选择、保存、输出的各种实现。这当中还包括了各个函数的调用的实现。
（5）、程序所能达到的功能：完成对输入的数字的生成，并通过对各排序的选择实现数字从小到大的输出。
二、程序主要功能以及基本要求：
（1）、设计一个菜单，格式如下：
1、直接插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、选择排序
6、堆排序
7、退出
（2）、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。
三、系统框架图：
本程序包含了9个函数，它们分别是：
（1）、直接插入排序的算法函数InsertSort（）。
（2）、希尔排序的算法函数ShellSort（）。
主函数
（3）、冒泡排序算法函数BubbleSort（）。
操作界面的设计，函数的调用。
对输入的数组进行遍历初始化
各个排序算法函数
（4）、快速排序的算法函数Partition（）。
（5）、选择排序算法函数SelectSort（）。
（6）、堆排序算法函数HeapAdjust（）。
（7）、对存储数字的遍历函数Visit（）。
（8）、初始化函数InitSqList（）。
（9）、主函数main（）。
四、详细设计
实现各个算法的主要内容，下面是各个函数的主要信息：
（1）各个排序函数的算法：
一、直接插入排序
void InsertSort(SqList &L)
{
int i,j;
for( i=2; i<=L.length;i++)
{
if(L.r[i].key < L.r[i-1].key)
{
L.r[0] = L.r[i];
L.r[i] = L.r[i-1];
for( j=i-2; (L.r[0].key < L.r[j].key); j--)
L.r[j+1] = L.r[j];
L.r[j+1] = L.r[0];
}
}
}
二、希尔排序
void ShellSort(SqList &L)
{
int i, j;
int dk = 1;//增量
while(dk <=L.length/3)
dk = 3*dk+1;//增大增量
while(dk>0)
{
dk /= 3;//减小增量
for (i = dk; i <=L.length; i++)
{
L.r[0].key = L.r[i].key;
j = i;
while ((j >= dk) && (L.r[j-dk].key > L.r[0].key))
{
L.r[j].key = L.r[j-dk].key;
j -= dk;
}
L.r[j].key = L.r[0].key;
}
}
}
三、冒泡排序
void BubbleSort(SqList &L)
{
int i,j;
for(i=0;i<L.length-2;i++)
{
int flag = 1;
for(j=0;j<L.length-i-2;j++)
if(L.r[j].key > L.r[j+1].key)
{
flag = 0;
int temp;
temp = L.r[j].key;
L.r[j].key = L.r[j+1].key;
L.r[j+1].key = temp;
}
//若无交换说明已经有序
if(flag==1)
break;
}

}
四、快速排序
int Partition(SqList &L,int low,int high)
{
//分割区域函数
L.r[0] = L.r[low];
int pivotkey = L.r[low].key;//一般将顺序表第一个元素作为支点
while(low < high)
{
while(low<high && L.r[high].key>=pivotkey)
high--;
L.r[low] = L.r[high];
while(low<high && L.r[low].key<=pivotkey)
low++;
L.r[high] = L.r[low];
}
L.r[low] = L.r[0];//返回枢轴位置
return low;
}
void QSort(SqList &L,int low,int high)
{
//每张子表的快速排序
if(low<high)
{
int pivotloc = Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L)
{
QSort(L,1,L.length);
}
五、简单选择排序
void SelectSort(SqList &L)
{
int min;
int j;
for (int i = 0; i <L.length; i++)
{ // 选择第i小的记录，并交换
j = i;
min = L.r[i].key;
for (int k = i; k < L.length; k++)
{ // 在R[i..n-1]中选择最小的记录
if (L.r[k].key < min)
{
min = L.r[k].key ;
j = k;
}
}
if (i != j)
{ // 与第i个记录交换
int temp = L.r[i].key;
L.r[i].key = L.r[j].key;
L.r[j].key = temp;
}
}
}
六、堆排序
void HeapAdjust(HeapType &H,int s,int m)
{
//堆调整，将记录调整为小顶堆
int j;
RedType rc = H.r[s];//暂时存储根结点
for(j=2*s; j<=m; j*=2)
{
//沿着结点记录较小的向下筛选
if(j<m && H.r[j].key<H.r[j+1].key)
++j;
if(rc.key>= H.r[j].key)
break;
H.r[s] = H.r[j];
s = j;
}
H.r[s] = rc;
}
void HeapSort(HeapType &H)
{
int i;
RedType temp;
for(i = H.length; i>0; --i)
HeapAdjust(H,i,H.length);
for(i=H.length; i>1; --i)
{

temp = H.r[1];
H.r[1] = H.r[i];
H.r[i] = temp;
HeapAdjust(H,1,i-1);
}
}
（2）遍历函数与初始化
void Visit(SqList L)
{
for(int i=1; i<=L.length; i++)
cout<<L.r[i].key<<" ";
cout<<endl;
}
void InitSqList(SqList &L,int a[])
{
for(int i=1;i<=L.length;i++)
L.r[i].key = a[i];
}
五、测试结果
以下是各种界面的测试结果：
（1）输入的界面 :

（2）排序操作界面：

（3）各种排序的结果：

六、设计不足以及存在问题
本程序是基于C++6.0的实现，其实在设计上的改进可以利用类进行操作，这种类的改进了存储上的不足还可以实现了，对各种的函数基于类的实现，这就是对本程序的改进，这是十分重要的与是改进的基础。
本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题，导致排序的结果以及排序的界面出现了问题，的不到实现。后来对算法进行改进，最终把问题得以解决。

10