数据结构排序实验报告

本演示程序用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的实现，其实在设计上的改进可以利用类进行操作，这种类的改进了存储上的不足还可以实现了，对各种的函数基于类的实现，这就是对本程序的改进，这是十分重要的与是改进的基础。

本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题，导致排序的结果以及排序的界面出现了问题，的不到实现。后来对算法进行改进，最终把问题得以解决。

《数据结构》课程设计报告

数据结构实验报告排序实验题目输入十个数从插入排序快速排序选择排序三类算法中各选一种编程实现实验所使用的数据结构内容及编程思路1插入排序直接插入排序的基本操作是将一个记录到已排好序的有序表中从而得到一个新的记录增...

1实验要求实验目的学习实现对比各种排序算法掌握各种排序算法的优劣以及各种算法使用的情况实验内容使用简单数组实现下面各种排序算法并进行比较排序算法1插入排序2希尔排序3冒泡排序4快速排序5简单选择排序6堆排序选作...

实验八排序一实验目的1熟悉掌握教材中所介绍的几种排序方法2学会分析各种内排序算法的性能二实验内容1随机产生20位整数2输入序列编写程序按下列排序方法将序列从小到大排序并输出1冒泡排序2快速排序3纪录每种方法比较...

一问题描述在操作系统中我们总是希望以最短的时间处理完所有的任务但事情总是要一件件地做任务也要操作系统一件件地处理当操作系统处理一件任务时其他待处理的任务就需要等待虽然所有任务的处理时间不能降低但我们可以安排它们...

通达学院实验报告20xx20xx学年第2学期课程名称数据结构实验名称基本内排序算法的验证和性能比较专业软件工程学生姓名班级学号10003102指导教师陈蕾日期20xx年5月29日南京邮电大学通达学院

实验8快速排序1需求分析1输入的形式和输入值的范围第一行是一个整数n代表任务的件数接下来一行有n个正整数代表每件任务所用的时间中间用空格或者回车隔开不对非法输入做处理及假设用户输入都是合法的2输出的形式输出有n...

问题描述基数排序是采用分配与收集的办法用对多关键码进行排序的思想实现对单关键码进行排序的方法实现多关键码排序有两种常用的方法1最高位优先MSDMostSignificantDigitfirst2最低位优先LSD...

《数据结构》课程设计报告

数据结构实验排序姓名陆孟飞学号1219xx29需求分析本演示程序用C60编写完成排序的实现对输入的一组数字实现不同的排序方法对其由小到大顺序输出1分别对直接插入排序希尔排序冒泡排序快速排序选择排序堆排序算法进行...

封面学生实验报告学院国际经贸学院课程名称数据结构专业班级09电子商务姓名学号学生实验报告经管类专业用一实验目的及要求1目的掌握内排序的方法2内容及要求实验题101编写一个程序实现直接插入排序算法并输出98765...

数据结构课程实验报告注空间不够可以增加页码

一实验内容1Description建立一个顺序表然后在已建好的顺序表上实现顺序表插入和删除等基本操作最后输出最终结果要求TimeLimit1000MSMemoryLimit65536K2egInput有多组测试...

数据结构排序实验报告（34篇）