中国科学技术大学University of Science and Technology of China算法基础上机实验 1育天下英才剑寰宇学府学 期：2016(秋)麻清意道
算法基础 上机实验 1 学 期: 2016 (秋)
SehoolofCSTProject l: Sorting实验1：排序n个元素，元素为随机生成的长为1.16的字符串（字符串均为英文小写字母），n的取值为：32，34，3%，38，310°，312；算法：直接插入排序，堆排序，归并排序，快速排序，SHELL排序（5个增量，分别是：1，3，7，15，21）。实验2：排序n个元素，元素为随机生成的1到65535之间的整数，n的取值为：33，35，37，3°，3'l，313;算法：冒泡排序，快速排序，归并排序，基数排序，计数排序
School of CST Project 1: Sorting ◼ 实验1：排序 n 个元素，元素为随机生成的长为1.16的字符串（字 符串均为英文小写字母），n的取值为：3 2 ，3 4 ，3 6 ，3 8 ，3 10 ，3 12； 算法：直接插入排序，堆排序，归并排序，快速排序， SHELL排序（5个增量，分别是：1，3，7，15，21）。 ◼ 实验2：排序n个元素，元素为随机生成的1到65535之间的整数，n 的取值为：3 3 ，3 5 ，3 7 ，3 9 ，3 11 ，3 13； 算法：冒泡排序，快速排序，归并排序， 基数排序，计数排序
SehoolofCSTProject l: Sorting字符串大小判断标准：1.首先按字符串长度进行排序（短字符串在前，长字符串在后）。2.对长度相同的字符串，按字母顺序进行排序如：ab,gdh,c,gaa,caa排序后的结果是：c,ab,caa,gaa, gdh
School of CST Project 1: Sorting ◼ 字符串大小判断标准： ◼ 1.首先按字符串长度进行排序（短字符串在前，长字 符串在后）。 ◼ 2.对长度相同的字符串，按字母顺序进行排序。 ◼ 如：ab, gdh, c, gaa, caa排序后的结果是：c, ab, caa, gaa, gdh
Sehoolof CST实验要求：1、实验格式：■a)实验需建立根文件夹，文件夹名称为：学号-project1，在根文件夹下需包括实验报告、和ex1、ex2两个子文件夹，每个子文件夹又分别包含3个子文件夹：input文件夹：存放输入数据source文件夹：源程序output文件夹：输出数据b)input:输入文件中每行一个随机数据，总行数大于等于313顺序读取N个数据，进行排序example：用插入排序对310个字符串进行排序，其随机数据的输入文件路径为学号-project1/ex1/input/input_strings.txt，顺序读取前310个字符串进行排序。C)output:每种算法建立一个子文件夹，其输出结果数据导出到其对应子文件下面resultn.txt：排序结果的数据(N为数据规模的指数），每个数据规模一个输出文件time.txt：运行时间效率的数据，六个规模的时间结果都写到同个文件Example：用插入排序对310个字符串进行排序，其排序结果文件路径为学号-project1/ex1/output/insert_sort/result_10.txt
School of CST 实验要求： 1、实验格式: ◼ a)实验需建立根文件夹，文件夹名称为：学号-project1，在根文件夹下需 包括实验报告、和ex1、ex2两个子文件夹，每个子文件夹又分别包含3个子 文件夹： ◼input文件夹：存放输入数据 ◼source文件夹：源程序 ◼output文件夹：输出数据 ◼b)input： ◼输入文件中每行一个随机数据，总行数大于等于3 13 ◼顺序读取N个数据，进行排序 ◼example：用插入排序对3 10个字符串进行排序，其随机数据的输入文件路径为 学号-project1/ex1/input/input_strings.txt，顺序读取前3 10个字符串进行排序。 ◼C)output： ◼每种算法建立一个子文件夹，其输出结果数据导出到其对应子文件下面 ◼result_n.txt：排序结果的数据(N为数据规模的指数)，每个数据规模一个输出文件 ◼time.txt：运行时间效率的数据，六个规模的时间结果都写到同个文件 ◼Example：用插入排序对3 10个字符串进行排序，其排序结果文件路径为 学号-project1/ex1/output/insert_sort/result_10.txt
SehoolofCST2、性能分析的要求：a用适当的方法，或工具记录排序算法在执行时所消耗的时间：b)根据不同输入规模时记录的数据，画出算法在不同输入规模下的运行时间曲线图：比较你的曲线是否与课本中的算法渐进性能是否相同，若否，为什么，给出分析。C)比较分析不同的排序算法的时间曲线，根据你的图表分析各种排序算法在不同输入规模下哪个更占优势，与课本上介绍的算法渐进性能的相符吗？如果不相符，为什么？
School of CST 2、性能分析的要求： ◼a)用适当的方法，或工具记录排序算法在执行时所消耗的时间； ◼b)根据不同输入规模时记录的数据，画出算法在不同输入规模下的运行时 间曲线图；比较你的曲线是否与课本中的算法渐进性能是否相同，若否， 为什么，给出分析。 ◼c)比较分析不同的排序算法的时间曲线， 根据你的图表分析各种排序算法 在不同输入规模下哪个更占优势，与课本上介绍的算法渐进性能的相符吗 ？如果不相符，为什么？