第二章 算法基础

发表于   |   分类于

本章将要介绍一个贯穿本书的框架，后续的算法设计与分析都是在这个框架的=中进行的。

插入排序

我们的第一个算法（插入排序）求解第1章中引入的排序问题：

  • 输入：$n$ 个数的一个序列 $\langle a_1, a_2, \dotsm, a_n \rangle$ 。
  • 输出：输入序列的一个排列 $\langle a’_{1}, a’_{2}, \dotsm, a’_{n} \rangle$ ，满足 $a’_{1} \leq a’_{2} \leq \dotsm \leq a’_{n}$

我们希望排序的数也称为关键词。虽然概念上我们在排序一个序列，但是输入是以 $n$ 个元素的数组的形式出现的。

我们通常将算法描述为用一种伪代码书写的程序，该伪代码在许多方面类似于C、C++、Java、Python或Pascal。伪代码和真代码的区别在于，伪代码使用最清晰、最简介的表示方法来说明给定的算法。

插入排序，对于少量的元素排序，它是一个有效的算法。插入排序的工作方式像大家排序扑克牌一样。开始时，我们的左手为空并且桌面的牌面朝下。然后，我们每次从桌上拿一张牌，插入左手上正确的位置。为了找到一张牌的正确位置，我们从左到右将它与已经在手中的牌进行比较。这样拿在左手上的牌总是排序好的，原来这些牌都是桌子上牌堆中顶部的牌。

对于插入排序，我们将其伪代码过程命名为INSERTION-SORT，其中参数是一个数组 $A[1 \dotsm n]$，包含长度为 $n$ 的要排序的一个序列。（在代码中，$A$ 中元素的数目 $n$ 用 $A.length$ 表示）该算法原址排序输入的数：算法在数组 $A$ 中重排这些数，在任何时候，最多只有其中的常数个数字存储在数组外。在过程INSERTION-SORT结束时，输入数组 $A$ 包含排序好的输出序列。 

1
2
3
4
5
6
7
8
9
INSERTION-SORT(A)
    for j = 2 to A.length
        key = A[j]
        // Insert A[j] into the sorted sequence A[1...j - 1]
        i = j - 1
        while i > 0 and A[i] > key
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key