数据结构实验 排序算法效率比较平台.docx

数据结构实验 排序算法效率比较平台.docx

《数据结构实验 排序算法效率比较平台.docx》由会员分享，可在线阅读，更多相关《数据结构实验 排序算法效率比较平台.docx（15页珍藏版）》请在冰点文库上搜索。

数据结构实验排序算法效率比较平台

《数据结构》课程实验

实验报告

题目：

内部排序算法效率比较平台的设计与实现

专业：

计算机科学与技术

班级：

姓名：

学号：

完成日期：

一、试验内容

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。

设计和实现内部排序算法效率比较平台，通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观的感受。

二、试验目的

掌握多种排序方法的基本思想，如直接插入、冒泡、简单选择、快速、堆、希尔排序等排序方法，并能够用高级语言实现。

三、源程序代码

#include

#include

#include

#definele100

structpoint

{

charkey[11];

};

//冒泡法

voidmaopao（pointc[]）

{

pointa,b[le];

inti,j,jh=0,bj=0,q;

for（i=0;i

b[i]=c[i];

};

for（i=0;i

for（j=le-1;j>i;j--）{

bj=bj+1;q=strcmp（b[i].key,b[j].key）;

if（q==1）{

a=b[i];

b[i]=b[j];

b[j]=a;

jh=jh+3;

};

};

};

cout<<"冒泡法:

"<

"<

for（i=0;i

cout<

};

cout<

};

//直接插入排序

voidzhijiecharu（pointc[]）

{

pointb[le+1];

inti,j,jh=0,bj=0,q;

for（i=0;i

b[i+1]=c[i];

};

for（i=2;i<=le+1;i++）{

q=strcmp（b[i].key,b[i-1].key）;

bj=bj+1;

if（q==-1）{

b[0]=b[i];

b[i]=b[i-1];jh=jh+2;

q=strcmp（b[0].key,b[i-2].key）;bj=bj+1;

for（j=i-2;q==-1;j--）{

b[j+1]=b[j];jh=jh+1;

q=strcmp（b[0].key,b[j-1].key）;bj=bj+1;

};

b[j+1]=b[0];jh=jh+1;

};

};

cout<<"直接插入排序:

"<

"<

for（i=1;i

cout<

};

cout<

};

//

voidshellinsert（pointc[],intdk,intd[]）

{

intj,i,q;

pointa;

for（i=dk+1;i

q=strcmp（c[i].key,c[i-dk].key）;d[0]=d[0]+1;

if（q==-1）{

a=c[i];q=strcmp（a.key,c[i-dk].key）;d[0]=d[0]+1;d[1]=d[1]+1;

for（j=i-dk;j>0&&q==-1;j=j-dk）{

c[j+dk]=c[j];d[1]=d[1]+1;

q=strcmp（a.key,c[j-dk].key）;

};

c[j+dk]=a;d[1]=d[1]+1;

};

};

};

voidshellsort（pointc[],intdlta[],intt）

{

intk,d[2],i;d[0]=0;d[1]=0;

pointb[le+1];

for（k=0;k

b[k+1]=c[k];

};

for（k=0;k

cout<<"希尔排序:

"<

"<

for（i=1;i

cout<

};

cout<

};

//希尔排序

voidxier（pointc[]）

{

intdlta[20],t,i;t=le/2;

for（i=0;i<20;i++）{

dlta[i]=t+1;

if（t==0）break;

t=t/2;

};

t=i+1;

shellsort（c,dlta,t）;

};

//简单选择排序

voidjiandanxuanze（pointc[]）

{

pointa,b[le];

inti,j,jh=0,bj=0,q,w;

for（i=0;i

b[i]=c[i];

};

for（i=0;i

q=i;

for（j=i+1;j

bj=bj+1;

w=strcmp（b[q].key,b[j].key）;

if（w==1）q=j;

};

if（q==i）continue;

else{

a=b[i];

b[i]=b[q];

b[q]=a;

jh=jh+3;

};

};

cout<<"简单选择排序排序:

"<

"<

for（i=0;i

cout<

};

cout<

};

intpartition（pointc[],intlow,inthigh,intd[]）

{

pointa,b;

intjh=0,bj=0,q;

a=c[low];

while（low

q=strcmp（c[high].key,a.key）;d[0]=d[0]+1;

while（low

=-1）{high--;q=strcmp（c[high].key,a.key）;d[0]=d[0]+1;};

b=c[low];

c[low]=c[high];

c[high]=b;

d[1]=d[1]+3;

q=strcmp（c[low].key,a.key）;d[0]=d[0]+1;

while（low

=1）{low++;q=strcmp（c[low].key,a.key）;d[0]=d[0]+1;};

b=c[low];

c[low]=c[high];

c[high]=b;

d[1]=d[1]+3;

};

return（low）;

};

voidqsort（pointc[],intlow,inthigh,intd[]）

