get_product_contenthtml
第3章chapter3
算 法 思 维第2章讲述了计算过程的正确性与图灵机的通用性。假设我们已知一个问题是可计算的，可能存在许多计算过程去解决该问题。算法思维的目的是找出求解该问题的巧妙的计算过程，使得计算时间短、使用的计算资源少。巧妙的计算过程所体现的方法称为算法。3.1从一个实例看算法我们从计算机领域内的一个经典问题——排序问题开始。排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列按照大小关系调整为“有序”的记录序列。为了简单起见，假设排序的记录都是正整数；这些正整数的个数是已知的；这些正整数各不相同；要把这些正整数从小到大排序。为了求解排序问题，人们发展了各种各样的算法，例如冒泡排序、选择排序、快速排序、归并排序、堆排序等。在这一节里以冒泡排序算法为例介绍算法是如何运行的，在后续的章节中还会介绍更复杂的快速排序算法。冒泡排序的原理是： 每次将相邻的数字进行比较，按照小的排在左边，大的排在右边进行交换。这样一趟过去后，的数字被交换到了后的位置，然后再从头开始进行两两比较交换，直到比较到倒数第二个数时结束，以此类推。举例如下。 假设原始待排序数组6, 2, 4, 1, 5, 9趟排序(外循环)： 次比较，6>2交换交换前状态 6, 2, 4, 1, 5, 9→交换后状态2, 6, 4, 1, 5, 9第二次比较，6>4交换交换前状态 2, 6, 4, 1, 5, 9→交换后状态2, 4, 6, 1, 5, 9第三次比较，6>1交换交换前状态 2, 4, 6, 1, 5, 9→交换后状态2, 4, 1, 6, 5, 9第四次比较，6>5交换交换前状态 2, 4, 1, 6, 5, 9→交换后状态2, 4, 1, 5, 6, 9第五次比较，6<9不交换◆计算机科学导论第◆3章算法思维第二趟排序(外循环)： 次比较，2<4不交换第二次比较，4>1交换交换前状态 2, 4, 1, 5, 6, 9→交换后状态2, 1, 4, 5, 6, 9第三次比较，4<5不交换第四次比较，5<6不交换第三趟排序(外循环)： 次比较，2>1交换交换前状态 2, 1, 4, 5, 6, 9→交换后状态1, 2, 4, 5, 6, 9第二次比较，2<4不交换第三次比较，4<5不交换第四趟排序(外循环)无交换。第五趟排序(外循环)无交换。排序完毕，输出终结果1 2 4 5 6 9。“冒泡排序”这个名字的由来是因为大的数字会经由交换慢慢“浮”到数列的，就像气泡从水底冒上来一样。下面给出算法的形式化描述。冒泡排序算法输入： 待排序的数组A，数组A的长度n。输出： 排好序的数组A。算法描述： for i=1 to n-1for j=1 to n-iif A\[j\]>A\[j 1\]exchangeA\[j\] with A\[j 1\].一般地，可以采用如下来自高德纳教授的算法定义高德纳.计算机程序设计艺术： 第1卷 基本算法［M］.3版.苏运霖,译.北京： 国防工业出版社，2002.。高德纳的算法定义一个算法是一组有穷的规则，给出求解特定类型问题的运算序列，并具备下列五个特征。 （1） 有穷性： 一个算法在有限步骤之后必然要终止。（2） 确定性： 一个算法的每个步骤都必须精确地（严格地和无歧义地）定义。（3） 输入： 一个算法有零个或多个输入。（4） 输出： 一个算法有一个或多个输出。（5） 能行性： 一个算法的所有运算必须是充分基本的，原则上人们用笔和纸可以在有限时间内精确地完成它们。冒泡排序的算法描述定义了求解排序问题的一组有穷的规则，这组规则符合算法的五个特征。(1) 有穷性。分析可知，冒泡排序的外层循环需执行n-1次；对于确定的i，内层循环需执行n-i次。因此，算法在∑n-1i=1(n-i)=n(n-1)/2步内必然终止。
