排序相关算法实现.docx

1、排序相关算法实现排序相关算法C+实现一、直接插入排序算法.cpp部分#include#include#includeinsertsort.husing namespace std;int main() int size,k; string str; cout输入比较元素个数:size; element * list=new elementsize+1; cout输入各关键字值:endl; for(int i=1;ik;listi.setkey(k); for(i=1;i=size;i+) cout输入同学姓名:str; listi.setname(str); insertsort(list,

2、size); print(list,size); return 0;.h部分#include#includeusing namespace std;class elementprivate: int key; string name;public: element(int k=0)key=k; int getkey()return key; void setkey(int k)key=k; string getname()return name; void setname(string str)name=str;void insertsort(element * list,int n) int

3、 e; string s; int k0; string ss; cout请设置最小下界k0和下界名:k0ss; if(k0=0)coutk0不合法endl; else list0.setkey(k0); list0.setname(ss); int i,j; for(j=2;j=n;j+) e=listj.getkey(); s=listj.getname(); i=j-1; while(elisti.getkey() listi+1.setkey(listi.getkey(); listi+1.setname(listi.getname(); i-; listi+1.setkey(e);

4、listi+1.setname(s); ;void print(element * list,int n) for(inti=1;i=n;i+)coutlisti.getname():listi.getkey()endl;二、对半插入排序.cpp部分#include#includehalfsort.husing namespace std;int main() list slist; cout最初状态: ;slist.print(); slist.halfinsertsort(slist.getarray(); cout现态: ;slist.print(); return 0;.h部分#inc

5、lude#includeusing namespace std;class elementprivate: int key; string name;public: element(int k=0)key=k; int getkey()return key; void setkey(int k)key=k; string getname()return name; void setname(string str)name=str;class listprivate: int size; element * array;public: list(); list()cout*谢谢使用*endl;

6、void halfinsertsort(element r); void halfinsert(element r,int n); void print(); int getsize()return size; element * getarray()return array;list:list() int s; cout输入元素数:s; size=s; array= new elementsize; cout输入各个元素关键字值:endl; for(int i=0;ik; arrayi.setkey(k); cout输入各个元素名字:endl; for(i=0;ik; arrayi.setn

7、ame(k); void list: print() for(int i=0;isize;i+)coutarrayi.getname():arrayi.getkey() ; coutendl;void list:halfinsert(element r,int n) int e=rn.getkey(); string p=rn.getname(); int front=0,end=n-1; while(front=end) if(rn.getkey()=front;i-) ri+1.setkey(ri.getkey(); ri+1.setname(ri.getname(); rfront.se

8、tkey(e); rfront.setname(p);void list:halfinsertsort(element r) for(int k=1;ksize;k+) halfinsert(r,k);三、冒泡排序.cpp部分#include#include#includebuble.husing namespace std;int main() int c; int d; string s; cout请输入欲创建数组的大小:c; element * p=new elementc; cout请输入c个关键字数据:endl; for(int i=0;id; pi.setkey(d); cout请

9、输入c个数值域数据:endl; for(i=0;is; pi.setln(s); int ch; cout选择菜单:endl; cout1:输出数组元素:endl; cout2:冒泡排序:ch; while(ch!=-1) switch(ch) case 1:for(i=0;ic;i+)coutpi.getln() ;break; case 2:buble(p,c); for(i=0;ic;i+)coutpi.getln() ; break; cout还需要什么帮助?ch; if(ch=-1)cout谢谢使用endl; return 0;.h部分#includeusing namespace

10、std;templateclass elementprivate: int key; T ln;public: int getkey()return key; void setkey(int k)key=k; T getln()return ln; void setln(T l)ln=l;templatevoid buble(element R,int n) int bound, j,t; T e1; int e2; bound=n; /t来记录一趟冒泡最后交换记录的位置/ while(bound1) t=0; for(j=0;jRj+1.getkey() e1=Rj.getln();e2=R

11、j.getkey(); Rj.setln(Rj+1.getln(); Rj.setkey(Rj+1.getkey(); Rj+1.setln(e1);Rj+1.setkey(e2); t=j; bound=t+1;/bound 应比t 大1,当前t所指还有可能变更/ 四、交替冒泡排序.cpp部分#include#include#includealternant.husing namespace std;int main() int c; int d; string s; cout请输入欲创建数组的大小:c; element * p=new elementc; cout请输入c个关键字数据:en

12、dl; for(int i=0;id; pi.setkey(d); cout请输入c个数值域数据:endl; for(i=0;is; pi.setln(s); int ch; cout选择菜单:endl; cout1:输出数组元素:endl; cout2:交替冒泡排序:ch; while(ch!=-1) switch(ch) case 1:for(i=0;ic;i+)coutpi.getln() ;break; case 2:alternantbuble(p,c); for(i=0;ic;i+)coutpi.getln() ; break; cout还需要什么帮助?ch; if(ch=-1)c

13、out谢谢使用endl; return 0;.h部分#includeusing namespace std;templateclass elementprivate: int key; T ln;public: int getkey()return key; void setkey(int k)key=k; T getln()return ln; void setln(T l)ln=l;templatevoid alternantbuble(element R,int n) int exchange=0,compare=0; int rising, r; int diving, d; int

14、j,alter=0; rising=n; while(divingrising) T e1; int e2; if(alter=0) r=0; for(j=0;jRj+1.getkey() e1=Rj.getln();e2=Rj.getkey(); Rj.setln(Rj+1.getln(); Rj.setkey(Rj+1.getkey(); Rj+1.setln(e1);Rj+1.setkey(e2); r=j; exchange+; rising=r+1; alter=1; /rising 应比r大1,当前r所指还有可能变更/ if(alter=1) d=n; for(j=rising-1;j0;j-) compare+; if(Rj.getkey()Rj+1.getkey() e1=Rj.getln();e2=Rj.getkey(); Rj.setln(Rj+1.getln(); Rj.setkey(Rj+1.getkey(); Rj+1.setln(e1);Rj+1.setkey(e2); d=j; exchange+; diving=d; alter=0; cout关键词比较次数:compareendl; cout记录移动次数:exchangeendl;