{

intpivotloc;

if（low

pivotloc=partition（c,low,high,d）;

qsort（c,low,pivotloc-1,d）;

qsort（c,pivotloc+1,high,d）;

};

};

//快速排序

voidkuaisu（pointc[]）

{

pointb[le];

inti,d[2];

d[0]=0;d[1]=0;

for（i=0;i

b[i]=c[i];

};

qsort（b,0,le-1,d）;

cout<<"快速排序:

"<

"<

for（i=0;i

cout<

};

cout<

};

voiddiu（pointb[],intwe,int*jh,int*bj）

{

pointa;inti,q;

for（i=we/2-1;i>=0;i--）{

q=strcmp（b[i].key,b[2*i].key）;*bj=*bj+1;

if（q==-1）{

a=b[i];b[i]=b[2*i];b[2*i]=a;*jh=*jh+3;

};

if（2*i+1

q=strcmp（b[i].key,b[2*i+1].key）;*bj=*bj+1;

if（q==-1）{

a=b[i];b[i]=b[2*i+1];b[2*i+1]=a;*jh=*jh+3;

};

};

};

a=b[we-1];b[we-1]=b[0];b[0]=a;*jh=*jh+3;

};

//堆排序

voiddiup（pointc[]）

{

pointb[le];

inti,jh=0,bj=0,*j,*bl;

j=&jh;bl=&bj;

for（i=0;i

b[i]=c[i];

};

for（i=le;i>1;i--）{

diu（b,i,j,bl）;

};

cout<<"堆排序:

"<

"<

for（i=0;i

cout<

};

cout<

};

voidmain（）

{

inti,j,n=10,ans,an;

charb[]="abcdefghijklmnopqrstuvwxyz";

pointa[le];

for（i=0;i

n=10;

an=rand（）*（n-1）/RAND_MAX+1;

n=26;

for（j=0;j

ans=rand（）*（n-0）/RAND_MAX+0;

a[i].key[j]=b[ans];

};

a[i].key[j]='\0';

};

for（i=0;i

cout<

};

zhijiecharu（a）;

maopao（a）;

xier（a）;

jiandanxuanze（a）;

kuaisu（a）;

diup（a）;

};

四、流程图

五、调试过程

要很好的理解各种算法就可以这样才可以编出程序来，要注意比较次数和交换次数的计数问题。

六、结果分析

运行结果如下：

o

vp

jxvte

snhacjde

ldaajnopp

rl

bpuu

hwsyy

dmgwf

vzzpkghv

j

r

a

hhprvsmft

lytcp

tpoj

fl

nztiermb

ndydxsh

bzrd

vpeevmen

khortsm

jv

n

lcyxoi

jwilh

htoftvknx

z

bnfvqr

vd

t

yhi

tv

ptgdabu

fdoacltr

blfsh

gpnq

nz

yeiezlz

q

l

bxhftkfqp

mpqwv

sojeto

gepspjmct

qrudow

psbrziohe

w

teicbqvo

khmnd

tiv

wshydbunp

bwricnfhx

rcmjm

njrnpkas

q

mtmjuojy

ejdtyp

i

q

ww

swadsq

be

iijruu

puxdq

gdwb

ohof

cvd

uxu

pjwfwfg

zbcnl

g

gddycbbix

lyvn

skganykg

grylxa

puodfjakc

wbvrru

rdrsu

w

scoybh

zq

xjs

eg

xcxlc

ezuwflat

ki

bgegdqxyf

qrxlxrdq

kyopng

jauf

k

bfeqlp

lrkvpfy

kzexolqs

h

kxs

xkkxiko

tttt

fh

直接插入排序:

完成的序列如下:

abebfeqlpbgegdqxyfblfshbnfvqrbpuubwricnfhxbxhftkfqpbz

rdcvddmgwfegejdtypezuwflatfdoacltrfhflggddycbbix

gdwbgepspjmctgpnqgrylxahhhprvsmfthtoftvknxhwsyyiiijr

uujjaufjvjwilhjxvtekkhmndkhortsmkikxskyopngk

zexolqsllcyxoildaajnopplrkvpfylytcplyvnmpqwvmtmjuojyn

ndydxshnjrnpkasnznztiermboohofpjwfwfgpsbrzioheptgdabu

puodfjakcpuxdqqqqqrudowqrxlxrdqrrcmjmrdrsurl

scoybhskganykgsnhacjdesojetoswadsqtteicbqvotivtpojttt

ttvuxuvdvpvpeevmenvzzpkghvwwwbvrruwshydbunpww

xcxlcxjsxkkxikoyeiezlzyhizzbcnlzq

共进行比较2528次,进行交换2616次

***************************

起泡法:

完成的序列如下:

abebfeqlpbgegdqxyfblfshbnfvqrbpuubwricnfhxbxhftkfqpbz

rdcvddmgwfegejdtypezuwflatfdoacltrfhflggddycbbix

gdwbgepspjmctgpnqgrylxahhhprvsmfthtoftvknxhwsyyiiijr

