数据结构课程设计(内部排序算法比较-C语言).doc

(完整word版)数据结构课程设计(内部排序算法比较_C语言)

课题：内部排序算法比较

第一章 问题描述
排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。

第二章 系统分析
界面的设计如图所示：

|******************************|
|-------欢 迎 使 用---------|
|-----（1）随 机 取 数-------|
|-----（2）自 行 输 入-------|
|-----（0）退 出 使 用-------|
|******************************|
请 选 择 操 作 方 式：
如上图所示该系统的功能有：
（1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。
（2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。
（3）选择0 打印“谢谢使用！！”退出系统的使用！！

第三章 系统设计
（I） 友好的人机界面设计：（如图3.1所示）
|******************************|
|-------欢 迎 使 用---------|
|-----（1）随 机 取 数-------|
|-----（2）自 行 输 入-------|
|-----（0）退 出 使 用-------|
|******************************|
（3.1）
（II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示）
|******************************|
|-------欢 迎 使 用---------|
|-----（1）随 机 取 数-------|
|-----（2）自 行 输 入-------|
|-----（0）退 出 使 用-------|
|******************************|
请 选 择 操 作 方 式：（用户在此输入操作方式）
（3.2）
（III）系统采用定义结构体数组来存储数据 。
（IV）功能介绍：
（1）操作功能：a .当用户选择随即电脑随机取数时
系统将弹出——>请输入你要输入的个数 ：（用户在此输入要电脑取数的个数） 要是用户输入的数据过大系统将提醒错误——>超出范围重新输入!!!
b . .当用户选择自行输入时
系统将弹出——>请输入你要输入的个数（不大于于30的整数）：
当用户输完元素的个数之后系统将提示用户依次输入各个元素。
——>请输入各个元素:
(2) 排序功能：系统有 简单选择排序，冒泡排序，堆排序，二路归并排序，快速排序的功能。
（3）打印清晰：系统会打印出在排序操作之前电脑随机取数或者用户输入的原始排列顺序；并将排序操作之后的有序数据打印在原始数据的下面以便用户的对比。在排序操作结束之后系统将以直方图的形式打出排序过程中比较和移动次数让客户一目了然地看到排序的结果：

比 较 结 果
排序方式
比较次数
移动次数
直 接

简单选择

冒 泡

堆 排 序

直 接

快 速

第四章 系统实现
(一)定义结构体数组：
typedef struct
{ int key;
} datatype;
datatype R[MAXNUM];//定义结构体数组
（二）直接排序：
void D_InsertSort(datatype R[ ], int n)//直接排序
{
int i,j;

for(i=2; i<=n; i++)
{ cn[0]++;
if (R[i].key<R[i-1].key)
{R[0]=R[i]; mn[0]++;
for(j=i-1; R[0].key<R[j].key; j--)
R[j+1]=R[j];
R[j+1]=R[0]; mn[0]+=2;
}

}

}

（三）简单选择排序：
void Select_Sort(datatype R[ ],int n)//简单选择排序
{
int i,j,k;
for(i=1;i<n;i++)
{ k=i;
for(j=i+1; j<=n; j++)
{
cn[1]++;
if(R[j].key<R[k].key)
k=j;
}
if (i=k)
{ R[0]=R[k];
R[k]=R[i];
R[i]=R[0]; mn[1]+=3; }
}

}
（四）冒泡排序：
void Bubble_Sort (datatype R[ ], int n)//冒泡排序
{
int i, j;
int swap;

for(i=1; i<n-1; i++)
{swap=0;
for(j=1; j<=n-i; j++)
{
cn[2]++;
if (R[j].key<R[j+1].key)
{R[0]=R[j];
R[j]=R[j+1];
R[j+1]=R[0]; mn[2]+=3;
swap=1;
}}
if(swap==0) break;

}
}

（五）堆排序：
void HeapAdjust(datatype R[ ], int s, int t)
{
datatype rc;
int i,j ;
rc=R[s];
i=s;
for(j=2*i; j<=t; j=2*j)

{ cn[3]++;
if(j<t && R[j].key<R[j+1].key)j=j+1;
if(rc.key > R[j].key) break;
R[i]=R[j]; mn[3]++;
i=j;
}
R[i]=rc;
}
void HeapSort(datatype R[ ], int n)//堆排序
{
int i;
for(i=n/2; i>0; i-- )
HeapAdjust(R, i, n);
for(i=n; i>1; i--)
{ R[0]=R[1];
R[1]=R[i];
R[i]=R[0]; mn[3]+=3;
HeapAdjust(R,1, i-1);
}

}
（六）归并排序：
void Merge(datatype R[ ], datatype R1[ ], int s, int m , int t)
{
int i,j,k;
i=s; j=m+1; k=s;
while (i<=m&&j<=t)
{
cn[4]++;
if(R[i].key<R[j].key)
{ R1[k++]=R[i++]; mn[4]++;}
else
{ R1[k++]=R[j++]; mn[4]++;}
}
while (i<=m) { R1[k++]=R[i++]; mn[4]++; }
while (j<=t) { R1[k++]=R[j++]; mn[4]++;}
}
void MSort(datatype R[ ], datatype R1[ ], int s, int t)
{
int m;
if(s==t) { R1[s]=R[s]; mn[4]++;}
else {m=(s+t)/2;
MSort(R, R1, s, m);
MSort(R, R1, m+1, t);
Merge(R1, R, s, m, t);
}
}

