排序算法数据结构课程设计说明书.doc

中北大学
数 据 结 构
课 程 设 计 说 明 书

学生姓名:

学 号：

学生姓名:

学 号：

学生姓名:

学 号：

学生姓名:

学 号：

学生姓名:

学 号：

学 院:
软件学院
专 业:
 软件工程
题 目:
排序算法实现与演示系统
成绩

指导教师

   2012 年 1月 8 日
1 设计目的
本系统是为了实现和比较各种不同排序方法的不同复杂度,而建立的,从不同的角度比较各算法的优劣,从而使使用者能对个排序方法有更清晰的了解.
2. 设计内容和要求
本次设计的内容主要有实现各种排序算法以及比较各种算法。要求主要是要执行对一种数据类型的序列进行所有排序方法的排序计算，并返回序列及各算法的排序指标。
3．本设计所采用的数据结构
本次设计主要采用的数据结构有结构体定义，直接排序，选择排序，归并排序，快速排序，冒泡排序，希尔排序，堆排序等。
4．功能模块详细设计
4.1 详细设计思想
本次设计分主题设计和模块设计两部分。
主体设计方面，本系统的主要数据类型为含有一个关键字的结构体类型，命名为datatype；设置两个全局变量数组，cn和mn，分别用于记录每种排序方法中的各排序元素的比较次数和移动次数（关键字交换以3次计）的总和。
模块设计方面，本系统大致可分为排序模块部分和运行模块部分。排序模块部分分为归并排序模块，快速排序模块，冒泡排序模块，选择排序模块，直接排序模块，希尔排序模块，堆排序模块；运行模块部分分为主函数，自行输入模块，随机模块，输出模块。
以下是各排序算法的核心设计思想：
冒泡排序
相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作
快速排序
使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists） ，从数列中挑出一个元素，称为 "基准"，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边），递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子序列排序
插入排序
将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表
选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完
希尔排序
将待排序的元素分为多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入
堆排序
堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录
归并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
运行模块个算法如下：
主函数
首先选择一种生成原始数列的方法，然后经过选择进入相应的界面，将数据排序后输出，并显示出排序比较结果。
手动输入函数
依次输入数据，记录在一个已定义的寄存器中，待排序时使用。排序时将各排序模块函数调用，排序得出结果。
自动输入函数
调用已有的库函数产生所输入的个数的数列，然后调用已有排序函数，得到排序后数列，然后输出。

4.2 核心代码
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

#define MAXNUM 100
typedef struct
{ int key;
} datatype;
datatype R[MAXNUM];/*定义类型*/
int cn[MAXNUM],mn[MAXNUM];

void D_InsertSort(datatype R[ ], int n)/*直接排序*/
{
int i,j;
extern int cn[MAXNUM],mn[MAXNUM];
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;
extern int cn[MAXNUM],mn[MAXNUM];
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;
extern int cn[MAXNUM],mn[MAXNUM];
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;
extern int cn[MAXNUM],mn[MAXNUM];
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;
extern int cn[MAXNUM],mn[MAXNUM];
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;
extern int cn[MAXNUM],mn[MAXNUM];
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;
extern int cn[MAXNUM],mn[MAXNUM];
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)
{
extern int cn[MAXNUM],mn[MAXNUM];
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 sort(datatype R[],int n)/*希尔排序*/
{
int gap,i,j,temp;
extern int cn[MAXNUM],mn[MAXNUM];
for(gap=n/2;gap>0;gap /= 2) /* 设置排序的步长，步长gap每次减半，直到减到1 */
{
for(i=gap;i<n;i++) /* 定位到每一个元素 */
{
for(j=i-gap;(j >= 0) && (R[j].key > R[j+gap].key);j -= gap ) /* 比较相距gap远的两个元素的大小，根据排序方向决定如何调换 */
{
temp=R[j].key;
R[j].key=R[j+gap].key;
R[j+gap].key=temp;
cn[6]+=1;
mn[6]+=3;
}
}
}
}

void sui_ji()
{
int i,n;
datatype R[MAXNUM]={0},R1[MAXNUM]={0};;
a:printf("请输入你要输入的个数:");
scanf("%d",&n);
if(n>100)
{
printf("超出范围重新输入!!!\n");
goto a;
}

printf("排序前元素顺序为:");
for(i=1;i<n+1;i++)
{
R[i].key=rand();
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);/*堆排序*/
MergeSort(R, R1, n);/*二路归并排序*/
Quick_Sort(R,0, n);/*快速排序*/
sort(R,n);/*希尔排序*/
}

void zi_xing_input()
{ int n,i;
datatype R1[MAXNUM]={0};
printf("请输入你要输入的个数（不大于100的整数）:");
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);/*堆排序*/
Quick_Sort(R1,0, n);/*快速排序*/
sort(R,n);/*希尔排序*/
}

int main()
{
extern int cn[MAXNUM],mn[MAXNUM];
char s;
printf(“ 排序算法实现与演示统 \n ”);
printf(" ┏******************************┓\n");
printf(" ┃------- 欢 迎 使 用 ----┃\n");
printf(" ┃-----（1）随 机 取 数-------┃\n");
printf(" ┃-----（2）自 行 输 入-------┃\n");
printf(" ┃-----（0）退 出 使 用-------┃\n");
printf(" ┗******************************┛\n");
printf(" 请 选 择 操 作 方 式： ");
b:s=getch();
switch(s)
{
case '1': system("cls") ; sui_ji(); break;
case '2': system("cls"); zi_xing_input(); break;
case '0': printf(" 谢谢使用！！ "); exit(0); break;
default:printf("错误输入，重新输入！");goto b;
}
printf("\n ");
printf(" 比 较 结 果 \n");
printf(" \n");
printf(" 排序方式 比较次数 移动次数\n");
printf(" \n");
printf(" 直 接 %d %d \n",cn[0],mn[0]/3);
printf(" \n");
printf(" 简单选择 %d %d \n",cn[1],mn[1]/3);
printf(" \n");
printf(" 冒 泡 %d %d \n",cn[2],mn[2]/3);
printf(" \n");
printf(" 堆 排 序 %d %d \n",cn[3],mn[3]/3);
printf(" \n");
printf(" 二路归并 %d %d \n",cn[4],mn[4]/3);
printf(" \n");
printf(" 快 速 %d %d \n",cn[5],mn[5]/3);
printf(" \n");
printf(" 希尔排序 %d %d \n",cn[6],mn[6]/3);
getchar();
printf("谢谢使用！^ _ ^\n");
system("PAUSE");
return 0;
}

（此页附在说明书后，请在验收前填好）

9