第2章 算法基础

本章介绍一个贯穿本书的算法设计与分析的框架

2.1插入排序

算法思路

插入排序的工作方式像揭牌时排序手中的扑克牌。

使用插入排序来排序手中扑克牌
开始时，我们的左手为空并且桌子上的牌面向下。然后我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。
为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。
拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌

伪代码（算法说明）

插入排序伪代码过程命名为INSERTION-SORT,参数是一个数组A[1...n]，包含长度为n（n=A.length）的要排序的一个序列。

插入排序伪代码

\\Python 实现
def Insertion_sort(A):
    for j in range(1,len(A)):
        key=A[j]
        i=j-1
        while i>=0 and key<A[i]:
            A[i+1]=A[i]
            i=i-1
        A[i+1]=key
    return A;
A=[5,2,4,6,1,3]
print(Insertion_sort(A))

证明算法的正确性

循环不变式：循环的每次执行前后都为真的谓词
循环不变式的三条性质：

初始化：循环的第一次迭代之前，它为真
保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

插入排序的循环不变式：for 循环的每次迭代开始时，子数组A[1...j-1]由原来在A[1...j-1]中的元素组成，但现在已按序排列。

证明循环不变式的三条性质成立
前两条性质的证明类似于数学归纳法的基始步骤和归纳步骤

初始化：首先证明在第一次循环迭代之前（j=2），循环不变式成立
保持：证明每次迭代保持循环不变式
终止：研究在循环终止时发生了什么。（子数组A[1..n]由原来在A[1..n]中的元素组成，但以按序排列。子数组A[1..n]就是整个数组，我们推断出整个数组已排序。因此算法正确）