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

中北大学数 据 结 构课 程 设 计 说 明 书学生姓名:学 号：学生姓名:学 号：学生姓名:学 号：学生姓名:学 号：学生姓名:学 号：学 院:软件学院专 业:软件工程题 目:排序算法实现与演示系统成绩指导教师2012 年 1月 8 日1 设计目的 本系统是为了实现和比较各种不同排序方法的不同复杂度,而建立的,从不同的角度比较各算法的优劣,从而使使用者能对个排序方法有更清晰的了解.2. 设计内容和要求 本次设计的内容主要有实现各种排序算法以及比较各种算法。要求主要是要执行对一种数据类型的序列进行所有排序方法的排序计算，并返回序列及各算法的排序指标。3本设计所采用的数据结构 本次设计主要采用的数据结构有结构体定义，直接排序，选择排序，归并排序，快速排序，冒泡排序，希尔排序，堆排序等。4功能模块详细设计4.1 详细设计思想本次设计分主题设计和模块设计两部分。主体设计方面，本系统的主要数据类型为含有一个关键字的结构体类型，命名为datatype；设置两个全局变量数组，cn和mn，分别用于记录每种排序方法中的各排序元素的比较次数和移动次数（关键字交换以3次计）的总和。模块设计方面，本系统大致可分为排序模块部分和运行模块部分。排序模块部分分为归并排序模块，快速排序模块，冒泡排序模块，选择排序模块，直接排序模块，希尔排序模块，堆排序模块；运行模块部分分为主函数，自行输入模块，随机模块，输出模块。以下是各排序算法的核心设计思想：冒泡排序相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作快速排序使用分治法（Divideandconquer）策略来把一个序列（list）分为两个子序列（sub-lists），从数列中挑出一个元素，称为基准，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边），递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子序列排序插入排序将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表选择排序每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完希尔排序将待排序的元素分为多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入堆排序堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将Rl.n看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录归并排序归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。运行模块个算法如下：主函数首先选择一种生成原始数列的方法，然后经过选择进入相应的界面，将数据排序后输出，并显示出排序比较结果。手动输入函数依次输入数据，记录在一个已定义的寄存器中，待排序时使用。排序时将各排序模块函数调用，排序得出结果。自动输入函数调用已有的库函数产生所输入的个数的数列，然后调用已有排序函数，得到排序后数列，然后输出。4.2 核心代码#include#include#include#define MAXNUM 100 typedef struct int key; datatype; datatype RMAXNUM;/*定义类型*/ int cnMAXNUM,mnMAXNUM;void D_InsertSort(datatype R , int n)/*直接排序*/ int i,j; extern int cnMAXNUM,mnMAXNUM;for(i=2; i=n; i+) cn0+; if (Ri.keyRi-1.key) R0=Ri; mn0+; for(j=i-1; R0.keyRj.key; j-) Rj+1=Rj; Rj+1=R0; mn0+=2; void Select_Sort(datatype R ,int n)/*简单选择排序*/ int i,j,k; extern int cnMAXNUM,mnMAXNUM; for(i=1;in;i+) k=i; for(j=i+1; j=n; j+) cn1+; if(Rj.keyRk.key) k=j; if (i=k) R0=Rk; Rk=Ri; Ri=R0; mn1+=3; void Bubble_Sort (datatype R , int n)/*冒泡排序*/ int i, j; extern int cnMAXNUM,mnMAXNUM; int swap;for(i=1; in-1; i+) swap=0; for(j=1; j=n-i; j+) cn2+; if (Rj.keyRj+1.key) R0=Rj; Rj=Rj+1; Rj+1=R0; mn2+=3; swap=1; if(swap=0) break; void HeapAdjust(datatype R , int s, int t) datatype rc; extern int cnMAXNUM,mnMAXNUM; int i,j ; rc=Rs; i=s; for(j=2*i; j=t; j=2*j) cn3+; if(jt & Rj.key Rj.key) break; Ri=Rj; mn3+; i=j; Ri=rc;void HeapSort(datatype R , int n)/*堆排序*/ int i; extern int cnMAXNUM,mnMAXNUM; for(i=n/2; i0; i- ) HeapAdjust(R, i, n); for(i=n; i1; i-) R0=R1; R1=Ri; Ri=R0; mn3+=3; HeapAdjust(R,1, i-1); void Merge(datatype R , datatype R1 , int s, int m , int t) int i,j,k; extern int cnMAXNUM,mnMAXNUM; i=s; j=m+1; k=s; while (i=m&j=t) cn4+; if(Ri.keyRj.key) R1k+=Ri+; mn4+; else R1k+=Rj+; mn4+; while (i=m) R1k+=Ri+; mn4+; while (j=t) R1k+=Rj+; mn4+;void MSort(datatype R , datatype R1 , int s, int t) int m; extern int cnMAXNUM,mnMAXNUM; if(s=t) R1s=Rs; mn4+; 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 cnMAXNUM,mnMAXNUM; R0=Rlow; mn5+; while(lowhigh) while(low=R0.key) cn5+; high-; if(lowhigh) Rlow=Rhigh; low+; mn5+; while(lowhigh&Rlow.keyR0.key) mn5+; low+; if(lowhigh) Rhigh=Rlow; high-; mn5+; Rlow=R0; mn5+; return low;void Quick_Sort(datatype R , int s, int t)/*快速排序*/ int i; if( st ) 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;i0;gap /= 2) /* 设置排序的步长，步长gap每次减半，直到减到1 */ for(i=gap;i= 0) & (Rj.key Rj+gap.key);j -= gap ) /* 比较相距gap远的两个元素的大小，根据排序方向决定如何调换 */ temp=Rj.key; Rj.key=Rj+gap.key; Rj+gap.key=temp; cn6+=1; mn6+=3; void sui_ji() int i,n; datatype RMAXNUM=0,R1MAXNUM=0; a:printf(请输入你要输入的个数:); scanf(%d,&n); if(n100) printf(超出范围重新输入!n); goto a; printf(排序前元素顺序为:); for(i=1;in+1;i+) Ri.key=rand(); printf(%d ,Ri.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 R1MAXNUM=0; printf(请输入你要输入的个数（不大于100的整数）:); scanf(%d,&n); printf(请输入各个元素:); for(i=1;in+1;i+) scanf(%d,&R1i.key); printf(排序前元素顺序为:); for(i=1;in+1;i+) printf(%d ,R1i.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 cnMAXNUM,mnMAXNUM; 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,cn0,mn0/3);printf( n);printf( 简单选择 %d %d n,cn1,mn1/3);printf( n);printf( 冒 泡 %d %d n,cn2,mn2/3);printf( n);printf( 堆 排 序 %d %d n,cn3,mn3/3); printf( n); printf( 二路归并 %d %d n,cn4,mn4/3); printf( n); printf( 快 速 %d %d n,cn5,mn5/3); printf( n); printf( 希尔排序 %d %d n,cn6,mn6/3); getchar(); printf(谢谢使用！ _ n); system(PAUSE); return 0; （此页附在说明书后，请在验收前填好）9