数据结构课程设计(一)

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

数据结构课程设计

题目利用随机函数产生30000个随机整数，利用插入排序、

希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序

等排序方法进行排序，统计每一种排序上机所花费的时间，并和

理论上时间进行对比分析。

学

名

生姓

号

学

院

学

业

专

指导教师

年月目

一、设计题目

利用随机函数产生30000个随机整数，利用插入排序、起泡排序、快

速排序、选择排序、堆排序、归并排序等排序方法进行排序，统计每

一种排序上机所花费的时间，并和理论上时间进行对比分析。

二、算法设计的思想

1.简单选择排序

操作方法：第一趟，从n个记录中找出关键码最小的记录与第一个记录交换；第

二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录

交换；如此，第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的

记录与第i个记录交换，直到整个序列按关键码有序。

【效率分析】

空间效率：仅用了一个辅助单元。

时间效率：简单选择排序中，所需进行记录移动的操作次数较小，其最小值为0,

最大值为3(n-l)o然而，无论记录的初始排列如何，所需进行的关键字之间的

比较次数相同，均为n(n-l)/2o因此，总的时间复杂度也是O(n2)o

2.直接插入排序

设有n个记录，存放在数组r中，重新安排记录在数组中的存放顺序，使得按关

键码有序。即r[1].key^r[2].key.......Wr[n].key

先来看看向有序表中插入一个记录的方法：

设IcjWn,r[l].keyWr[2].keyW.......<rfj-l].key,将r[j]插入,重新安排存放

顺序，使得r[l].key^r[2].key^.......Wr[j].key,得到新的有序表，记录数增1。

【效率分析】

空间效率：仅用了一个辅助单元。

1文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

时间效率：向有序表中逐个插入记录的操作，进行了n-l趟，每趟操作分为比较

关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的

初始排列。

最好情况下：即待排序列已按关键码有序，每趟操作只需1次比较2次移动。

总比较次数=n-l次

总移动次数=2(n-l)次

最坏情况下：即第j趟操作，插入记录需要同前面的j个记录进行j次关键码比

较，移动记录的次数为j+2次。

平均情况下：即第j趟操作，插入记录大约同前面的j/2个记录进行关键码比较，

移动记录的次数为j/2+2次。

由此，直接插入排序的时间复杂度为O(n2)。是一个稳定的排序方法

3.希尔排序(Shell'sSort)

直接插入排序算法简单，在n值较小时，效率比较高，在n值很大时，若序列按

关键码基本有序，效率依然较高，其时间效率可提高到0(n)。希尔排序即是从

这两点出发，给出插入排序的改进方法。

希尔排序方法：

1.选择一个步长序列tl,t2,•••,tk,其中ti>tj,tk=l；

2.按步长序列个数k,对序列进行k趟排序；

3.每趟排序，根据对应的步长ti,将待排序列分割成若干长度为m的子序列，

分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处

理，表长度即为整个序列的长度。

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于步长因子序列的

选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没

有人给出选取最好的步长因子序列的方法。步长因子序列可以有各种取法，有取

奇数的，也有取质数的，但需要注意：步长因子中除1外没有公因子，且最后一

个步长因子必须为k希尔排序方法是一个不稳定的排序方法。4.冒

泡排序

冒泡排序方法：对n个记录的表，第一趟冒泡得到一个关键码最大的记录r[n],

第二趟冒泡对n-l个记录的表，再得到一个关键码最大的记录rfn-1],如此重复，

直到n个记录按关键码有序的表。

【效率分析】

空间效率：仅用了一个辅助单元。

时间效率：总共要进行n-l趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关

键码比较。

移动次数：

最好情况下：待排序列已有序，不需移动。

5.快速排序

快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将

待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键

码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键

码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序

列按关键码有序。

【效率分析】

空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，

2文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为

O(log2n),即树的高度；在最坏情况下，即二叉树是一个单链，为0(n)。

时间效率：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为

0(n),若设T(n)为对n个记录的待排序列进行快速排序所需时间。

理想情况下：每次划分，正好将分成两个等长的子序列，则

T(n)Wcn+2T(n/2)c是一个常数

Wcn+2(cn/2+2T(n/4))=2cn+4T(n/4)

