还剩10页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构与算法》课程实验报告
(6)实验题目实验6至少三种排序算法的程序实现
一、实验目的
1.掌握简单插入排序、希尔排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用
2.对各种查找、排序技术的时.间、空间复杂性有进一步认识
二、实验要求
1.认真阅读和掌握和本实验相关的教材内容
2.编写完整程序完成下面的实验内容并上机运行
3.整理并上交实验报告
三、实验内容编写程序实现下述六种算法至少三种,并用以下无序序列加以验证49,38,65,97,76,13,27,
491.简单插入排序
2.希尔排序
3.冒泡排序
4.快速排序
5.归并排序return j;void Quicksortint r[],int low,int highiflowhighintpivot=Partitionr,low,high;Quicksort r,low,pivot-1;Quicksort r,pivol+l,high;运行结果:快速排序
五、思考与提高I.设有1000个无序的元素,希望用最快的速度挑出其中前10个最大的元素,采用哪一种排序方法最好?为什么?答用堆排序最合适,因为不必等全部元索排完就能得到所需结果,时间效率为0nlog2n;若用冒泡排序则需时n!/n-10!
6.堆排序
四、源代码与结果
1、简单插入排序源代码#includeiostream.hvoid InsertSortint r[],int n;int mainOintr[]={49,38,65,97,76,13,27,49};cout〈,直接插入排序:,,«endl;InsertSort r,8;forint i=0;i8;i++cout«r[i]«,\t;coutcndl;return0;void InsertSortintr[],int nforint i=l;i〈n;i++for int j=i-l,s=r[i];sr[j]j=O;j-r[j+l]=r[j];r[j+l]=s;运行结果瘴接插入排序Press anykey tocontinue
2.希尔排序:#includeiostream.hvoid ShellSortintr[],int n;int mainintr[]={49,38,65,97,76,13,27,49};cout〃希尔排序:/z«endl;ShellSortr,8;forint i=0;i8;i++coutr[i]*W;cout«endl;return0;}void ShellSortintr[],int nintstep=n/2;whilestep=1forini i=step;in;i+=stepforint j=i-step,s=r[i];sr[j]j=0;j-=stepr[j+step]=r[j];}r[j+step]=s;step/=2;运行结果怖■尔排序13273849Press anykey tocontinue
496576973、冒泡排序:源代码〃起泡法排序:#includeiostream.h#define N8//N为数的总个数void BubbleSortintr[],int n;int mainOint i;int a[N];cout〈〃请输入上N〃个数字〃;fori=0;iN;i++cina[i];cout〃冒泡排序结果〃cndl;BubbleSort a,N;fori=0;iN;i++cout«endl;return0;void BubbleSortintr[],int nforinti=0;in-l;i++〃进行nT次循环,实现nT趟比较forinl j=0;jn-l-i;J++〃在每一趟中进行n-l-i次比较ifr[j]r[j+l]int temper[j];r[j]=r[j+l];r[j+l]=temp;运行结果:327384949657697ress anykey tocontinue.
4、快速排序#includeiostrcam.hint Partitionintr[],int low,int high;void Quicksortintr[],int low,int high;int mainintr[]={49,38,65,97,76,13,27,49};cout〈”快速排序:,zendl;Quicksortr,0,10-l;forint i=0;i10;i++cout«endl;return0;}int Partitionintr[],int low,int highintpivotkey=r[low];inti=low;intj=high;whileijwhileijr[j]pivotkey j-;ifij{r[i]=r[j];i++;}whileijr[i]pivotkey i++;ifij{r[j]=r[i];j—;r[j]=pivotkey;。