《实验6至少三种排序算法的程序实现.docx》由会员分享，可在线阅读，更多相关《实验6至少三种排序算法的程序实现.docx（5页珍藏版）》请在三一办公上搜索。
1、实验6至少三种排序算法的程序实现数据结构与算法课程实验报告 实验题目：实验6：至少三种排序算法的程序实现 一、 实验目的 1掌握简单插入排序、希尔排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。 2对各种查找、排序技术的时间、空间复杂性有进一步认识。 二 、实验要求 1认真阅读和掌握和本实验相关的教材内容。 2编写完整程序完成下面的实验内容并上机运行。 3整理并上交实验报告。 三、实验内容 编写程序实现下述六种算法至少三种，并用以下无序序列加以验证：49，38，65，97，76，13，27，49 1简单插入排序 2希尔排序 3. 冒泡排序 4快速排序 5归并排序 6堆排序 四、源
2、代码与结果： 1、简单插入排序： 源代码： #include void InsertSort(int r,int n); int main int r=49,38,65,97,76,13,27,49; cout直接插入排序:endl; InsertSort(r,8); for(int i=0;i8;i+) coutrit; coutendl; return 0; void InsertSort(int r,int n) for(int i=1;in;i+) for(int j=i-1,s=ri;s=0;j-) rj+1=rj; rj+1=s; 运行结果： 2希尔排序： #include voi
3、d ShellSort(int r,int n); int main int r=49,38,65,97,76,13,27,49; cout希尔排序:endl; ShellSort(r,8); for(int i=0;i8;i+) coutrit; cout= 1) for(int i=step;in;i+=step) for(int j=i-step,s=ri;s=0;j-=step) rj+step=rj; rj+step=s; step/=2; 运行结果： 3、冒泡排序： 源代码： /起泡法排序： #include #define N 8 /N为数的总个数 void BubbleSort
4、(int r,int n); int main int i; int aN; cout请输入N个数字：; for(i=0;iai; cout冒泡排序结果:endl; BubbleSort(a,N); for(i=0;iN;i+) coutait; coutendl; return 0; void BubbleSort(int r,int n) for(int i=0;in-1;i+) /进行n-1次循环，实现n-1趟比较 for(int j=0;jrj+1) int temp=rj; rj=rj+1; rj+1=temp; 运行结果： 4、快速排序： #include int Partitio
5、n(int r,int low,int high); void QuickSort(int r,int low,int high); int main int r=49,38,65,97,76,13,27,49; cout快速排序:endl; QuickSort(r,0,10-1); for(int i=0;i10;i+) coutrit; coutendl; return 0; int Partition(int r,int low,int high) int pivotkey=rlow; int i=low; int j=high; while(ij) while(ipivotkey) j
6、-; if(ij)ri=rj;i+; while(ij & ripivotkey) i+; if(ij)rj=ri;j-; rj=pivotkey; return j; void QuickSort(int r,int low,int high) if(lowhigh) int pivot=Partition(r,low,high); QuickSort(r,low,pivot-1); QuickSort(r,pivot+1,high); 运行结果： 五、思考与提高 1设有1000个无序的元素，希望用最快的速度挑出其中前10个最大的元素，采用哪一种排序方法最好？为什么？ 答：用堆排序最合适，因为不必等全部元素排完就能得到所需结果， 时间效率为O(nlog2n)；若用冒泡排序则需时n!/(n-10)!
