排序算法课程设计.docx

资源描述

排序算法课程设计.docx

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

排序算法课程设计.docx

排序算法课程设计

专业

班级

学号

姓名

指导老师

一：

课程设计的目的

1.掌握各种排序的基本思想

2.掌握各种排序的算法实现

3.掌握各种排序的算法优劣分析花费的时间计算

4.掌握各种排序算法所适用的不同场合。

二：

课程设计的内容

（1）冒泡、直插、选择、快速、希尔、归并、堆排序算法进行比较；

（2）待排序的元素的关键字为整数。

其中的数据用伪随机产生程序产生（如10000个,1000个），再使用各种算法对其进行排序，记录其排序时间，再汇总比较；（3）将每次测试所用的时间，用条形图进行表示，以便比较各种排序的优劣。

三：

课程设计的实现

（1）直接插入排序

#includetypedefintkeytype;

structdatatype

{

keytypekey;

};

/*intrand（void）;

voidsrand（unsignedintseed）;*/#include#include#include#includevoidInsertSort（datatypea[],intn）//用直接插入法对a[0]--a[n-1]排序{

inti,j;

datatypetemp;for（i=0;i

{

temp=a[i+1];j=i;

while（j>-1&&temp.key<=a[j].key）

{

a[j+1]=a[j];

j--;

}

a[j+1]=temp;

}

voidmain（）

{

/*srand（（unsigned）time（NULL））;//随机种子*/

/*time_tt;srand（（unsigned）time（&t））;*/time_tt1,t2;

srand（（unsigned）GetCurrentTime（））;datatypenum[10000];

t1=GetCurrentTime（）;

for（inti=0;i<10000;i++）

{num[i].key=rand（）;

}

intn=10000;

InsertSort（num,n）;for（intj=0;j<10000;j++）cout<

t2=GetCurrentTime（）;

cout<<"Thet1timeis:

}

（2）希尔排序

#include

/*intrand（void）;

voidsrand（unsignedintseed）;

#include

#include#includetypedefintkeytype;

structdatatype

{keytypekey;

};

voidShellSort（datatypea[],intn,intd[],intnumOfD）//用希尔排序法对记录a[0]--a[n-1]排序//各组内采用直接插入法排序

{

inti,j,k,m,span;

datatypetemp;

for（m=0;m

span=d[m];

for（k=0;k

for（i=k;i

temp=a[i+span];j=i;

while（j>-1&&temp.key<=a[j].key）{

a[j+span]=a[j];

j=j-span;}a[j+span]=temp;

voidmain（）

{

/*srand（（unsigned）time（NULL））;//随机种子*//*time_tt;

srand（（unsigned）time（&t））;*/

time_tt1,t2;srand（（unsigned）GetCurrentTime（））;datatypenum[10000];

t1=GetCurrentTime（）;

for（inti=0;i<10000;i++）

{

num[i].key=rand（）;

}

intn=10000,d[]={1000,100,10,1},numOfd=4;

ShellSort（num,n,d,numOfd）;

for（intj=0;j<10000;j++）

cout<

t2=GetCurrentTime（）;

cout<<"Thet1timeis:

}

（3）直接选择排序#includetypedefintkeytype;structdatatype

{keytypekey;

};

/*intrand（void）;

voidsrand（unsignedintseed）;

#include#include#include#includevoidSelectSort（datatypea[],intn）/*用直接选择排序法对a[0]--a[n-1]排序*/

