实验 8 查找算法实验比较 实验目的 基于教材内容,从顺序查找、二分查找、基于 BST 的查找和哈希中任选两种查找算法, 实现并比较性能。 基本要求 (1)对实现的查找算法进行实验比较,在不同数据规模(N)下执行 100次成功查找, 以表格形式记录最小、最大和平均查找时间;在不同数据规模(N)下执行 100 次不成功查 找,以表格形式记录最小、最大和平均查找时间。 (2)查找算法要基于教材,测试输入的整数数据文件(5 个,文件中数据规模 N 分别 是 100,1K,10K,100K 和 1M),每次查找的比较次数和…

2019年12月23日 0条评论 9点热度 阅读全文

实验 8 查找算法实验比较 实验目的 基于教材内容,从顺序查找、二分查找、基于 BST 的查找和哈希中任选两种查找算法, 实现并比较性能。 基本要求 (1)对实现的查找算法进行实验比较,在不同数据规模(N)下执行 100次成功查找, 以表格形式记录最小、最大和平均查找时间;在不同数据规模(N)下执行 100 次不成功查 找,以表格形式记录最小、最大和平均查找时间。 (2)查找算法要基于教材,测试输入的整数数据文件(5 个,文件中数据规模 N 分别 是 100,1K,10K,100K 和 1M),每次查找的比较次数和…

2019年12月23日 0条评论 9点热度 阅读全文

一. 交换排序 1. 冒泡排序 冒泡排序是所有排序算法中最原始的,重复的遍历要排序的数串,一次比较两个元素,假如顺序错误就交换这两个元素,直到不再需要交换,则数串已经排序完毕。数串中的最大元素会逐渐冒上来,所以称之为“冒泡排序”。 冒泡排序流程图如下所示: 时间复杂度分析 无论数串的紊乱状态如何,只要数串的长度确定,比较次数就是确定的。假设数串的长度为n,那么每次遍历(即内层循环)需要的比较操作为 (n-i-1) 步,而i又是从0遍历到 (n-1) 。因此最后得出的比较步数为 n(n−1)2 ,比较操作时间复杂度为…

2017年5月22日 0条评论 4点热度 阅读全文