void MergeSort(datatype R[ ], datatype R1[ ], int n)//归并排序
{
MSort(R, R1,1, n);
}
int Partition(datatype R[ ], int low, int high)
{
R[0]=R[low]; mn[5]++;
while(low<high)
{ while(low<high&&R[high].key>=R[0].key) {cn[5]++; high--;}
if(low<high) { R[low]=R[high]; low++; mn[5]++; }

while(low<high&&R[low].key<R[0].key) { mn[5]++; low++; }
if(low<high) {R[high]=R[low]; high--; mn[5]++; }

}
R[low]=R[0]; mn[5]++;
return low;
}
（七）快速排序：
void Quick_Sort(datatype R[ ], int s, int t)//快速排序
{
int i;
if( s<t )
{
i = Partition(R, s, t);
Quick_Sort(R, s, i-1);
Quick_Sort(R, i+1, t);
}

}
void prin(datatype R[],int n)
{
int i ;
printf("排序的结果为：");
for(i=1;i<=n;i++)
printf("%d ",R[i]);
printf("\n ");

}
（八）电脑随机取数：
void sui_ji()
{
int i,n;
datatype R[MAXNUM]={0};
a: printf("请输入你要输入的个数:");
scanf("%d",&n);
if(n>25)
{
printf("超出范围重新输入!!!\n");
goto a;
}
addlist(R,n);
printf("排序前元素顺序为:");
for(i=1;i<n+1;i++) printf("%d ",R[i].key);
printf("\n");
D_InsertSort(R,n);//直接排序
prin(R,n);
Select_Sort(R,n);//简单选择排序
Bubble_Sort(R, n);//冒泡排序
HeapSort(R, n);//堆排序
datatype R1[MAXNUM]={0};
MergeSort(R, R1, n);//二路归并排序
Quick_Sort(R,0, n);//快速排序

}
（九）用户自行输入：
void zixing_input()
{ int n,i;
datatype R1[MAXNUM]={0};
printf("请输入你要输入的个数（不大于于30的整数）:");
scanf("%d",&n);
printf("请输入各个元素:");
for(i=1;i<n+1;i++)
scanf("%d",&R1[i].key);
printf("排序前元素顺序为:");
for(i=1;i<n+1;i++) printf("%d ",R1[i].key);
printf("\n");
D_InsertSort(R1,n);//直接排序
prin(R1,n);
Select_Sort(R1,n);//简单选择排序
Bubble_Sort(R1, n);//冒泡排序
HeapSort(R1, n);//堆排序
datatype R2[MAXNUM]={0};
MergeSort(R1, R2, n);//二路归并排序
Quick_Sort(R1,0, n);//快速排序

}
（十）主函数调用：

int main(void)
{
int s;
printf(" |******************************|\n");
printf(" |-------欢 迎 使 用-----------------|\n");
printf(" |-----（1）随 机 取 数-------------|\n");
printf(" |-----（2）自 行 输 入-------------|\n");
printf(" |-----（0）退 出 使 用-------------|\n");
printf(" |******************************|\n");
printf(" 请 选 择 操 作 方 式： ");
scanf("%d",&s);
switch(s)
{
case 1: system("cls") ; sui_ji(); break;
case 2: system("cls") ; zixing_input(); break;
case 0: printf(" 谢谢使用！！ "); exit(0); break;

}
printf("\n ");

printf(" 比 较 结 果 \n");
printf(" \n");
printf(" 排序方式 比较次数 移动次数\n");
printf(" \n");
printf(" 直 接 %d %d \n",cn[0],mn[0]);
printf(" \n");
printf(" 简单选择 %d %d \n",cn[1],mn[1]);
printf(" \n");
printf(" 冒 泡 %d %d \n",cn[2],mn[2]);
printf(" \n");
printf(" 堆 排 序 %d %d \n",cn[3],mn[3]);
printf(" \n");
printf(" 二路归并 %d %d \n",cn[4],mn[4]);
printf(" \n");
printf(" 快 速 %d %d \n",cn[5],mn[5]);

}
第五章 系统测试

（一） 随机取数的测试：

（二）自行输入的测试：

（三）退出系统：

（四）时间的估算：

排序方法
平均时间性能
最好时间性能
最坏时间性能
直 接
O(n2)
O(n)
O(n2)
简单选择
O(n2)
O(n)
O(n2)
冒 泡
O(n2)
O(n)
O(n2)
堆 排 序
O(nlog2 n)
O(nlog2 n)
O(nlog2 n)
直 接
O(nlog2 n)
O(nlog2 n)
O(nlog2 n)
快 速
O(nlog2 n)
O(nlog2 n)
O(nlog2 n)

参考文献
1. 作者:张晓莉 王苗 《数据结构与算法》 机械工业出版社 2008年7月
2. 作者：杨升 《数据结构》 厦门大学出版社 2009年6月

教师评语和成绩

2010 年 6 月

框架三层，局部为二层钢构。本工程外脚手架采用落地式钢管脚手架,外架随主体结构上升，同步搭设，比操作面高出一步，确保主体及外装修的正常安全施工。16