{

inti,j,s;datatypetemp;for（i=0;i

{

s=i;

for（j=i+1;j

if（s!

=i）

{temp=a[i];a[i]=a[s];a[s]=temp;

}

voidmain（）

{/*srand（（unsigned）time（NULL））;//随机种子*//*time_tt;

srand（（unsigned）time（&t））;*/time_tt1,t2;

srand（（unsigned）GetCurrentTime（））;

datatypenum[10000];

t1=GetCurrentTime（）;

for（inti=0;i<10000;i++）

{num[i].key=rand（）;

}

intn=10000;

SelectSort（num,n）;

for（intj=0;j<10000;j++）

cout<

t2=GetCurrentTime（）;

cout<<"Thet1timeis:

}

（4）堆排序

#include

typedefintkeytype;

structdatatype

{

keytypekey;

};

#include

voidCreatHeap（datatypea[],intn,inth）

{

inti,j,flag;

datatypetemp;

i=h;//i为要建堆的二叉树根结点下标

j=2*i+1;//j为i的左孩子结点的下标

temp=a[i];

flag=0;

//沿左右孩子中值较大者重复向下筛选

while（j

=1）

{//寻找左右孩子结点中的较大者,j为其下标if（ja[j].key）//a[i].key>a[j].key

flag=1;//标记结束筛选条件

else//否则把a[j]上移

{

a[i]=a[j];

i=j;

j=2*i+1;

}

a[i]=temp;//把最初的a[i]赋予最后的a[j]

}

voidInitCreatHeap（datatypea[],intn）

{

inti;

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

CreatHeap（a,n,i）;

}

voidHeapSort（datatypea[],intn）

{

inti;

datatypetemp;

InitCreatHeap（a,n）;//初始化创建最大堆

for（i=n-1;i>0;i--）//当前最大堆个数每次递减1

{

〃把堆顶a[0]元素和当前最大堆的最后一个元素交换

temp=a[0];

a[0]=a[i];

a[i]=temp;

CreatHeap（a,i,0）;//调整根结点满足最大堆

}

voidmain（）

{/*srand（（unsigned）time（NULL））;//随机种子*//*time_tt;

srand（（unsigned）time（&t））;*/

time_tt1,t2;srand（（unsigned）GetCurrentTime（））;

datatypenum[10000];

t1=GetCurrentTime（）;

for（inti=0;i<10000;i++）{

num[i].key=rand（）;

}

intn=10000;

HeapSort（num,n）;

for（intj=0;j<10000;j++）cout<

cout<<"Thet1timeis:

}

（5）冒泡排序

#includetypedefintkeytype;structdatatype{

keytypekey;

};

#include#include#include#includevoidBubbleSort（datatypea[],intn）//用冒泡排序法对a[0]--a[n-1]排序{

inti,j,flag=1;

datatypetemp;

for（i=1;i

{

flag=0;

for（j=0;j

{if（a[j].key>a[j+1].key）{flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;

}

voidmain（）

{

/*srand（（unsigned）time（NULL））;//随机种子*/

/*time_tt;srand（（unsigned）time（&t））;*/time_tt1,t2;

srand（（unsigned）GetCurrentTime（））;datatypenum[10000];

t1=GetCurrentTime（）;

for（inti=0;i<10000;i++）

{num[i].key=rand（）;

}

intn=10000;

BubbleSort（num,n）;for（intj=0;j<10000;j++）cout<

t2=GetCurrentTime（）;

cout<<"Thet1timeis:

}

（6）快速排序

#include

/*intrand（void）;

voidsrand（unsignedintseed）;

#include

#include#includetypedefintkeytype;

structdatatype

{

keytypekey;

};

voidQuickSort（datatypea[],intlow,inthigh）

//用递归方法对对象a[low]--a[high]进行快速排序

{

inti,j;datatypetemp;i=low;j=high;temp=a[low];while（i

//在数组的右端扫描

while（i

if（i

{

a[i]=a[j];

i++;

}

//在数组的左端扫描

while（i

if（i

{

a[j]=a[i];

j--;

}

a[i]=temp;

//对子对象数组进行递归快速排序

if（low

if（i

}

voidmain（）

{

/*srand（（unsigned）time（NULL））;//随机种子*/

/*time_tt;

srand（（unsigned）time（&t））;*/

time_tt1,t2;srand（（unsigned）GetCurrentTime（））;

datatypenum[10000];

t1=GetCurrentTime（）;

for（inti=0;i<10000;i++）

{num[i].key=rand（）;

}

intn=10000;

QuickSort（num,0,9999）;

for（intj=0;j<10000;j++）

cout<

t2=GetCurrentTime（）;

cout<<"Thet1timeis:

（7）归并排序

#include

/*intrand（void）;

voidsrand（unsignedintseed）;

#include

typedefintkeytype;

structdatatype

{

keytypekey;

};

voidMerge（datatypea[],intn,datatypeswap[],intk）

//对有序表a[0]--a[n-1]进行一次二路归并排序，每个有序子表的长度为k//一次二路归并排序后新的有序子表存于swap中

{

intm=0,u1,l2,i,j,u2;

intl1=0;//给出第一个有序子表下界while（l1+k<=n-1）

{

l2=l1+k;//计算第二个有序子表下界

u1=l2-1;//计算第一个有序子表上界

u2=（l2+k-1<=n-1）?

l2+k-1:

n-1;//计算第二个有序子表上界

//两个有序子表合并

for（i=l1,j=l2;i<=u1&&j<=u2;m++）

{

if（a[i].key<=a[j].key）

{

swap[m]=a[i];

i++;

}

else

{

swap[m]=a[j];

j++;

}

//子表2已归并完，将子表1中剩余的对象顺序存放到数组swap中while（i<=u1）

{

swap[m]=a[i];

m++;

i++;

}

//子表1已归并完，将子表2中剩余的对象顺序存放到数组swap中while（j<=u2）

{

swap[m]=a[j];

m++;

j++;

}

l1=u2+1;

}

//将原始数组中不足二组的对象顺序存放到数组swap中for（i=l1;i

}

voidMergeSort（datatypea[],intn）

〃用二路归并排序法对对象数组a[O]--a[n-1]排序，swap用于临时存放对象{

inti,k=1;//归并长度由1开始

datatype*swap=newdatatype[n];//动态数组申请

while（k

{

Merge（a,n,swap,k）;

//将记录从数组swap放回a中for（i=O;i

//归并长度加倍k=2*k;

}delete[]swap;

}

voidmain（）

{

/*srand（（unsigned）time（NULL））;//随机种子*/

/*time_tt;

srand（（unsigned）time（&t））;*/

time_tt1,t2;

srand（（unsigned）GetCurrentTime（））;

datatypenum[10000];

t仁GetCurrentTime（）;

for（inti=0;i<10000;i++）

{

num[i].key=rand（）;

}

intn=10000;

MergeSort（num,n）;

for（intj=0;j<10000;j++）

cout<

t2=GetCurrentTime（）;

cout«"Thet1timeis:

getchar（）;

}

四：

课程设计的结果

对10000个随机数排序所用时间

排序算法

一一一

二二二

四

五

平均

直接插入

453n

468

P484:

469

485

471.8

希尔排序

297

直接选择

500:

484

500

490.4

堆排序

312

296

297

281

296.6

冒泡排序

500

485

497

快速排序

312「

281

296「

297

296.6

归并排序

281

282

297

281

297

287.6

对1000个随机数排序所用时间

排序算法

一一一

二二

三三

四

五

平均

直接插入

47:

r31

40.6

希尔排序

34.6

直接选择

37.4

堆排序

—31

34.4

冒泡排序

40.4

快速排序

46「

37.2

归并排序

31.4

用图的形式表示如下:

五：

课程设计的结论

在数据多的情况下，归并排序能够在最短的运行中完成排序，其次希尔排序,堆排序，快速排序。

而冒泡所需要的时间最长，在数据少的情况下归并排序依然最快，可是没有那一种排序算法有明显的时间优势。

通过理论计算与数据验证可得：

各种排序方法性能比较

排序方法

最好时间

平均时间

最坏时间

直接插入

「0（n）

O（n2）

希尔排序

O（n1.3）

直接选择

O（n2）

堆排序

O（nIog2n）

冒泡排序

O（n）

O（n2）

快速排序

O（nlog2n）

O（nIog2n）

O（n2）

归并排序

O（nIog2n）

展开阅读全文