W2cn+4(cn/4+T(n/8))=3cn+8T(n/8)

•••

Wcnlog2n+nT(1)=O(nlog2n)

最坏情况下：即每次划分，只得到一个子序列，时效为O(n2)o

快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。

但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进

之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三

个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

6堆排序

堆排序的时间，主要由建立初始］堆和反复重建堆这两部分的时间开销构

成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为

O(nlogn)o堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较

次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，

辅助空间为0(1),它是不稳定的排序方法。

7.归并排序

归并操作的工作原理如下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的

序列，设定两个指针，最初位置分别为两个已经排序序列的起始位置。

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动

指针到下一位置。重复步骤3直到某一指针达到序列尾，将另一序列剩

下的所有元素直接复制到合并序列尾。速度仅次于快速排序，但较稳定。

归并排序的时间复杂度为O(nlogn)。

三、算法设计分析

程序总体采用分块化设计，每种排序的函数都以其相应的名字保存，

在主程序调用时用#include"**.cpp”调用。这样的总体布局将各个功

能隔离开来，每个模块负责每个模块的功能，使得程序的布局简单明了。

且子程序只有在被调用时才会运行大大节约系统资源减少了运算时间。

同时由于功能的隔离使得程序的扩展性大大提高，无论程序将要任何改

3文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

动时，都会方便很多。

四、源代码

以“.cpp”保存，其他子函数分别保存，以下是主函数的代码。

#include<iostream>

#include<conio.h>

#include<time.h>

#include”快速排序.cpp”

#include”堆排序.cpp”

#include”直接插入排序.cpp”

#include”选择排序.cpp”

#include”冒泡排序.cpp”

#include"希尔排序.cpp”

#include”归并排序.cpp”

usingnamespacestd;

intmain()

clock_tstart,finish;

inti,timel,time2,time3,time4,time5,time6,time7;

inta[30000],b[30000];

srand(time(O));

for(i=0;i<30000;i++)

a[i]=rand();

**************************\n”•

cout«"\t选择排序\n";

coutw”**************************\n”・

for(i=0;i<30000;i++)b[i]=a[i];start=clock();

choices_sort(b);

finish=clock();

timel=finish-start;