uujjaufjvjwilhjxvtekkhmndkhortsmkikxskyopngk

zexolqsllcyxoildaajnopplrkvpfylytcplyvnmpqwvmtmjuojyn

ndydxshnjrnpkasnznztiermboohofpjwfwfgpsbrzioheptgdabu

puodfjakcpuxdqqqqqrudowqrxlxrdqrrcmjmrdrsurl

scoybhskganykgsnhacjdesojetoswadsqtteicbqvotivtpojttt

ttvuxuvdvpvpeevmenvzzpkghvwwwbvrruwshydbunpww

xcxlcxjsxkkxikoyeiezlzyhizzbcnlzq

共进行比较4950次,进行交换2469次

***************************

希尔排序:

完成的序列如下:

abebfeqlpbgegdqxyfblfshbnfvqrbpuubwricnfhxbxhftkfqpbz

rdcvddmgwfegejdtypezuwflatfdoacltrfhflggddycbbix

gdwbgepspjmctgpnqgrylxahhhprvsmfthtoftvknxhwsyyiiijr

uujjaufjvjwilhjxvtekkhmndkhortsmkikxskyopngk

zexolqsllcyxoildaajnopplrkvpfylytcplyvnmpqwvmtmjuojyn

ndydxshnjrnpkasnznztiermboohofpjwfwfgpsbrzioheptgdabu

puodfjakcpuxdqqqqqrudowqrxlxrdqrrcmjmrdrsurl

scoybhskganykgsnhacjdesojetoswadsqtteicbqvotivtpojttt

ttvuxuvdvpvpeevmenvzzpkghvwwwbvrruwshydbunpww

xcxlcxjsxkkxikoyeiezlzyhizzbcnlzq

共进行比较838次,进行交换800次

***************************

简单选择排序排序:

完成的序列如下:

abebfeqlpbgegdqxyfblfshbnfvqrbpuubwricnfhxbxhftkfqpbz

rdcvddmgwfegejdtypezuwflatfdoacltrfhflggddycbbix

gdwbgepspjmctgpnqgrylxahhhprvsmfthtoftvknxhwsyyiiijr

uujjaufjvjwilhjxvtekkhmndkhortsmkikxskyopngk

zexolqsllcyxoildaajnopplrkvpfylytcplyvnmpqwvmtmjuojyn

ndydxshnjrnpkasnznztiermboohofpjwfwfgpsbrzioheptgdabu

puodfjakcpuxdqqqqqrudowqrxlxrdqrrcmjmrdrsurl

scoybhskganykgsnhacjdesojetoswadsqtteicbqvotivtpojttt

ttvuxuvdvpvpeevmenvzzpkghvwwwbvrruwshydbunpww

xcxlcxjsxkkxikoyeiezlzyhizzbcnlzq

共进行比较4950次,进行交换279次

***************************

快速排序:

完成的序列如下:

abebfeqlpbgegdqxyfblfshbnfvqrbpuubwricnfhxbxhftkfqpbz

rdcvddmgwfegejdtypezuwflatfdoacltrfhflggddycbbix

gdwbgepspjmctgpnqgrylxahhhprvsmfthtoftvknxhwsyyiiijr

uujjaufjvjwilhjxvtekkhmndkhortsmkikxskyopngk

zexolqsllcyxoildaajnopplrkvpfylytcplyvnmpqwvmtmjuojyn

ndydxshnjrnpkasnznztiermboohofpjwfwfgpsbrzioheptgdabu

puodfjakcpuxdqqqqqrudowqrxlxrdqrrcmjmrdrsurl

scoybhskganykgsnhacjdesojetoswadsqtteicbqvotivtpojttt

ttvuxuvdvpvpeevmenvzzpkghvwwwbvrruwshydbunpww

xcxlcxjsxkkxikoyeiezlzyhizzbcnlzq

共进行比较1068次,进行交换984次

***************************

堆排序:

完成的序列如下:

abebfeqlpbgegdqxyfblfshbnfvqrbpuubwricnfhxbxhftkfqpbz

rdcvddmgwfegejdtypezuwflatfdoacltrfhflggddycbbix

gdwbgepspjmctgpnqgrylxahhhprvsmfthtoftvknxhwsyyiiijr

uujjaufjvjwilhjxvtekkhmndkhortsmkikxskyopngk

zexolqsllcyxoildaajnopplrkvpfylytcplyvnmpqwvmtmjuojyn

ndydxshnjrnpkasnznztiermboohofpjwfwfgpsbrzioheptgdabu

puodfjakcpuxdqqqqqrudowqrxlxrdqrrcmjmrdrsurl

scoybhskganykgsnhacjdesojetoswadsqtteicbqvotivtpojttt

ttvuxuvdvpvpeevmenvzzpkghvwwwbvrruwshydbunpww

xcxlcxjsxkkxikoyeiezlzyhizzbcnlzq

共进行比较5000次,进行交换7059次

***************************