数据结构 二维码文件第5章主要算法的C++代码.doc

《数据结构 二维码文件第5章主要算法的C++代码.doc》由会员分享，可在线阅读，更多相关《数据结构 二维码文件第5章主要算法的C++代码.doc（9页珍藏版）》请在汇文网上搜索。

1、第5章主要算法的C+代码1插入排序#include using namespace std; #define MAX 100/直接插入排序算法void prints(int a,int n) int i;for(i=0;in;i+)coutai,;coutendl; /直接插入排序void Sinsert_sort(int a ,int n) int i,j,x; cout直接插入排序结果：endl; for(i=1;i=0&xaj; j-) aj+1=aj; aj+1=x; /将x 插在位置j cout第i趟排序结果为：; prints(a,n); /二分插入排序算法void Binsert

2、_sort(int a ,int n) int i,j,left,right,mid,x; cout二分插入排序结果：endl; for(i=1;in;i+) /准备插入ai x=ai; left=0; right=i-1; while(left=right) mid=(left+right)/2; if(x=left;j-) aj+1=aj; aleft=x; /元素ai就位 cout第i趟排序结果为：; prints(a,n); /希尔排序void Shell_sort(int a ,int d ,int n,int t) int i,j,h,k,x; cout希尔排序结果：endl; f

3、or(h=0;ht;h+) k=dh; /当前增量为k for(i=k;i=0&xaj;) aj+k=aj; j-=k; aj+k=x; /x就位 cout第h+1趟排序结果为：; prints(a,n); int main()int i,n,t,a1MAX,a2MAX,a3MAX,dMAX;coutn;cout请输入需要排序的具体整数：;for(i=0;ia1i;a2i=a1i;a3i=a1i;coutt;cout请输入希尔排序排序中的具体增量依次是：;for(i=0;idi;Sinsert_sort(a1,n);Binsert_sort(a2,n);Shell_sort(a3,d,n,t)

4、;return 0;【运行结果参考】插入排序运行结果2交换排序#include using namespace std; #define MAX 100void prints(int a,int n)int i;for(i=0;in;i+)coutai,;coutendl;void bubble_sort(int a ,int n) int i,j,x,flag=1; j=n-2; while(flag) /当数据无序时循环，flag=0时，数据已经有序，退出循环 flag=0; for(i=0;iai+1) x=ai; ai=ai+1; ai+1=x; flag=1; j- ; prints

5、(a,n); void partition(int a ,int s,int t,int &k,int n) int i,j,x; x=as; /取划分元素 i=s; j=t; /扫描指针初值 do /循环地进行划分 while(aj=x)&(ij) j- ; if(ij) ai+=aj; while (aix)&(ij) i+; if(ij) aj-=ai; while(ij); /直到i等于j ai=x; /划分元素就位 k=i; prints(a,n); void qksort(int a ,int i,int j,int n) int k; if(ij) partition(a,i,j

6、,k,n); /划分 qksort(a,i,k-1,n); /递归 qksort(a,k+1,j,n); /递归 int main()int i,n,a1MAX,a2MAX;coutn;cout请输入需要排序的具体整数：;for(i=0;ia1i;a2i=a1i; cout冒泡排序结果：endl;bubble_sort(a1,n); cout快速排序结果：endl; qksort(a2,0,n-1,n); return 0;【运行结果】交换排序运行结果3选择排序#include using namespace std; #define MAX 100void prints(int a,int

7、n)int i;for(i=0;in;i+)coutai,;cout0;k-) i=0; for(j=1;jai) i=j; /选最大元 x=ak;ak=ai;ai=x; /交换ak与ai; prints(a,n); /以某个节点为根节点的子树进行调整，调整为大顶堆void max_heapify(int a,int i,int heapsize) int l=2*i+1; int r=2*i+2; int largest=i; if(lai) largest=l; if(ralargest) largest=r; if(largest!=i) int temp=alargest; alarg

8、est=ai; ai=temp; max_heapify(a,largest,heapsize); /建堆的过程，通过自底向上地调用max_heapify来将一个数组data【1n】/变成一个大顶堆，只需要对除了叶子节点以外的节点进行调整void bulid_max_heap(int a,int heapsize) for(int i=heapsize/2-1;i=0;i-) max_heapify(a,i,heapsize);/堆排序算法实现主体：先用bulid_max_heap将输入数组构造成大顶堆，/然后将data【0】和堆的最后一个元数交换，继续进行调整。void heap_sort(

9、int a,int n) bulid_max_heap(a,n); for(int i=n-1;i0;i-) int t=a0; a0=ai; ai=t; max_heapify(a,0,i); prints(a,n); int main()int i,n,a1MAX,a2MAX;coutn;cout请输入需要排序的具体整数：;for(i=0;ia1i;a2i=a1i;cout直接选择排序结果：endl;simpl_sort(a1,n);cout堆排序结果：endl;heap_sort(a2,n);return 0;选择排序运行结果4合并排序#include using namespace s

10、td;#define MAX 100void prints(int a,int n)int i;for(i=0;in;i+)coutai,;coutendl;/有序段合并函数void merge(int a ,int p,int q,int s,int t) int i,j,k,bMAX; i=p, j=s, k=p-1; while(i=q)&(j=t) if(ai=aj) b+k=ai+; else b+k=aj+; while(i=q) b+k=ai+; while(j=t) b+k=aj+; for(i=p;i=t;i+)ai=bi; /递归的合并排序算法 void merge_sor

11、t(int a ,int i,int j,int n) int k; if(ij) k=(i+j)/2; merge_sort(a,i,k,n); merge_sort(a,k+1,j,n); merge(a,i,k,k+1,j); /非递归的合并排序算法 void merge2(int a ,int b ,int p,int s,int t) int i,j,k; i=p, j=s+1, k=p; while(i=s)&(j=t) if(ais) for(int z=j;z=t;z+) bk+=az;elsefor(int z=i;z=s;z+)bk+=az; /控制一遍合并的扫描函数 vo

12、id scan(int t,int a ,int b ,int n) int p,q,r; p=0; while(pn-1) q=n-1; /限制语句 if(rn-1) r=n-1; merge2(a,b,p,q,r); / 合并两段 p=r+1; /非递归的合并排序void merge_sort_2(int a ,int n) int bMAX, t ; t=1; /有序段标准长度t初值为1 while(tn) scan(t,a,b,n); /从 a 合并到 b prints(a,n); scan(2*t,b,a,n); /从 b 合并到 a t=4*t; / t 扩大4倍 prints(a,n); int main()int i,n,a1MAX,a2MAX;coutn;cout请输入需要排序的具体整数：;for(i=0;ia1i;a2i=a1i;cout递归合并排序结果：endl;merge_sort(a1,0,n-1,n);cout非递归合并排序结果：endl;merge_sort_2(a2,n);return 0;【运行结果】合并排序运行结果