数据结构的第九讲.ppt

《数据结构的第九讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、一个人接受科技教育得到的最大收获，是那些能够受用一生的一般性智能工具。—GeorgeForsythe，《计算机科学家到来以前我们做什么》，1968第九讲基本排序算法和查找算法主要内容9.1基本排序算法9.2基本查找算法9.1基本排序算法9.1基本排序算法基本概念插入排序冒泡排序选择排序5基本概念排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(datalist):它是待排序数据对象的有限集合。关键字(key):通常数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为关键字。每个数据表用哪个属性域作

2、为关键字，要视具体的应用需要而定。6基本概念排序算法的稳定性:如果在对象序列中有两个对象r[i]和r[j]它们的关键字k[i]==k[j],且在排序之前,对象r[i]排在r[j]前面。如果在排序之后,对象r[i]仍在对象r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。7基本概念内排序与外排序:内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。8基本概念内部排序的过程是一个逐步扩大记录的“有序序列”区域的长度的过程。9基

3、本概念大多数排序方法在排序过程中将出现如动画所示“有序”和“无序”两个区域，其中有序区内的记录已按关键字非递减有序排列，而无序区内为待排记录，通常称“使有序区中记录数目增加一个或几个”的操作过程为“一趟排序”。按何种策略扩大有序区域将导致不同的排序方法。例如在无序区域中选取一个关键字最小记录加到有序区域中的排序方法称为“选择类”的排序法.除此之外还有插入类、交换类、归并类和计数类等排序方法。10基本概念排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的大略估算一

4、般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。11基本概念算法执行时所需的附加存储:评价算法好坏的另一标准。注意：在这里我们针对的是无序数组进行相关排序！12插入排序(InsertSort)1、直接插入排序插入排序的准则是，在有序序列中插入新的记录以达到扩大有序区的长度的目的。一趟直接插入排序的基本思想则是:在对记录序列R[1..n]的排序过程中，区段R[1..i-1]中的记录已按关键字非递减的顺序排列，将R[i]插入到有序序列R[1..i-1]中，使区段R[1..i]中的记录按关键字非

5、递减顺序排列。13直接插入排序R[1..n]表示记录序列的长度为n，1..n表示它们的序号(下标)连续地从1至n。14直接插入排序由此实现一趟插入排序的步骤为：1)在R[1..i-1]中查找R[i]的插入位置，即确定j(0≤j＜i)使得R[1..j].key≤R[i].key＜R[j+1..i-1].key2)将R[j+1..i-1]中的记录后移一个位置；3)将R[i]插入到j+1的位置。15直接插入排序的算法voidinsertion_sort(elementlist[],intn){/*对一个数组list进行直接插入排序*/inti,j;eleme

6、ntnext;/*element为待定数据类型*/for(i=1;i=0&&next.key

7、排序的算法可见，这两个操作的次数取决于待排记录序列的状态，当待排记录处于“正序”的情况时，所需进行的关键字比较和记录移动的次数最少，反之，当待排记录处于“逆序”的情况时，所需进行的关键字比较和记录移动的次数最多。17算法分析设待排序对象个数为n,则该算法的主程序执行n-1趟。关键字比较次数和对象移动次数与对象排序码的初始排列有关。最好情况下,排序前对象已按关键字从小到大有序,每趟只需与前面有序对象序列的最后一个对象比较1次,移动0次对象,总的关键字比较次数为n-1,对象移动次数为0。18算法分析最坏情况下,第i趟时第i个对象必须要做i次比较，要做i+1

8、次数据移动。则总关键字比较次数KCN和对象移动次数RMN分别为19算法分析在平均情况下的关键字