《数据结构实验源程序》由会员分享，可在线阅读，更多相关《数据结构实验源程序（13页珍藏版）》请在金锄头文库上搜索。
1、/共 n-1 趟排序/判断是否存在逆序/查找、后移/插入移动次数为vvmovevvendl;本人为北邮通信工程专业2011 级本科生，此程序为本人原创，编译通过，结果正确。排序实验：#include#include using namespace std;int c1=0;int m1=0;int c2=0;int m2=0;int c3=0;int m3=0;/直接插入排序void InsertSort(int r,int n)int j;int key;int cmp=0;int move=0;for(int i=1;in;i+)if(riri-1)key=ri;for(j=i-1;key
2、rj;j-)rj+1=rj;move+;cmp+;cmp+;rj+1=key;move+;elsecmp+;cout比较次数为cmp=1;d=d/2)/以 d 为分量划分子集for(int i=d;in;i+)/每个元素进行一趟希尔排序，共 n-d 趟if(ri=0&keyrj;j=j-d)/在子集中查找、后移、插入rj+d=rj;move+;cmp+;cmp+;rj+d=key;move+;elsecmp+;cout比较次数为vvcmpvv1移动次数为moveendl;/冒泡排序(改进过后的)void BubbleSort(int r,int n)int key;int pos=n-1;定义
3、变量pos标记上一次交换发生的位置int cmp=0;int move=0;while(pos!=0)int bound=pos;/本次排序停止比较的位置为上一次交换发生的位置pos=0;for(int i=0;iri+1)比较、交换、重新给pos赋值key=ri;ri=ri+1;ri+1=key;pos=i;move+=3;cmp+;cout比较次数为vvcmpvv1移动次数为moveendl;/快速排序(改进过后的)int Partion(int r,int i,int j)/快速排序一趟排序int pivot=ri;/确定轴值为最左侧的元素while(ij)while(i=pivot)j
4、-;c1+;if(ij)c1+;ri=rj;m1+=3;while(ij)&(ri=pivot)i+;c1+;if(ij)c1+;rj=ri;m1+=3;ri=pivot;return i;void QSort(int r,int i,int j)/右侧扫描/左侧扫描/完整的快速排序（递归）/共 n-1 趟排序/假设这一趟排序中最左面的元素最小/找到这一趟排序中最小的元素/交换移动次数为vvmovevvendl;/筛选if(ij)int pivotloc=Partion(r,i,j);QSort(r,i,pivotloc-1);QSort(r,pivotloc+1,j);/简单选择排序void
5、 SelectSort(int r,int n)int key;int cmp=0;int move=0;for(int i=0;in-1;i+)int index=i;for(int j=i+1;jn;j+)if(rjrindex)index=j;cmp+;if(index!=i)key=ri;ri=rindex;rindex=key;move+=3;cout比较次数为cmp/小根堆的堆排序void Sift(int r,int k,int m)int key;int i=k;i为要师选的点，j为其左孩子int j;if(i=0)j=1;elsej=2*i;while(j=m)/选出左右孩子
6、中较小的一点if(jrj+1)j+;c2+;if(ri=0;i-) Sift(r,i,n-1);/若符合小根堆条件，则结束/若不符合，则交换根节点与左右孩子中较小的那个，并/完整的堆排序/从后往前建立堆，以此来保证满足小根堆条件cout排序后的数组为：vvendl;for(int i=0;in;i+)coutvvr0vv ;/输出堆顶元素之后将其与堆的最后一个元素交换位置，进行下一次筛选，下一次筛选范围不包括此次筛选的最后一个位置key1=r0;r0=rn-1-i;rn-1-i=key1;m2+=3;Sift(r,0,n-2-i);coutvvendl;cout比较次数为匕“?*1移动次数为m
7、2endl;/归并排序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(rirj)比较 ri与 rj,将较小的写进 r1kr1k+=ri+;elser1k+=rj+;c3+; if(i=m)进 r1m3+;/一个数列全部写进r1后将另一个数列剩下的元素都写while(i=m)r1k+=ri+;m3+;if(j=t)while(j=t)r1k+=rj+;m3+;void MergePass(int r,int r1,int n,int h) int i=0;/若存在两个以上的长
8、度为 h 的/若两个子序列一个长度小于 h，若只有一个长度小于等于h的while(in-2*h+1) 子序列,则两个序列进行归并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-1);else子序列，则直接写进r1for(;in;i+)r1i=ri;m3+;/子序列初始长度为一，每次归并后h*2/当 hn 时进行归并，每次归并后将 r1void MergeSort(int r,int r1,int n) int h=1;while(hn) 的内容复制到 r1MergePass(r,r1,n,h);
9、 h=2*h;for(int i=0;in;i+)ri=r1i; m3+; /* void main()intr130=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30; /正序数据intr230=30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1; /逆序数据intr330=3,26,7,24,29,15,6,19,25,4,5,18,20,21,2,13,23,1,30,
10、14,17,8,16,22,12,9,10,27,28,11; /随机数据int r1130,r1230;int r2130,r2230,r2330,r2430,r2530,r2630,r27130,r27230;int r3130,r3230,r3330,r3430,r3530,r3630,r37130,r37230;for(int i=0;i30;i+)r11i=r12i=r1i;for(int i=0;i30;i+)r21i=r22i=r23i=r24i=r25i=r26i=r271i=r272i=r2i;for(int i=0;i30;i+) r31i=r32i=r33i=r34i=r35i=r36i=r371i=r372i=r3i;cout 正序数据排序endl;for(int i=0;i30;i+)coutr1i ;coutendlendl;cout1、直接插入排序endl;InsertSort(r1,30);cout排序后的数组为：endl;for(int i=0;i30;i+)coutr1i ;coutendlendl;cout2、希尔排序endl;ShellInsert(r1,30);cout排序后的数组为：endl;for(int i=0;i30;i+)coutr1i ;coutendlendl;cout3、冒泡排序endl;BubbleSort(r1,3
