大学计算机----计算思维视角-电子教案第9章 算法设计.pptx

信息技术基础;9.1算法

9.1.1算法的概念

9.1.2算法复杂度

9.2查找

9.2.1顺序查找算法

9.2.2二分查找算法

9.3排序

9.3.1插入排序算法

9.3.2折半插入排序算法

本章小结

;;9.1.1算法的概念;9.1.1算法的概念;9.1.1算法的概念;9.1.1算法的概念;【例9.2】求的值

步骤如下：

S1：计算1和2的乘积，结果为2。

S2：计算S1的结果和3的乘积，结果为6。

S3：计算S2的结果和4的乘积，结果为24;首先设置两个变量，分别为a和i，a和i的初始值分别为1和2，并规定i的值小于等于4,具体步骤为：

S1：计算a和i的乘积，并将所得结果赋值给a，即a=a*i。

S2：将i的值加1，即i=i+1。

S3：判断i的值是否小于等于4，如果是，则返回S1继续按顺序执行；如果不是，则结束执行，算法结束，此时a中的值即为最终结果。;不同的算法可能需要不同的时间和空间来解决同一问题。那么对于同一问题，我们怎么来衡量不同算法的优劣呢？一个算法的优劣可以用算法的复杂度来衡量。对于计算机来说，算法的复杂度越高，占用计算机的时间和空间资源也就越高，所以衡量算法的复杂度主要从时间和空间入手，即时间复杂度和空间复杂度。;时间复杂度;?;;顺序查找也称为线形查找，适应于顺序存储结构或链接存储结构的线性表。顺序查找算法属于无序查找算法的一种。

顺序查找算法的基本思想：首先给定一个待查找的表，这个表的元素可以是有序的也可以是无序的。然后从表的一端开始顺序扫描元素，每次扫描一个元素。将扫描到的元素与给定的元素进行比较，若两个元素相等则表示查找成功；若扫描到另一端仍没有找到与给定元素相等的元素，则表示查找失败。;顺序查找算法的步骤如下：

S1：给定一个待查找的线性表A。

S2：选定一个查找对象，即给定元素k。

S3：从一端开始扫描线性表A，每次扫描一个元素。

S4：将扫描到的元素a[i]与给定元素k进行比较，若两个元素相等，则停止查找，元素a[i]即为查找的正确结果；若扫描到另一端仍没有找到与给定元素k相等的元素，则表示查找失败并结束查找。;?;?;;二分查找也称为折半查找，属于有序查找算法的一种。二分查找要求查找表中的元素是有序的，如果是无序的，则先要进行排序操作。

二分查找算法的指导思想：首先给定一个有序的查找表。其次在查找表的中间节点将查找表分为两个子表并扫描中间节点的元素。再次将中间节点的元素与给定的元素进行比较，若两个元素相等则查找成功；若中间节点的元素小于给定元素，则在右子表进行递归操作；若中间节点的元素大于给定元素，则在左子表进行递归操作。这样进行递归，直到查找到正确的元素或者表中没有这样的元素结束递归。;二分查找算法的步骤如下：

S1：给定一个待查找的有序表A。

S2：选定一个查找对象，即给定元素k。

S3：在查找表的中间节点将查找表分为两个子表并扫描中间节点的元素a。

S4：将扫描到的元素a与给定元素k进行比较，若两个元素相等则查找成功并结束查找；若a小于k，则在右子表进行递归操作；若a大于k，则在左子表进行递归操作。在查找到正确的元素或表中没有所需的元素时结束递归。;?;?;9.3.1插入排序算法;什么是排序？;9.3.1插入排序算法;9.3.1插入排序算法;插入排序是一种简单直观且稳定的排序算法。

其基本思想是：已知一个有序的数据序列，要求在这个有序数据序列中插入一个数，要求插入后此数据序列仍然有序，直至全部插完为止。

我们手中的扑克牌即为“已知有序数列”，每次抓的新牌为“插入的数据”，抓完所有扑克牌后手中的扑克牌依旧是“有序数列”，在算法实现中，我们需要设立“哨兵”来保存我们当前待排序数据。;S1：从第一个元素a[1]开始，该元素认为已经被排序。

S2：取出下一个待排序元素a[i]，令key=a[i]。

S3：在已经排序的元素序列中从后向前扫描，

令j=i-1,如果a[j]key，则令i=i-1。

S4：重复S3，直至a[j]key不成立。

S5：将新元素插入到该位置。

S6：重复步骤S2～S5，直至整个数据为有序数列。;给定无序数列12、5、43、7、18、25、18*、13（其中18*表示第二个18），将其通过插入排序算法变为有序数列的具体过程如下：;S2：当前key为5，由于5小于12，故5插在12左边。;S4：当前key为7，由于7大于5，故7插在5和12之间。;S6：当前key为25，由于25大于18，故25插在18和43之间。;S8：