算法导论第二版：降序INSERTION-SORT与线性查找详解

在《算法导论》第二章的讲解中，我们首先探讨了"插入排序"的非升序版本。原版的插入排序(INSERTION-SORT)通常用于升序排列，但题目要求将其修改为按非升序进行。这种变化意味着在将当前元素`A[j]`插入有序子序列时，不再是寻找小于等于它的位置，而是大于等于。具体实现时，算法2.1-2-1通过一个额外的条件`A[i] < key`来决定元素的插入位置，这与标准插入排序的主要区别在于判断条件。 接下来，章节讨论了线性查找问题。线性查找是一种基础的搜索算法，目标是在给定的一列有序或无序数组`A`中找到指定值`v`的索引。线性查找的核心是顺序遍历数组，当找到目标元素时返回其索引，否则返回`NIL`。算法2.1-3-1展示了传统的for循环实现，其时间复杂度为Θ(𝑛)，表示查找次数与数组长度成正比。哨兵线性查找(Algorithm2.1-3-2)引入了一个虚拟的哨兵元素，改变了查找策略，当元素未在数组中找到时，从最后一个元素开始向后查找，提高了效率。递归版本的线性查找算法(Algorithm2.1-3-3)则是通过递归的方式实现，虽然形式上有所不同，但本质上的逻辑是一致的，都是逐个检查元素直到找到目标或遍历完整个数组。 这些基本的算法概念和实现细节是理解数据结构和算法分析的基础，它们在后续章节的学习中会起到关键作用。理解这些基本操作如何适应不同的排序和搜索需求，对于提升编程技能以及设计高效算法至关重要。在实际编程和解决问题时，根据具体场景选择合适的排序和搜索方法，能够显著提高程序的执行效率。