C语言II博客作业02

• 2021 年 3 月 13 日
• 筆記

本周作业

2.1 完成PTA作业，并给出编程题完成截图

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

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

• 解法一
  
  

• 解法二
  
  

• 解法三
  
  

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

首先穷举法的复杂度是最高的，效率最低，解法二比较解法一，复杂度低了，但是效率还是一样的，二分法查找比较
前两者有一定的提升，不论是效率还是复杂度上。
我还了解道构造hash表，但是我写不出来代码，构造hash表用空间换取时间。

2.3 请搜索有哪些排序算法，并用自己的理解对集中排序算法分别进行描述

一.交换排序

• 1.冒泡排序:比较相邻的两个数，如果前者比后者大，则进行交换。每一轮排序结束，选出一个未排序中最大的数放到数组后面。

• 2.快速排序:选取一个基准元素，通常为数组最后一个元素（或者第一个元素）。从前向后遍历数组，当遇到小于基准元素的元素时，把它和左边第一个大于基准元素的元素进行交换。在利用分治策略从已经分好的两组中分别进行以上步骤，直到排序完成。

二.插入排序

• 1.直接插入排序: 和交换排序不同的是它不用进行交换操作，而是用一个临时变量存储当前值。当前面的元素比后面大时，先把后面的元素存入临时变量，前面元素的值放到后面元素位置，再到最后把其值插入到合适的数组位置
  。
• 2.希尔(shell)排序: 在直接插入排序的思想下设置一个最小增量dk,刚开始dk设置为n/2。进行插入排序，随后再让dk=dk/2,再进行插入排序，直到dk为1时完成最后一次插入排序，此时数组完成排序。

三.选择排序

• 1.直接选择排序: 依次选出数组最小的数放到数组的前面。首先从数组的第二个元素开始往后遍历，找出最小的数放到第一个位置。再从剩下数组中找出最小的数放到第二个位置。以此类推，直到数组有序。

• 2.堆(Heap)排序: 先把数组构造成一个大顶堆（父亲节点大于其子节点），然后把堆顶（数组最大值，数组第一个元素）和数组最后一个元素交换，这样就把最大值放到了数组最后边。把数组长度n-1,再进行构造堆，把剩余的第二大值放到堆顶，输出堆顶(放到剩余未排序数组最后面)。依次类推，直至数组排序完成。

四.归并排序: 归并算法应用到分治策略，简单说就是把一个答问题分解成易于解决的小问题后一个个解决，最后在把小问题的一步步合并成总问题的解。这里的排序应用递归来把数组分解成一个个小数组，直到小数组的数位有序，在把有序的小数组两两合并而成有序的大数组。

2.4 请给出本周学习总结

1 学习进度条

2 累积代码行和博客字数

3 学习内容总结和感悟

• 学习了数组,这样有些代码就可以简化了,可以更好的解决问题。
• 感觉已经落后别人挺多的了,要努力学习了。