京火 限锡病 第九章排序 n概述 n插入排序 交换排序 a选择排序 归并排序 n基数排序 外排序
第九章 排序 ◼ 概述 ◼ 插入排序 ◼ 交换排序 ◼ 选择排序 ◼ 归并排序 ◼ *基数排序 ◼ *外排序
§9.1概述 排序:将一组杂乱无章的数据按一定的规律 顺次排列起来。 数据表dist:它是待排序数据对象的有限 集合。 排序码(ke以:通常数据对象有多个属性域, 即多个数据成员组成,其中有一个属性坷可 用来区分对象,作为排序依据。该域即为排 序码。每个数据表用哪个属性域作为排序码 ,要视具体的应用需要而定
◼ 排序：将一组杂乱无章的数据按一定的规律 顺次排列起来。 ◼ 数据表(datalist): 它是待排序数据对象的有限 集合。 ◼ 排序码(key): 通常数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可 用来区分对象, 作为排序依据。该域即为排 序码。每个数据表用哪个属性域作为排序码 ，要视具体的应用需要而定。 §9.1 概述
排序算法的稳定性:如果在对象序列中有两 个对象r和7i,它们的排序码和==k,且 在排序之前,对象r排在前面。如果在排 序之后对象r仍在对象r的前面,则称这 个排序方法是稳定的,否则称这个排序方法 是不稳定的。 内排序与外排序:内排序是指在排序期间 数据对象全部存放在内存的排序;外排序 是指在排序期间全部对象个数太多,不能 同时存放在内存,必须根据排序过程的要 求,不断在内、外存之间移动的排序
◼ 排序算法的稳定性: 如果在对象序列中有两 个对象r[i]和r[j], 它们的排序码 k[i] == k[j] , 且 在排序之前, 对象r[i]排在r[j]前面。如果在排 序之后, 对象r[i]仍在对象r[j]的前面, 则称这 个排序方法是稳定的, 否则称这个排序方法 是不稳定的。 ◼ 内排序与外排序: 内排序是指在排序期间 数据对象全部存放在内存的排序；外排序 是指在排序期间全部对象个数太多，不能 同时存放在内存，必须根据排序过程的要 求，不断在内、外存之间移动的排序
排序的时间开销:排序的时间开销是衡量 算法好坏的最重要的标志。排序的时间开销 可用算法执行中的数据比较次数与数据移动 次数来衡量。 算法执行时所需的附加存储:评价算法好 坏的另一标准。 算法运行时间代价的大略估算一般都安平均 情况进行估算。受对象排序码序列初始排列 及对泉个数影响较大的,需要按最好憤况和 最坏情况进行估算
◼ 排序的时间开销: 排序的时间开销是衡量 算法好坏的最重要的标志。排序的时间开销 可用算法执行中的数据比较次数与数据移动 次数来衡量。 ◼ 算法执行时所需的附加存储: 评价算法好 坏的另一标准。 ◼ 算法运行时间代价的大略估算一般都按平均 情况进行估算。受对象排序码序列初始排列 及对象个数影响较大的，需要按最好情况和 最坏情况进行估算
§9.2插入排序( Insert Sorting) 基本方法:每步将一个待排序的对象,按其排 序码大小,插入到前面已经排好序的一组对象 的适当位置上,直到对象全部插入为止。 1直接插入排序( Insert Sort 基本思想:当插入第i(21)个对象时前面 的v0,V1…Vi-1已经排好序。这时, 用Ⅴ的排序码依次与V-1,Vi-2],…的排 序码顺序进行比较,找到插入位置即将Ⅴ插 入,原来位置上的对象向后顺移
◼ 基本思想: 当插入第i (i 1) 个对象时, 前面 的V[0], V[1], …, V[i-1]已经排好序。这时, 用V[i]的排序码依次与V[i-1], V[i-2], …的排 序码顺序进行比较, 找到插入位置即将V[i]插 入, 原来位置上的对象向后顺移。 基本方法 : 每步将一个待排序的对象, 按其排 序码大小, 插入到前面已经排好序的一组对象 的适当位置上, 直到对象全部插入为止。 1.直接插入排序 (Insert Sort) §9.2 插入排序 (Insert Sorting)