第十章内部排序 概迷 令插入排序 快速排序 令选择排序 令归并排序 基数排序 各种内排方法比较
❖概述 ❖插入排序 ❖快速排序 ❖选择排序 ❖归并排序 ❖基数排序 ❖各种内排方法比较 第十章内部排序
概迷 排序:将一个数据元素的任意序列,重新 排列成一个按关键字有序的序列。 数据表( datalist):它是待排序数据对象的 有限集合。 主关键字(key):数据对象有多个属性域, 即多个数据成员组成,其中有一个属性城可用 来区分对象,作为排序依据,称为关键字。也 称为排序码
概 述 ◼ 排序：将一个数据元素的任意序列，重新 排列成一个按关键字有序的序列。 ◼ 数据表(datalist): 它是待排序数据对象的 有限集合。 ◼ 主关键字(key): 数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用 来区分对象, 作为排序依据，称为关键字。也 称为排序码
排序方法的稳定性:如果在对象序列中有两 个对象r和rj它们的排序码k[i==kil, 且在排序之前,对象r排在r前面。如果在 排序之后,对象r仍在对象r的前面,则称 这个排序方法是稳定的,否则称这个排序方法 是不稳定的。 n内排序与外排序:内排序是指在排序期间 数据对象全部存放在内存的排序;外排序是 指在排序期间全部对象个数太多,不能同时 存放在内存,必须根据排序过程的要求,不 断在内、外存之间移动的排序
◼ 排序方法的稳定性: 如果在对象序列中有两 个对象r[i]和r[j], 它们的排序码 k[i] == k[j], 且在排序之前, 对象r[i]排在r[j]前面。如果在 排序之后, 对象r[i]仍在对象r[j]的前面, 则称 这个排序方法是稳定的, 否则称这个排序方法 是不稳定的。 ◼ 内排序与外排序: 内排序是指在排序期间 数据对象全部存放在内存的排序；外排序是 指在排序期间全部对象个数太多，不能同时 存放在内存，必须根据排序过程的要求，不 断在内、外存之间移动的排序
排序的时间开销:排序的时间开销是 衡量算法好坏的最重要的标志。排序的 时间开销可用算法执行中的数据比较次 数与数据移动次数来衡量
◼ 排序的时间开销: 排序的时间开销是 衡量算法好坏的最重要的标志。排序的 时间开销可用算法执行中的数据比较次 数与数据移动次数来衡量
内排序分类 依不同原则 插入排序、交换排序、选择排序、归 并排序、和计数排序等。 依所须工作量 简单排序-时间复杂度o(m2) 先进排序方法-时间复杂度o(nlgn) 基数排序-时间复杂度odn)
内排序分类 • 依不同原则 插入排序、交换排序、选择排序、归 并排序、和计数排序等。 • 依所须工作量 简单排序---时间复杂度o(n2) 先进排序方法---时间复杂度o(n logn) 基数排序---时间复杂度o(d.n)