计算机导论 教学课件 作者 祁亨年 主编 汪杭军 高志刚 副主编第6章 算法与数据结构.ppt

《计算机导论 教学课件 作者 祁亨年 主编 汪杭军 高志刚 副主编第6章 算法与数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《计算机导论》IntroductionofComputerScienceSchoolofInformationEngineeringZhejiangForestryCollege第6章算法与数据结构6.1算法概述6.2经典排序算法6.3算法策略6.4数据结构概述6.5线性表6.6树和图6.1算法概述6.1算法概述6.2经典排序算法6.3算法策略6.4数据结构概述6.5线性表6.6树和图6.1算法概述（定义）计算机解题一般可分解成若干操作步骤,通常把对特定问题的求解步骤的描述称为算法。程序可以看作是用计算机语言描述的算法。6.1算法概述（特性）算法的五

2、个重要特性有穷性：一个算法必须保证执行有限步后结束；确定性：算法的每一步骤必须有确切的定义；可行性：算法原则上能够精确地运行，且人们用笔和纸做有限次运算后即可完成。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；6.2经典排序算法6.1算法概述6.2经典排序算法6.2.1冒泡排序6.2.2插入排序6.2.3快速排序6.3算法策略6.4数据结构概述6.5线性表6.6树和图6.2经典排序算法排序问题就是将一组可比较大

3、小的元素按从小到大(或从大到小)的顺序排列。现在主要的算法重要有：比较排序算法冒泡排序选择排序插入排序快速排序堆排序基数排序基数排序桶排序6.2经典排序算法(冒泡排序1/5)冒泡排序是最简单的排序方法基本思想：将待排序的元素看作是竖着排列的“气泡”，较小的元素相当于比较轻的气泡，从而要不断往重的气泡上面浮。在冒泡排序算法中我们要对这个“气泡”序列进行若干轮处理。每一轮处理都自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序出现“轻”的元素在下面，就交换它们的位置。显然，处理一轮之后，“最轻”的元素就浮到了最高

4、位置；处理第二轮之后，“次轻”的元素就浮到了次高位置。在进行第二轮处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i轮处理时，不必检查第i位以上的元素，因为经过前面i-1轮的处理，它们已正确地排好序。6.2经典排序算法（冒泡排序2/5）冒泡排序算法步骤如下：Step1：对于数组item中的1至n个数据，先将第0位和第1位数据进行比较，如果item[0]

5、n-1位。Step2：然后，对2至n个数据进行同样操作，则具有次大值的数据被安置在第n-2位上。Step3：重复以上过程，每次的移动都向最终排序的目标前进，直至没有数据需要交换为止。6.2经典排序算法（冒泡排序3/5）冒泡排序程序代码：voidBubbleSort（intitem[]，intlength）{inti,j；/*定义两个整数变量i,j*/inttemp；/*定义一个用于暂时存储一个数的整数变量*/for(i=0；i

6、if(item[j]>item[j+1]){/*当item[j]>item[j+1]时，item[j]与item[j+1]交换*/temp=item[j]；/*将item[j]赋给temp*/item[j]=item[j+1]；/*将item[j]赋给item[j+1]*/item[j+1]=temp；/*将将item[j+1]赋给temp*/}}}6.2经典排序算法（冒泡排序4/5）举例：依然以绪论中的排序任务为例：将3、74、23、89、22、99、65、109、55、45十个数按从小到大的顺序排列。冒泡排序算法产生以下的排序过程：第1遍：3、2

7、3、74、22、89、65、99、55、45、109第2遍：3、23、22、74、65、89、55、45、99、109第3遍：3、22、23、65、74、55、45、89、99、109第4遍：3、22、23、65、55、45、74、89、99、109第5遍：3、22、23、55、45、65、74、89、99、109第6遍：3、22、23、45、55、65、74、89、99、109第7遍：3、22、23、45、55、65、74、89、99、109第8遍：3、22、23、45、55、65、74、89、99、109第9遍：3、22、23、45、55、65、

8、74、89、99、109结果应为：3、22、23、45、55、65、74、89、99、1096.2经典排序算