printf("选择排序耗时％d毫秒!\n\n\n”,timel);

cou***************************\n”•

cout«"\t直接插入排序\n";

cout<<***************************\n”•

for(i=0;i<30000;i++)b[i]=a[i];

start=clock();

direct(b);

finish=clock();

time2=finish-start;

printf("直接插入排序耗时％(1毫秒!\n\n\n”,time2);

***************************\n"♦

4文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑,欢迎下载支持.

coutv<"\t堆排序\n";

cout<<”**************************\ri''・

for(i=0;i<30000;i++)b[i]=a[i];start=clock();

heap_sort(b,30000);

finish=clock();

time3=finish-start;

printf(”堆排序耗时％(1毫秒!\n\n\n”,time3);

coutv<''**************************\ri”・

cout«"\t快速排序\n";

cout<<***************************\n”♦

for(i=0;i<30000;i++)bfi]=a[i];start=clock();

sort(b,0,29999);

finish=clock();

time4=finish-start;

printf("快速排序耗时％d毫秒!\n\n\n”,time4);

cout^^<***************************\n"•

cout«"\t冒泡排序\n";

cou***************************\n”•

for(i=0;i<30000;i++)b[i]=a[i];start=clock();

bubble_sort(b);

finish二clock。；

time5=finish-start;

printf("冒泡排序耗时％d毫秒!\n\n\n】ime5);

cout^^<”**************************\n"•

coutv<"\t希尔排序\n";

cout<<”**************************\ri''・

for(i=0;i<30000;i++)b[i]=a[i];start=clock();

shellsort(b,30000);

finish=clock();

time6=finish-start;

printf("希尔排序耗时％d毫秒!\n\n\n\tim排);

cou***************************\n”•

cout«"\t归并排序\n";

cout^^<”**************************\n"•

for(i=0;i<30000;i++)b[i]=a[i];

start=clock();

MergeSort(b,0,29999);

finish=clock();

time7=finish-start;

printf("归并排序耗时％d毫秒!\n\n\n”,time7);

5文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

getch();

return0;

以下是直接插入排序的函数，以“直接插入排序.cpp”保存

#include<iostream>

#include<conio.h>

usingnamespacestd;

voiddirect(int

a[]){inti,j,w;

for(i=0;i<30000;i++)

for(j=i;j>=0;j-)

if(a[j]>=a[j+l])

w=afj];

a[j]=a|j+l];

a[j+l]=w;

以下是选择排序的函数，以“选择排序.cpp”保存

#include<iostream>

#include<conio.h>

usingnamespacestd;

voidchoices_sort(inta[])

(

inti,j,k,t;

for(i=0;i<30000;i++)

(

k=i;

for(j=i+l;j<30000;j++)

if(a[k]>aU])

k=j;

t=a[i];

a[i]=a[k];

a[k]=t;

以下是冒泡排序的函数，以“冒泡排序.cpp”保存

6文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

#include<iostream>

#include<conio.h>

usingnamespacestd;

voidbubble_sort(inta[])

(

inti,j,w;

for(i=0;i<30000;i++)

for(j=0;j<30000-i;j++)

if(a[j]>a[j+l])

{

w=a[j];

a[j]=a[j+l];

a[j+l]=w;

以下是希尔排序的函数，以“希尔排序.cpp”保存

#include<iostream>

#include<conio.h>

#include<time.h>

usingnamespacestd;

voidshellsort(inta[],intn)

(

intd,i,j,temp;

for(d=n/2;d>=l;d=d/2)

(

for(i=d;i<n;i++)

(

temp=a[i];

for(j=i-d;(j>=0)&&(a[j]>temp);j=j-d)

(

a[j+d]=a|j];

}

a[j+d]=temp;

以下是快速排序的函数，以“快速排序.cpp”保存

#include<iostream>

#include<conio.h>

usingnamespacestd;

voidsort(inta[],intx,inty)

7文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑,欢迎下载支持.

intxx=x,yy=y;

intk=a[x];

if(x>=y)return;

while(xx!=yy)

{

while(xx<yy&&a[yy]>=k)yy—;

a[xx]=a[yy];

while(xx<yy&&a[xx]<=k)xx++;

a[yy]=a[xx];

)

a[xx]=k;

sort(a,x,xx-l);

sort(a,xx+l,y);

)

以下是堆排序的函数，以“堆排序.c叩”保存

#include<iostream>

#include<conio.h>

#include<time.h>

usingnamespacestd;

voidsift(int*x,intn,ints)

(

intt,k,j;

t=*(x+s);/*暂存开始元素*/

k=s;/*开始元素下标*/

j=2*k+1;/*右子树元素下标*/

while(j<n)

(

if(j<n-l&&*(x+j)<*(x+j+l))/*判断是否满足堆的条件：满足

就继续下一轮比较，否则调整。*/

(

j++；

)

if(t<*(x+j))/*调整*/

(

*(x+k)=*(x+j);

k=j；/*调整后，开始元素也随之

调整*/

j=2*k+1;

)

else/*没有需要调整了，已经是

个堆了，退出循环。*/

(

break;

8文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

*(x+k)=t;/*开始元素放到它正确位

置*/

)

voidheap_sort(int*x,intn)

(

inti,k,t;

for(i=n/2-l;i>=0;i—)

(

sift(x,n,i);/*初始建堆*/

}

for(k=n-1;k>=l;k—)

(

t=*(x+0);/*堆顶放到最后*/

*(x+0)=*(x+k);

*(x+k)=t;

sift(x,k,0);/*剩下的数再建堆*/

以下是归并排序的函数，以“归并排序.cpp”保存

#include<iostream>

#include<conio.h>

usingnamespacestd;

voidMerge(int*R,intlow,intm,inthigh)

(一

inti=low,j=m+l,p=0;

int*R1;

R1=(int*)malloc((high-low+l)*sizeof(int));

if(!Rl)

return;

while(i<=m&&j<=high)

Rl[p++]=(R[i]<=RU])?R[i++]:RU++];

while(i<=m)

Rl[p++]=R[i++];

while(j<=high)

Rl[p++]=RU++]；

for(p=0,i=low;i<=high;p++,i++)

R[i]=Rl[p]；

)

voidMergeSort(intR[],intlow,inthigh)

intmid;

9文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.wor