第第55章归纳法章归纳法5.1引言5.2两个简单的例子5.2.1选择排序5.2.2插入排序5.3基数排序5.4整数幂5.5多项式求值（HornerHorner规则）规则）5.6生成排列5.6.1第一种算法5.6.25.6.2第二种算法（略）第二种算法（略）5.75.7寻找多数元素寻找多数元素5.15.1引引言言考虑一个带有参数考虑一个带有参数nn的问题，在问题的实例的问题，在问题的实例中中nn通常表示事物的数目。通常表示事物的数目。当我们寻找这类问题解时，可从求解一个当我们寻找这类问题解时，可从求解一个带有小一点参数的相同问题开始，例如参数为带有小一点参数的相同问题开始，例如参数为n-n-11，，n/2n/2等。然后再把解推广到包含等。然后再把解推广到包含nn个物体的个物体的实例。这样，问题的解决就比较容易，这种方法实例。这样，问题的解决就比较容易，这种方法是基于众所周知的数学归纳法。是基于众所周知的数学归纳法。在本章的算法中，递归调用仅书写一次，这在本章的算法中，递归调用仅书写一次，这样的递归称为尾递归。在大多数情况下，尾递归样的递归称为尾递归。在大多数情况下，尾递归可以方便地转换为非递归过程（迭代过程）。可以方便地转换为非递归过程（迭代过程）。5.25.2二个简单的例子二个简单的例子5.2.15.2.1选择排序法选择排序法对数组对数组A[1..n]A[1..n]中中nn个元素的排序，可视为在个元素的排序，可视为在nn个元素中选择一个元素中选择一个最小的数，将其和个最小的数，将其和A[1]A[1]交换，然后对交换，然后对A[2..n]A[2..n]中中n-1n-1个元素排个元素排序。序。Selection(1)Selection(1)//A[1..n]//A[1..n]SelectionSortRec(2)SelectionSortRec(2)//A[2..n]//A[2..n]对数组对数组A[2..n]A[2..n]中中n-1n-1个元素的排序，可视为在个元素的排序，可视为在n-1n-1个元素中选个元素中选择一个最小的数，将其和择一个最小的数，将其和A[2]A[2]交换，然后对交换，然后对A[3..n]A[3..n]中中n-2n-2个元个元素排序。素排序。Selection(2)Selection(2)//A[2..n]//A[2..n]SelectionSortRec(3)SelectionSortRec(3)//A[3..n]//A[3..n]…………对数组对数组A[n-1..n]A[n-1..n]中中22个元素的排序，可视为在个元素的排序，可视为在22个元素中选择个元素中选择一个最小的数，将其和一个最小的数，将其和A[n-1]A[n-1]交换。交换。Selection(n-1)Selection(n-1)//A[n-1..n]//A[n-1..n]SelectionSortRec(n)SelectionSortRec(n)//A[n..n]//A[n..n]因余下元素仅为因余下元素仅为11个，排序终止。个，排序终止。这样，由归纳法得到选择排序法递归形式的算法这样，由归纳法得到选择排序法递归形式的算法SelectionSortRecSelectionSortRec。。算法算法5.15.1SelectionSortRec(SelectionSortRec(参见参见Page90-91)Page90-91)输入：输入：nn个元素的数组个元素的数组A[1..n]A[1..n]输出：按升序排列的数组输出：按升序排列的数组A[1..n]A[1..n]1.SelectionSortRec(1)1.SelectionSortRec(1)过程过程0.procedureSelectionSortRec(i)0.procedureSelectionSortRec(i)1.ifi
