《数据结构》实验报告

实验七：排序

一．我的实验选题：排序算法

二．实验主要内容和目的：

将输入的n个数用插入排序、快速排序、选择排序分别重新排列成按一个数据元素某个项值有序的序列。

本实验的目的在于：对于每一种排序，要深刻理解它的思想，熟练掌握排序过程，时间和空间复杂度，最好情况和最坏情况，稳定性如何，适用于什么样的初始序列。掌握重要排序的算法和排序过程，插入排序，快速排序，选择排序。

三．概要设计：

（主要模块及相互关系）

一个“输入”模块，完成数据的输入建立；

一个“输出”模块，完成对数据序列的输出；

三个“排序”模块，分别完成对数据序列的三种排序；

主函数Main完成对上述五个模块的调用。

四．运用的存储结构说明：

scanf("%d",&list[i])；

五．主要算法及相关函数功能、参数说明：

voidInputData(intlist[],intn)/*数据输入。*/

voidOutputData(intlist[],intn)/*数据输出*/

voidInsertSort(intlist[],intn)/*直接插入排序算法*/

voidQuickSort(intlist[],intstart,intend,intn)/*快速排序算法*/

voidBubblessort(intlist[],intn)/*冒泡算法*/

六．在设计和调试程序时我遇到的主要问题及其解决方案：

遇到的问题：第一个排序算法对输入数据排序后，后两个排序所要排的序列已拍好。

解决的方案：又定义了两个数组，将输入的数据分别复制到另外两个数组，对三个数组的相同数据序列用三个排序算法排序。

七．程序运行结果截图：

（应当给出不少于三次的运行结果，以便从不同角度来观察分析。图不要太大，最好根据内容剪裁后再粘贴）

实验结论：实验成功

八．我对本次实验的总结：

直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已经排好的序列中，从而得到新的有序表。快速排序是通过一趟排序将待排记录分成俩个部分，其中一部分的关键字比另一个部分的关键字小，如此下去继续排列，达到有序。冒泡算法是通过相邻元素之间的比较和交换使排序码较大的元素逐渐的向有序列的尾部移动。

九．附录：

#include<stdio.h>

#defineMAX50

voidInputData(intlist[],intn)

{

printf("inputdata:/n");

for(inti=0;i<n;i++)

scanf("%d",&list[i]);

}

voidOutputData(intlist[],intn)

{

printf("/nthecurrentsoringis:");

for(intk=0;k<n;k++)

printf("%4d",list[k]);

}

voidInsertSort(intlist[],intn)

{

inti,j;

inttemp;

for(i=0;i<n;i++)

{

temp=list[i];

j=i-1;

while(temp<list[j])

{

list[j+1]=list[j];

j--;

}

list[j+1]=temp;

OutputData(list,n);

}

}

voidQuickSort(intlist[],intn)

{

inti=start;

intj=end;

inttemp;

intvalue=list[start];

if(start<end)

{

do

{

while(i<=end&&list[i]<=value)i++;

while(j>start&&list[j]>=value)j--;

if(i<j)

{

temp=list[i];

list[i]=list[j];

list[j]=temp;

}

}while(i<j);

temp=list[start];

list[start]=list[j];

list[j]=temp;

OutputData(list,n);

QuickSort(list,start,j-1,j+1,end,n);

}

}

voidBubblessort(intlist[],intn)

{

inti,j,k;

for(i=0;i<n;i++)

{

for(j=n-1;j>i;j--)

if(list[j]<list[j-1])

{k=list[j];

list[j]=list[j-1];

list[j-1]=k;

OutputData(list,n);

}

}

}

}

voidmain()

{

intnum;

intlist[MAX];

printf("inputlengthofthelist(n<50):/n");

scanf("%d",&num);

InputData(list,num);

intlist1[MAX],list2[MAX];

for(inti=0;i<num;i++)

list2[i]=list1[i]=list[i];

printf("直接插入排序：");

InsertSort(list,num);

printf("/n快速排序：");

QuickSort(list1,num-1,num);

printf("/n选择排序：");

SelectSort(list2,num);

printf("/n");

}