USTC算法基础课：作业1-非升序INSERT-SORT与二进制加法

本次分享的内容是关于中国科学技术大学(USTC)的算法基础课程在2013年第一次习题课上的教学内容，主要包括两个部分的作业练习。 第一个作业涉及对经典的插入排序算法(INSERT-SORT)进行修改，使其按照非升序而非降序进行排序。原始的插入排序是通过查找已排序部分的正确位置来插入新元素，若要改为非升序，只需将第五行条件 `A[i]>key` 修改为 `A[i]<key`。插入操作相应地调整，即当遇到比目标值大的元素时，向左移动元素，直到找到合适的位置。 第二个作业则聚焦于二进制整数相加的问题。题目要求设计一个伪代码实现，将两个n位二进制整数A和B相加，结果以n+1位的二进制形式存入数组C。在这个过程中，需要一个临时变量Key来存储计算结果，以及一个标志flag表示进位，确保每次加法操作后正确更新C数组和flag的状态。 接着，是关于选择排序算法的讨论。选择排序是一种简单直观的排序方法，它的核心步骤是每次从未排序的部分中找到最小元素并放到已排序部分的末尾。这里给出的伪代码展示了这一过程，循环不变式是 `i` 的值小于剩余未排序元素的数量。选择排序的最好和最坏情况都是线性时间复杂度O(n^2)，这是因为无论数组如何排列，比较的次数总是与元素数量的平方成正比。 最后，作业还要求分析选择排序的运行时间，由于在每一轮中都需要遍历剩余的元素以寻找最小值，因此无论数组初始状态如何，比较次数都是O(n)，从而得出总的运行时间为O(n^2)。 这次习题课主要考察了学生对基本排序算法的理解和实现能力，以及在特定场景下解决问题的技巧。通过这些习题，学生可以加深对算法原理的掌握，同时提升编程实践能力。