作业头
| 这个作业属于哪个课程 | https://edu.cnblogs.com/campus/zswxy/SE2020-2 |
|---|---|
| 这个作业要求在哪里 | https://edu.cnblogs.com/campus/zswxy/SE2020-2/homework/11825 |
| 这个作业的目标 | <学会使用数组，学会利用使用二分法来解题> |
| 学号 | 20209120 |
一、本周教学内容&目标
第七章 数组 7.17.1 输出所有大于平均值的数
1.学生知道在哪种情况下可以使用构造数据类型—数组进行数据的处理
2.掌握用一维数组进行编程
3.掌握选择排序法和二分查找法
二、本周作业（总分：50分）
2.1 完成PTA作业，并给出编程题完成截图（5分）
1.
2.
2.2
2.2 题目：快速寻找满足条件的两个数
能否快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的值，为了简化起见，我们假设这个数组中肯定存在至少一组符合要求的解。
解法一：采用穷举法，从数组中任意取出两个数字，计算两者之和是否为给定的数字。
解法二：对数组中的每个数字arr[i]都判别Sum-arr[i]是否在数组中。
解法三：对数组进行排序，然后使用二分查找法针对arr[i]查找Sum-arr[i]。
要求：
1.根据三种解法给出相应的代码，并给出测试数据。（15分）
2.请说明三种算法的区别是什么？你还可以给出更好的算法吗？（10分）
1.
解法一：
解法二：
解法三：
2.
区别：
第一种：算法是最基础的也是最容易想到的。
第二种：算法较第一种更简单，也不难想到。
第三种：三种算法中第三种明显第三种最难想到，算法自我感觉比前两种都难，可能它更适用于处理大数据。
2.二分法是要在有序的数组中查找特定元素，将所有元素一分为二，找到中值，然后逐步缩小范围，此算法效率较高，运算时间较少目前我不能给出更好的算法。
（1）.冒泡排序：对一组数据，两个两个的依次比较，将小的数放到前面，大数放到后面。
（2）.选择排序：对一组数进行遍历，第一次遍历选择出最小的数，与下标为0的数进行交换，第二次从下表为1开始遍历，从余下的数中选择最小的数与当前下标为1的数进行交换，依次下去。
（3）.插入排序：主要分为直接插入排序和希尔排序。
（4）.归并排序：先将数组中的两个元素两两排序合并，然后在第一轮的基础上再将小组进行两两排序合并，依次类推，直到整个数组排序完成。
（5）.堆排序：将最小值和最大值交换位置，输出最大值，然后将预先的数再次调整为大顶堆，依次输出。
（6）.快速排序：找一个标准数，将比这个数小的放在左边，将比这个数大的放到右边，对这两组数再次分而治之，找到中间的数，将比这个数小的放在左边，将比其大的放到右边，依次类推，直到排序完成为止。
冒泡排序和选择排序的区别：
选择排序是通过进行多次比较选出每一次的最小值，每次进行时都会排除上一轮的最小值再将这一次的最小值选出，下一次也是如此，直至所有数都被选出为止。
冒泡排序也是要进行多次排序，与选择排序不同的是冒泡排序是依次比较相邻的数据，将每次相邻两个数中的最小值放置在前，下一轮也是如此直至数值被排序完成为止。
2.4 请给出本周学习总结（15分）
1 学习进度条（5分）
| 时间 | 所用时间 | 代码行数 |
|---|---|---|
| 第一周 | 18h | 308 |
| 第二周 | 21h | 234 |
2 累积代码行和博客字数（5分）
- 学习内容总结和感悟（5分）
