C语言II博客作业02

1.作业头

这个作业属于哪个课程	https://edu.cnblogs.com/campus/zswxy/SE2020-2
这个作业要求在哪里	https://edu.cnblogs.com/campus/zswxy/SE2020-2/homework/11825
这个作业的目标	<让我们掌握数组排序算法，学会自己找思路写代码。>
学号	<20209136>

一、本周教学内容&目标

第七章 数组 7.17.1 输出所有大于平均值的数

1.学生知道在哪种情况下可以使用构造数据类型—数组进行数据的处理

2.掌握用一维数组进行编程

3.掌握选择排序法和二分查找法

二、本周作业

2.1 完成PTA作业，并给出编程题完成截图（5分）

1.某医院想统计一下某项疾病的获得与否与年龄是否有关，需要对以前的诊断记录进行整理，按照0-18、19-35、36-60、61以上（含61）四个年龄段统计的患病人数占总患病人数的比例。

2.在主函数中首先输入一个整数N(1<N<=100),然后再输入N个整数存入数组中，然后用选择排序法对数组中的N个元素从大到小排序，最后输出数组所有元素。

2.2 题目：快速寻找满足条件的两个数

能否快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的值，为了简化起见，我们假设这个数组中肯定存在至少一组符合要求的解。

解法一：采用穷举法，从数组中任意取出两个数字，计算两者之和是否为给定的数字。

解法二：对数组中的每个数字arr[i]都判别Sum-arr[i]是否在数组中。

解法三：对数组进行排序，然后使用二分查找法针对arr[i]查找Sum-arr[i]。

要求：

1.根据三种解法给出相应的代码，并给出测试数据。（15分）

解法一：穷举法

测试数据

输入数据	输出数据
0 1 2 3 4 5 6 7 8 9	0 and 5 1 and 4 2 and 3
3 6 5 8 2 4 5 6 7 8	3 and 2

解法二：

测试数据

输入数据	输出数据
0 1 2 3 4 5 6 7 8 9	1 and 9 2 and 8 3 and 7 4 and 6
3 6 5 8 2 4 5 6 7 8	3 and 7 6 and 4 5 and 5 8 and 2 2 and 8 4 and 6

解法三：

输入数据	输出数据
10 0 1 2 3 4 5 6 7 8 9	1 and 9 2 and 8 3 and 7 4 and 6
10 3 6 5 8 2 4 5 6 7 8	3 and 7 6 and 4 5 and 5 8 and 2 2 and 8 4 and 6

2.请说明三种算法的区别是什么？你还可以给出更好的算法吗？（10分）

1.穷举法是把每一项元素都做了比较，思路比较简单易于操作，但是效率不高时间冗长。
2.第二种解法与第一种解法非常相像，只不过是做减法而已。
3.二分法是在排列好的数组中，取其中值作比较，再逐渐缩小范围继续比较，效率很高但最难操作。
4.暂时还在想更好的方法来排序，仍在学习中。

2.3 请搜索有哪些排序算法，并用自己的理解对几种排序算法分别进行描述（5分）

（1）常见的数组排序算法有七种：

第一种：冒泡排序

依次重复比较两个相邻的元素，按照大小顺序交换位置，直到没有相邻元素来比较，最大的元素逐渐被排到顶端，像极了鱼儿在水底吐泡泡，顾名思义叫做冒泡排序。

第二种：选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在最开始的位置，再从剩余的元素中重复该操作，最后放到排好的元素的末尾。直到排完所有元素。

第三种：直接插入排序

在少量数据的数组中，将一个数据按照关键码值插入到排好序的数据中，直到插入完为止。

第四种：二分插入排序

二分插入又称折半插入，也是一种稳定的插入排序方法，可以利用数组的特点快速定位指定索引的元素。

第五种：希尔排序

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，排序完成。

第六种：快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。把所有的排序工作分成两部分，一部分为最小部分，另一部分为最大部分，分开来单独排序，最后就可统一实现目标。

第七种：堆排序

是指利用堆这种数据结构所设计的一种排序算法，利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

2.4 请给出本周学习总结（15分）

（1）学习进度条（5分）

周/日期	代码行	这周所花的时间	学到的知识点简介	目前比较疑惑的问题
第一周03.01-03.07	510	20小时	回顾了数据类型和表达式，学习编写文件读写程序。	用代码把数据写入文件还不懂，学过的知识有点模糊了，新学的知识还有待消化。
第二周03.08-03.14	500	18小时	学会使用构造数据类型—数组进行数据的处理，掌握用一维数组进行编程和掌握选择排序法和二分查找法	二分查找法操作起来困难

（2）累积代码行和博客字数（5分）

（3）学习内容总结和感悟（5分）

1.学习内容总结

2.感悟：

1.现在感觉真正的进入到学习的状态了，新学的内容逐渐深入，真的需要自己去理解去感悟，老师一周就一节课，真正想掌握还得靠自己自学。

2.做一题就得记一题，争取做完一次作业就能熟练掌握一个知识点，并且能做到学以致用，举一反三。

3.目前如果对所学的知识还存在困惑的同学可以去网上看一看网课或者相关视频，这样能更好理解学习内容，趁大一空闲时间挺多还是得多多学习。

4.冒泡排序法与选择排序法的区别：用我自己的话来说，冒泡排序法先是相邻两个数之间进行比较，大的数放后面，每进行一轮都会筛选一个最大的数放在最后，同时下一轮就会减少一次比较次数，每一次都有大数往后排，就像鱼儿吐泡泡，水深压强大泡泡就小，越往上浮，压强越小泡泡就越大，所以叫冒泡排序法。选择排序是排序算法的一种，思想就是，每一轮寻找数组中最大的值或者最小的值，放在头部或者放入一个新的数组。这样经历一轮遍历，数组或者新数组就是排好序的，他的目的很明确，每次找最大值或者最小值。冒泡排序，每次比较的是相邻元素，选择排序比较的是固定位置的元素和集合中剩余的元素。一般情况下选择排序法比冒泡排序法效率高，冒泡排序在内循环交换，选择排序在外循环交换，两者存在交换次数差距。如果数组事先已经排好顺序，冒泡内循环的交换一次都不会执行，而选择排序每次还要和本身交换一次，此时冒泡效率高。但这种情况极少，所以从算法的角度看，选择排序法优于冒泡排序法。