数据结构的第九讲.pptVIP

第九讲 基本排序算法和查找算法 主要内容 9.1 基本排序算法 9.2 基本查找算法 9.1 基本排序算法 9.1 基本排序算法 基本概念 插入排序 冒泡排序 选择排序 基本概念 排序： 将一组杂乱无章的数据按一定的规律顺次排列起来。 数据表(datalist): 它是待排序数据对象的有限集合。 关键字(key): 通常数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分对象, 作为排序依据。该域即为关键字。 每个数据表用哪个属性域作为关键字，要视具体的应用需要而定。 基本概念 排序算法的稳定性: 如果在对象序列中有两 个对象 r [ i ]和r [ j ] 它们的关键字k[i] == k[j] , 且在排序之前, 对象r [ i ]排在r [ j ]前面。 如果在排序之后, 对象r [ i ]仍在对象r [ j ]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 基本概念 内排序与外排序: 内排序是指在排序期间数据对象全部存放在内存的排序； 外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。 基本概念 内部排序的过程是一个逐步扩大记录的“有序序列”区域的长度的过程。 基本概念 大多数排序方法在排序过程中将出现如动画所示“有序”和“无序”两个区域 ，其中有序区内的记录已按关键字非递减有序排列，而无序区内为待排记录，通常称“使有序区中记录数目增加一个或几个”的操作过程为“一趟排序”。 按何种策略扩大有序区域将导致不同的排序方法。 例如在无序区域中选取一个关键字最小记录加到有序区域中的排序方法称为“选择类”的排序法. 除此之外还有插入类、交换类、归并类和计数类等排序方法。 基本概念 排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。 排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。 算法运行时间代价的大略估算一般都按平均情况进行估算。 对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。 基本概念 算法执行时所需的附加存储: 评价算法好坏的另一标准。 注意：在这里我们针对的是无序数组进行相关排序！ 插入排序 (Insert Sort) 直接插入排序 直接插入排序 直接插入排序的算法 直接插入排序的算法 从上述排序过程可见，排序中的两个基本操作是： （关键字间的）比较和（记录的）移动。 因此排序的时间性能取决于排序过程中这两个操作的次数。 从直接插入排序的算法可见，这两个操作的次数取决于待排记录序列的状态，当待排记录处于“正序” 的情况时，所需进行的关键字比较和记录移动的次数最少，反之，当待排记录处于“逆序” 的情况时，所需进行的关键字比较和记录移动的次数最多。 算法分析 设待排序对象个数为n, 则该算法的主程序执行n-1趟。 关键字比较次数和对象移动次数与对象排序码的初始排列有关。 最好情况下, 排序前对象已按关键字从小到大有序, 每趟只需与前面有序对象序列的最后一个对象比较1次, 移动0次对象, 总的关键字比较次数为 n-1, 对象移动次数为 0。 算法分析 最坏情况下, 第 i 趟时第 i 个对象必须要做i 次比较，要做i +1次数据移动。 则总关键字比较次数KCN和对象移动次数RMN分别为 算法分析 在平均情况下的关键字比较次数和对象移动次数约为 n2/4。 直接插入排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。 插入排序 (Insert Sort) 折半有哪些信誉好的足球投注网站( Binary Search) 折半插入排序的算法 折半插入排序 折半插入排序 当 n 较大时, 总关键字比较次数比直接插入排序的最坏情况要好得多, 但比其最好情况要差。 在对象的初始排列已经按关键字排好序或接近有序时, 直接插入排序比折半插入排序执行的关键字比较次数要少。折半插入排序的对象移动次数与直接插入排序相同, 依赖于对象的初始排列。 折半插入排序只能减少排序过程中关键字比较的时间，并不能减少记录移动的时间，因此折半插入排序的时间复杂度仍为O (n2)。 冒泡排序 (Bubble Sort) 基本方法是： 设待排序对象序列中的对象个数为 n。最多作 n-1 趟，i = 1, 2, ?, n-1 。 在第 i 趟中从后向前，j = n-1, n-2, ?, i，顺次两两比较V[j-1].key和V[j].key。 如果发生逆序，则交换V