C语言II博客作业02

这个作业属于哪个课程	https://edu.cnblogs.com/campus/zswxy/CST2020-3
这个作业要求在哪里	https://edu.cnblogs.com/campus/zswxy/CST2020-3/homework/11806
这个作业的目标	知道在哪种情况下可以使用构造数据类型—数组进行数据的处理，用一维数组进行编程，选择排序法和二分查找法
学号	20209020

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

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

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

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

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

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

要求：

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

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

解法一（穷举法）：遍历数组中的每一个数，将满足条件（两数相加等于sum）输出，运用了双for语句，其时间复杂度为N（N-1）/2即O（N^2）；
解法二：与解法一有相似之处，遍历数组中的每一个数，将满足条件（sum减去一个数，判断另一个数是否在数组中）输出，运用了双for语句，其时间复杂度是O（Nlog2N）；
解法三（二分查找法）：先将数组中的数从小到大按顺序排列，再利用二分查找法找出目标数，其时间复杂度是O（2log2N）；
区别：三种不同的解法，所用时间逐级递减，并且，解法一二存在一个弊端：当数组中的数很多时，解法三大大减少了所需的时间，使得程序更加完美。
注：二分查找法：（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x；如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

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

排序算法：

冒泡，选择，插入，希尔，快速，归并，堆，基数，计数；

冒泡算法：

它重复地走访过要排序的数列，依次比较两个元素，如果他们的顺序错误就把他们交换过来。重复地进行直到没有再需要交换，说明该数列已经排序完成。（依次比较相邻的两个数，正序则不动，倒序则交换位置，如此循环，直到整个数组为有序为止）

选择排序：

选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
1·从待排序序列中，找到关键字最小的元素
2·如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换
3·从余下的 N - 1 个元素中，找出关键字最小的元素，重复进行直到排序结束

快速排序：

从数列中挑出一个元素作为基准。重新排列数列，把所有的比基准小的放在基准前面，反之放在后面（一样大可任意一边）完成后基准处在分区的中间位置。

插入排序：

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在从后向前扫描的过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间通过递归调用把小于基准元素和大于基准元素的子序列进行排序。

归并排序：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；设定两个指针，最初位置分别为两个已经排序序列的起始位置；比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；重复步骤3直到某一指针达到序列尾；将另一序列剩下的所有元素直接复制到合并序列尾。

希尔排列：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列个数k，对序列进行k 趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

堆排列：

指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

基数排列：

是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

桶排列：

是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

计数排列：

不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。