C语言II博客作业02

1.作业头

这个作业属于哪个课程	https://edu.cnblogs.com/campus/zswxy/SE2020-2/
这个作业要求在哪里	https://edu.cnblogs.com/campus/zswxy/SE2020-2/homework/11825
这个作业的目标	更好的利用数组进行编程，学会使用不同的方法进行数的判断，加强对数组的使用
学号	<20209124>

一、本周教学内容&目标

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

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

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

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

二、本周作业

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

2.

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

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

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

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

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

要求：

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

测试数据：

输入	输出
10 5 6 4 7 11 15 9 3 8 4	6,4 7,3
6 7 5 9 14 17 23 56 1	1,9

解法二：

测试数据：

输入	输出
15 4 6 19 8 3 7 2 16 9	4,6 8,2 3,7
5 6 2 25 13 7 4 5 8	5，5

解法三：

测试数据：

输入	输出
10 6 4 8 15 23 6 2	4，6，2，8
10 9 12 4 9 8 6 18 13 7 2	2，8

2.请说明三种算法的区别是什么？你还可以给出更好的算法吗？（10分）
区别：方法1穷举法会将每一个数分别与数组中所有数字进行计算，并判断是否与自己输入的数字相等；方法2是做差然后在数组中查找该数；方法三二分法也是这三种方法中最快速高效的方法，用数组中每一个数字与所输入的数字做差，然后在数组中进行每次除二再寻找该数字的方式，大大减少了较大数据的寻找时间。
不可以，能力有限，给不出更好算法
2.3 请搜索有哪些排序算法，并用自己的理解对集中排序算法分别进行描述（5分）
1.选择排序

过程简单描述： 首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法我们称之为选择排序。
2.插入排序

我们在玩打牌的时候，你是怎么整理那些牌的呢？一种简单的方法就是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。当我们给无序数组做排序的时候，为了要插入元素，我们需要腾出空间，将其余所有元素在插入之前都向右移动一位，这种算法我们称之为插入排序。过程简单描述：

1、从数组第2个元素开始抽取元素。

2、把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。

3、继续选取第3，4，....n个元素,重复步骤 2 ，选择适当的位置插入。
3.冒泡排序

1、把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置....

我们对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样一趟比较交换下来之后，排在最右的元素就会是最大的数。

除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。
4.希尔排序

希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。

希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。

希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。
5.归并排序

将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。

通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ..... 直到全部小的数组合并起来。
6.快速排序

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。
7.计数排序

计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。

基本思想：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。
8.基数排序

基数排序的排序思路是这样的：先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小......

排到最后，就是一组有序的元素了。不过，他在以某位数进行排序的时候，是用“桶”来排序的。

由于某位数（个位/十位....，不是一整个数）的大小范围为0-9，所以我们需要10个桶，然后把具有相同数值的数放进同一个桶里，之后再把桶里的数按照0号桶到9号桶的顺序取出来，这样一趟下来，按照某位数的排序就完成了

冒泡排序和选择排序的区别：区别主要在交换的方式上每一轮都把最大或最小的元素筛选出来放在相应的位置上这是相同的但是对于每一轮比如第一轮要把1~n 中最大的那个放到n这个位置冒泡法每次比较和移动相邻的两项而选择排序每次交换当前项和第n项
我把代码写出来你就懂了：
冒泡：

for i:=1 to n-1 do
  if (a[i]>a[i+1]) then swap(i,i+1);

选择：

for i:=1 to n-1 do
  if (a[i]>a[n]) then swap(i,n);
(swap 表示交换）

总的来说，两种排序比较的次数是相同的
但交换的次数，选择排序是更少的
虽然两者的时间复杂度都是 O（n^2)
但通常，选择排序更快一点

2.4 请给出本周学习总结（15分）
1 学习进度条（5分）

周/日期	这周所花的时间	代码行	学到的知识点简介	目前比较迷惑的问题
第一周3.1-3.7	12h	420	学会用文件进行代码书写并回顾复习以往数据类型和表达式	文件的使用
第二周3.8-3.14	13h	520	学会利用数组编写代码，并学会运用不同的方法对数字进行排序与筛选	数组的排序

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

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

感悟
1.经过一周的学习，我们又学到了新知识，同时所出现的问题也越来越多，例如上周学的文件，这周仍然对于一些问题无法理解，或者无法得到有效解决，因此还是那句老话“自学才是最最最重要的”
2.本周我们又学习了新的知识，数组在编程中的运用非常的重要，重要性也就不言而喻了，懂得不算深刻，但同时对自己的要求就要更高
3.学习需要激情，生活也需要激情，如果都对生活失去了激情，那么学习自然就没有那么上心，所以路得继续走，学习也是一刻不能停，加油
4.老师经常会叫我们在自己脑子里种下一棵树，这不是一颗普通的树，他是我们的思维导图，不断学习，不断成长，不断发散开，只有这样才能成长为参天大树
5.对于学习中出现的问题要学会自己解决，戒躁戒急，慢慢来，相信自己，一切都会好起来