发布时间 : 星期日 文章常用排序算法课程设计报告更新完毕开始阅读9489155577232f60ddcca1e0
xxxxx《xxxxx》课程设计报告
2 需求分析
2.1 直接插入排序
思路:设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.
2.2 希尔排序
思路:先取一个正整数d1(d1
2.3 快速排序:(递归和非递归)
思路:以第一个关键字K1为控制字,将[K1、K2、….Kn]分成两个子区,使左区的有关键字小于等于K1,右区所有关键字大于等于K1,最后控制居两个子区中间的适当位置。在子区内数据尚处于无序状态。将右区首、尾指针保存入栈,对左区进行与第(1)步相类似的处理,又得到它的左子区和右子区,控制字区中。重复第(1)、(2)步,直到左区处理完毕。然后退栈对一个个子区进行相类似的处理,直到栈空。 分区处理函数hoare
思路:首先用两个指针i、j分别指向首、尾两个关键字,i=1,j=8。如对(46、56、14、43、95、10、19、72)。第一个关键字46作为控制字,该关键字所属的
2
xxxxx《xxxxx》课程设计报告
记录另存储在一个x变量中。从文件右端元素r[j].key开始与控制字x.key相比较,当r[j].key大于等于x.key时,r[j]不移动,修改指针j,j--,直到r[j].key 2.4 堆排序 思路:把n个记录存于向量r之中,把它看成完全二叉树,此时关键字序列不一定满足堆的关系。堆排序大体分为两步处理: 初建堆,从堆的定义出发,当i=1、2、。。。。、[2/n]时应满足ki<=k2i和ki<=k2i+1.所以先取i=[n/2](它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆,然后令i=i-1,将以不结点为根的子树调整为堆。此时可能会反复调整某些结点,直到i=1为止,堆初步建成。 堆排序,首先输出堆顶元素(一般是最小值),让堆中最后一个元素上移到原堆顶位置,然后恢复堆。因为经过第一步输出堆顶元素的操作后,往往破坏了堆关系,所以要恢复堆;重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。 3 xxxxx《xxxxx》课程设计报告 3 概要设计 3.1 头文件 #include 3.2 ADT struct element { int key; }list[20]; struct rnode { }; int key; int point; 3.3 各种操作函数: (1)创建一个数组函数:int creat(); (2)输出数组函数:void print(struct element a[20],int n); (3)保存函数:void save(struct element a[SIZE],int n, char fileName[] ) (4)直接插入排序函数:void insert_sort(element a[], int n) (5)希尔排序函数:void shell(struct element a[20],int n); 4 xxxxx《xxxxx》课程设计报告 (6)快速排序函数(分区处理函数):int hoare(struct element a[20],int l,int h); (7)非递归的快速排序函数:void quick1(struct element a[20],int n); (8)递归的快速排序函数:void quick2(struct element a[20],int l,int h); (9)堆排序(调整堆的函数):void heap(struct element a[20],int i,int m); (10)堆排序(主体函数):void heapsort(struct element a[20],int n); (11)时间函数:start = clock();end = clock(); 3.4 主函数 Void main() { 接受命令(选择要执行的操作); 处理命令; 输出结果; } 5