排序相关算法实现.docx

排序相关算法实现.docx

《排序相关算法实现.docx》由会员分享，可在线阅读，更多相关《排序相关算法实现.docx（13页珍藏版）》请在冰点文库上搜索。

排序相关算法实现

排序相关算法C++实现

一、直接插入排序算法

.cpp部分

#include

#include

#include"insertsort.h"

usingnamespacestd;

intmain（）{

intsize,k;

stringstr;

cout<<"输入比较元素个数:

"<

cin>>size;

element*list=newelement[size+1];

cout<<"输入各关键字值:

"<

for（inti=1;i<=size;i++）{cin>>k;list[i].setkey（k）;}

for（i=1;i<=size;i++）{

cout<<"输入同学姓名:

"<

cin>>str;

list[i].setname（str）;

}

insertsort（list,size）;

print（list,size）;

return0;

}

.h部分

#include

#include

usingnamespacestd;

classelement{

private:

intkey;

stringname;

public:

element（intk=0）{key=k;}

intgetkey（）{returnkey;}

voidsetkey（intk）{key=k;}

stringgetname（）{returnname;}

voidsetname（stringstr）{name=str;}

};

voidinsertsort（element*list,intn）{

inte;

strings;

intk0;

stringss;

cout<<"请设置最小下界k0和下界名:

"<

cin>>k0>>ss;

if（k0>=0）cout<<"k0不合法"<

else{

list[0].setkey（k0）;

list[0].setname（ss）;

inti,j;

for（j=2;j<=n;j++）{

e=list[j].getkey（）;

s=list[j].getname（）;

i=j-1;

while（e

list[i+1].setkey（list[i].getkey（））;

list[i+1].setname（list[i].getname（））;

i--;

}

list[i+1].setkey（e）;

list[i+1].setname（s）;

}

}

};

voidprint（element*list,intn）{

for（inti=1;i<=n;i++）cout<

"<

<

}

二、对半插入排序

.cpp部分

#include

#include"halfsort.h"

usingnamespacestd;

intmain（）{

listslist;

cout<<"最初状态:

"<<"";slist.print（）;

slist.halfinsertsort（slist.getarray（））;

cout<<"现态:

"<<"";

slist.print（）;

return0;

}

.h部分

#include

#include

usingnamespacestd;

classelement{

private:

intkey;

stringname;

public:

element（intk=0）{key=k;}

intgetkey（）{returnkey;}

voidsetkey（intk）{key=k;}

stringgetname（）{returnname;}

voidsetname（stringstr）{name=str;}

};

classlist{

private:

intsize;

element*array;

public:

list（）;

~list（）{cout<<"**谢谢使用**"<

voidhalfinsertsort（elementr[]）;

voidhalfinsert（elementr[],intn）;

voidprint（）;

intgetsize（）{returnsize;}

element*getarray（）{returnarray;}

};

list:

:

list（）{

ints;

cout<<"输入元素数:

"<

cin>>s;

size=s;

array=newelement[size];

cout<<"输入各个元素关键字值:

"<

for（inti=0;i

intk;

cin>>k;

array[i].setkey（k）;

}

cout<<"输入各个元素名字:

"<

for（i=0;i

stringk;

cin>>k;

array[i].setname（k）;

}

}

voidlist:

:

print（）{

for（inti=0;i

"<

cout<

}

voidlist:

:

halfinsert（elementr[],intn）{

inte=r[n].getkey（）;

stringp=r[n].getname（）;

intfront=0,end=n-1;

while（front<=end）{

if（r[n].getkey（）

elsefront=（front+end）/2+1;

}

for（inti=n-1;i>=front;i--）{

r[i+1].setkey（r[i].getkey（））;

r[i+1].setname（r[i].getname（））;

}

r[front].setkey（e）;

r[front].setname（p）;

}

voidlist:

:

halfinsertsort（elementr[]）{

for（intk=1;k

halfinsert（r,k）;

}

三、冒泡排序

.cpp部分

#include

#include

#include"buble.h"

usingnamespacestd;

