实验6：至少三种排序算法的程序实现

《数据结构与算法》课程实验报告（6）实验题目：实验6：至少三种排序算法的程序实现一、实验目的1．掌握简单插入排序、希尔排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。2．对各种查找、排序技术的时间、空间复杂性有进一步认识。二、实验要求1．认真阅读和掌握和本实验相关的教材内容。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容编写程序实现下述六种算法至少三种，并用以下无序序列加以验证：49，38，65，97，76，13，27，491．简单插入排序2．希尔排序3.冒泡排序4．快速排序5．归并排序6．堆排序四、源代码与结果：1、简单插入排序：源代码：#includeiostream.hvoidInsertSort(intr[],intn);intmain(){intr[]={49,38,65,97,76,13,27,49};cout直接插入排序:endl;InsertSort(r,8);for(inti=0;i8;i++){coutr[i]'\t';}coutendl;return0;}voidInsertSort(intr[],intn){for(inti=1;in;i++){for(intj=i-1,s=r[i];sr[j]&&j=0;j--){r[j+1]=r[j];}r[j+1]=s;}}运行结果：2．希尔排序：#includeiostream.hvoidShellSort(intr[],intn);intmain(){intr[]={49,38,65,97,76,13,27,49};cout希尔排序:endl;ShellSort(r,8);for(inti=0;i8;i++){coutr[i]'\t';}coutendl;return0;}voidShellSort(intr[],intn){intstep=n/2;while(step=1){for(inti=step;in;i+=step){for(intj=i-step,s=r[i];sr[j]&&j=0;j-=step){r[j+step]=r[j];}r[j+step]=s;}step/=2;}}运行结果：3、冒泡排序：源代码：//起泡法排序：#includeiostream.h#defineN8//N为数的总个数voidBubbleSort(intr[],intn);intmain(){inti;inta[N];cout请输入N个数字：;for(i=0;iN;i++){cina[i];}cout冒泡排序结果:endl;BubbleSort(a,N);for(i=0;iN;i++){couta[i]\t;}coutendl;return0;}voidBubbleSort(intr[],intn){for(inti=0;in-1;i++)//进行n-1次循环，实现n-1趟比较{for(intj=0;jn-1-i;j++)//在每一趟中进行n-1-i次比较{if(r[j]r[j+1]){inttemp=r[j];r[j]=r[j+1];r[j+1]=temp;}}}}运行结果：4、快速排序：#includeiostream.hintPartition(intr[],intlow,inthigh);voidQuickSort(intr[],intlow,inthigh);intmain(){intr[]={49,38,65,97,76,13,27,49};cout快速排序:endl;QuickSort(r,0,10-1);for(inti=0;i10;i++){coutr[i]\t;}coutendl;return0;}intPartition(intr[],intlow,inthigh){intpivotkey=r[low];inti=low;intj=high;while(ij){while(ij&&r[j]pivotkey)j--;if(ij){r[i]=r[j];i++;}while(ij&&r[i]pivotkey)i++;if(ij){r[j]=r[i];j--;}}r[j]=pivotkey;returnj;}voidQuickSort(intr[],intlow,inthigh){if(lowhigh){intpivot=Partition(r,low,high);QuickSort(r,low,pivot-1);QuickSort(r,pivot+1,high);}}运行结果：五、思考与提高1．设有1000个无序的元素，希望用最快的速度挑出其中前10个最大的元素，采用哪一种排序方法最好？为什么？答：用堆排序最合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)；若用冒泡排序则需时n!/(n-10)!