数据结构实验报告——排序.docx

1实验要求【实验目的】 学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。【实验内容】使用简单数组实现下面各种排序算法，并进行比较。排序算法： 1、插入排序 2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。2. 程序分析2.1 存储结构 存储结构：数组r1r2 ri-1 ri ri+1 rn有序区 无序区 图8-1 直接插入排序的基本思想图解插入到合适位置2.2 关键算法分析/插入排序void InsertSort(int r, int n)int count1=0,count2=0;for (int i=2; in; i+) r0=ri; /设置哨兵for (int j=i-1; r0rj; j-) /寻找插入位置rj+1=rj; /记录后移rj+1=r0;count1+;count2+;for(int k=1;kn;k+)coutrk ;coutendl;cout比较次数为 count1 移动次数为 count2=1; d=d/2) /以增量为d进行直接插入排序for (i=d+1; i0 & r0rj; j=j-d)rj+d=rj; /记录后移d个位置rj+d=r0;count1+;count2=count2+d;count1+;for(i=1;in;i+)coutri ;coutendl;cout比较次数为 count1 移动次数为 count2endl;r1r2 ri-1 ri ri+1 rn有序区 无序区 图8-1 直接插入排序的基本思想图解插入到合适位置/起泡排序void BubbleSort(int r, int n)int temp;int exchange;int bound;int count1=0,count2=0; exchange=n-1; /第一趟起泡排序的范围是r1到rnwhile (exchange) /仅当上一趟排序有记录交换才进行本趟排序bound=exchange; exchange=0; for(int j=0;jrj+1) temp=rj;/交换rj和rj+1rj=rj+1;rj+1=temp;exchange=j;/记录每一次发生记录交换的位置count2=count2+3;/移动了3次for(int i=1;in;i+)coutri ;coutendl;cout比较次数为 count1 移动次数为 count2endl;/快速排序一次划分int Partition(int r, int first, int end,int &count1,int &count2)int i=first; /初始化 r1 ri-1 ri ri+1 rn 均ri 轴值 均ri 位于最终位置 图8-6 快速排序的基本思想图解int j=end;int temp; while (ij) while (ij & ri= rj)j-; /右侧扫描count1+;count1+;if (ij) temp=ri; /将较小记录交换到前面ri=rj;rj=temp;i+; count2=count2+3;while (ij & ri= rj) i+; /左侧扫描count1+;count1+;if (ij)temp=rj;rj=ri;ri=temp; /将较大记录交换到后面j-; count2=count2+3; return i; /i为轴值记录的最终位置/快速排序void QuickSort(int r, int first, int end,int &count1,int &count2)if (firstend) /递归结束int pivot=Partition(r, first, end,count1,count2); /一次划分QuickSort(r, first, pivot-1,count1,count2);/递归地对左侧子序列进行快速排序QuickSort(r, pivot+1, end,count1,count2); /递归地对右侧子序列进行快速排序r1 r2 ri-1 ri ri+1 rmin rn 有序区 无序区 已经位于最终位置 rmin为无序区的最小记录 图8-9 简单选择排序的基本思想图解交换/简单选择排序void SelectSort(int r , int n) int i;int j;int index;int temp;int count1=0,count2=0; for (i=0; in-1; i+) /对n个记录进行n-1趟简单选择排序 index=i; for(j=i+1;jn;j+)/在无序区中选取最小记录count1+;/比较次数加一 if(rjrindex)/如果该元素比现在第i个位置的元素小index=j;count1+;/在判断不满足循环条件jn时，比较了一次 if(index!=i) temp=ri;/将无序区的最小记录与第i个位置上的记录交换 ri=rindex; rindex=temp;count2=count2+3;/移动次数加3 for(i=1;in;i+)coutri ;coutendl; cout比较次数为 count1 移动次数为 count2endl;/筛选法调整堆void Sift(int r,int k,int m,int &count1,int &count2)/s，t分别为比较和移动次数int i;int j;int temp;i=k; j=2*i+1; /置i为要筛的结点，j为i的左孩子while(j=m)/筛选还没有进行到叶子if(jm & rjrj)break;/根结点已经大于左右孩子中的较大者else temp=ri; ri=rj; rj=temp;/将根结点与结点j交换 i=j; j=2*i+1;/下一个被筛结点位于原来结点j的位置count2=count2+3;/移动次数加3/堆排序void HeapSort(int r,int n) int count1=0,count2=0;/计数器，计比较和移动次数int i;int temp;for(i=n/2;i=0;i-)/初始建堆，从最后一个非终端结点至根结点Sift(r,i,n,count1,count2) ; for(i=n-1; i0; i-)/重复执行移走堆顶及重建堆的操作temp=ri;/将堆顶元素与最后一个元素交换ri=r0;r0=temp;/完成一趟排序，输出记录的次序状态Sift(r,0,i-1,count1,count2);/重建堆for(i=1;in;i+)coutri ;coutendl;cout比较次数为 count1 移动次数为 count2endl;/一次归并void Merge(int r, int r1, int s, int m, int t)int i=s;int j=m+1;int k=s;while (i=m & j=t) if (ri=rj) r1k+=ri+; /取ri和rj中较小者放入r1kelse r1k+=rj+; if (i=m) while (i=m) /若第一个子序列没处理完，则进行收尾处理 r1k+=ri+; else while (j=t) /若第二个子序列没处理完，则进行收尾处理 r1k+=rj+; /一趟归并void MergePass(int r , int r1 , int n, int h)int i=0;int k;while (i=n-2*h) /待归并记录至少有两个长度为h的子序列Merge(r, r1, i, i+h-1, i+2*h-1); i+=2*h;if (in-h) Merge(r, r1, i, i+h-1, n); /待归并序列中有一个长度小于helse for (k=i; k=n; k+) /待归并序列中只剩一个子序列 r1k=rk;/归并排序void MergeSort(int r , int r1 , int n ) int h=1;int i;while (hn)MergePass(r, r1, n-1, h); /归并h=2*h;MergePass(r1, r, n-1, h);h=2*h;for(i=1;in;i+)coutri ;coutendl;void Newarray(int a,int b,int c)cout新随机数组：;c0=0;a0=0;b0=0;for(int s=1;s11;s+)as=s;bs=20-s;cs=rand()%50+1;coutcs ;coutendl;2.3 其他排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)希尔排序O(nlog2n)O(n2)O(n1.3)O(n2)O(1)起泡排序O(n2)O (n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n) O(n)简单选择排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O (nlog2n)O(1)归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)3. 程序运行结果 void main()srand(time(NULL);const int num=11; /赋值int anum;int bnum;int cnum;int c1num;c0=0;a0=0;b0=0;Newarray(a,b,c);cout顺序数组：;for(int j=1;jnum;j+)coutaj ;coutendl;cout逆序数组：;for(j=1;jnum;j+)coutbj ;coutendl;coutendl;cout插入排序结果为：n;InsertSort(a,num);InsertSort(b,num);InsertSort(c,num);coutendl;Newarray(a,b,c);cout希尔排序结果为：n;ShellSort(a, num);ShellSort(b, num);ShellSort(c, num);coutendl;Newarray(a,b,c);cout起泡排序结果为：n;BubbleSort(a, num);BubbleSort(b, num);BubbleSort(c, num);coutendl;int count1=0,count2=0;Newarray(a,b,c);cout快速排序结果为：n;QuickSort(a,0,num-1,count1,count2);for(int i=1;inum;i+)coutai ;coutendl;cout比较次数为 count1 移动次数为 count2endl;count1=0,count2=0;QuickSort(b,0,num-1,count1,count2);for(i=1;inum;i+)coutbi ;coutendl;cout比较次数为 count1 移动次数为 count2endl;count1=0,count2=0;QuickSort(c,0,num-1,count1,count2);for(i=1;inum;i+)coutci ;coutendl;cout比较次数为 count1 移动次数为 count2endl;coutendl;coutendl;Newarray(a,b,c);cout 简单选择排序