intmain（）{

intc;

intd;

strings;

cout<<"请输入欲创建数组的大小:

"<

cin>>c;

element*p=newelement[c];

cout<<"请输入"<

"<

for（inti=0;i

cin>>d;

p[i].setkey（d）;

}

cout<<"请输入"<

"<

for（i=0;i

cin>>s;

p[i].setln（s）;

}

intch;

cout<<"选择菜单:

"<

cout<<"1:

输出数组元素:

"<

cout<<"2:

冒泡排序:

"<

cin>>ch;

while（ch!

=-1）{

switch（ch）{

case1:

{for（i=0;i

case2:

{buble（p,c）;

for（i=0;i

break;}

}

cout<<"还需要什么帮助?

"<

cin>>ch;

}

if（ch==-1）cout<<"谢谢使用"<

return0;

}

.h部分

#include

usingnamespacestd;

template

classelement{

private:

intkey;

Tln;

public:

intgetkey（）{returnkey;}

voidsetkey（intk）{key=k;}

Tgetln（）{returnln;}

voidsetln（Tl）{ln=l;}

};

template

voidbuble（elementR[],intn）{

intbound,j,t;

Te1;

inte2;

bound=n;//t来记录一趟冒泡最后交换记录的位置//

while（bound>1）{

t=0;

for（j=0;j

if（R[j].getkey（）>R[j+1].getkey（））{

e1=R[j].getln（）;e2=R[j].getkey（）;

R[j].setln（R[j+1].getln（））;R[j].setkey（R[j+1].getkey（））;

R[j+1].setln（e1）;R[j+1].setkey（e2）;

t=j;

}

}

bound=t+1;//bound应比t大1,当前t所指还有可能变更//

}

}

四、交替冒泡排序

.cpp部分

#include

#include

#include"alternant.h"

usingnamespacestd;

intmain（）{

intc;

intd;

strings;

cout<<"请输入欲创建数组的大小:

"<

cin>>c;

element*p=newelement[c];

cout<<"请输入"<

"<

for（inti=0;i

cin>>d;

p[i].setkey（d）;

}

cout<<"请输入"<

"<

for（i=0;i

cin>>s;

p[i].setln（s）;

}

intch;

cout<<"选择菜单:

"<

cout<<"1:

输出数组元素:

"<

cout<<"2:

交替冒泡排序:

"<

cin>>ch;

while（ch!

=-1）{

switch（ch）{

case1:

{for（i=0;i

case2:

{alternantbuble（p,c）;

for（i=0;i

break;}

}

cout<<"还需要什么帮助?

"<

cin>>ch;

}

if（ch==-1）cout<<"谢谢使用"<

return0;

}

.h部分

#include

usingnamespacestd;

template

classelement{

private:

intkey;

Tln;

public:

intgetkey（）{returnkey;}

voidsetkey（intk）{key=k;}

Tgetln（）{returnln;}

voidsetln（Tl）{ln=l;}

};

template

voidalternantbuble（elementR[],intn）{

intexchange=0,compare=0;

intrising,r;

intdiving,d;

intj,alter=0;

rising=n;

while（diving

Te1;

inte2;

if（alter==0）{

r=0;

for（j=0;j

compare++;

if（R[j].getkey（）>R[j+1].getkey（））{

e1=R[j].getln（）;e2=R[j].getkey（）;

R[j].setln（R[j+1].getln（））;R[j].setkey（R[j+1].getkey（））;

R[j+1].setln（e1）;R[j+1].setkey（e2）;

r=j;

exchange++;

}

}

rising=r+1;

alter=1;//rising应比r大1,当前r所指还有可能变更//

}

if（alter==1）{

d=n;

for（j=rising-1;j>0;j--）{

compare++;

if（R[j].getkey（）>R[j+1].getkey（））{

e1=R[j].getln（）;e2=R[j].getkey（）;

R[j].setln（R[j+1].getln（））;R[j].setkey（R[j+1].getkey（））;

R[j+1].setln（e1）;R[j+1].setkey（e2）;

d=j;

exchange++;

}

}

diving=d;

alter=0;

}

}

cout<<"关键词比较次数:

"<

cout<<"记录移动次数:

"<

}