西安交通大学：《计算机软件基础》第7单元 排序（刘志强）

第7单元 排序 计算机软件基础 The software bas ic of computer 下一页 主讲:刘志 西安文通大学 计算机教学实验中心

下一页 计算机软件基础 The software basic of computer 主讲：刘志强 西安交通大学 计算机教学实验中心 第7单元 排序

教学目标 ●了解有关排序的 基本概念 排序的典型算法 上一页 停止放映 下一页 第2页

下一页 上一页 停止放映 第 2 页 教学目标 ⚫ 了解有关排序的 –基本概念 –排序的典型算法

教学要求 通过本单元的学习,了解、掌握有关排序的: ●基本概念 排序、排序分类、算法稳定性 典型的排序算法 插入排序、选择排序、交换排序 快速排序、归并排序 上一页 停止放映 下一页 第3页

下一页 上一页 停止放映 第 3 页 教学要求 通过本单元的学习，了解、掌握有关排序的： ⚫ 基本概念 –排序、排序分类、算法稳定性 ⚫ 典型的排序算法 –插入排序、选择排序、交换排序 –快速排序、归并排序

基本概念 ●排序 ●排序分类 ●算法稳定性 上一页 停止放映 下一页 第4页

下一页 上一页 停止放映 第 4 页 一、基本概念 ⚫ 排序 ⚫ 排序分类 ⚫ 算法稳定性

排序( Sorting ●就是将记录按关键字递增(递减)的次序 排列起来,形成新的有序序列,称为排序。 设n个记录的序列为{R1,R2,…,Rn},其相 应关键字序列为{K1,K2,…,Kn},需确定 种排序P1,P2,,,Pn,使其相应的关键 字满足递增(升序),或递减(降序)的关系 Kp1≤Kp2≤...≤Kpn 上一页 或 停止放映 Kp1≥Kp2≥≥Kpn 下一页 第5页

下一页 上一页 停止放映 第 5 页 排序(Sorting) ⚫ 就是将记录按关键字递增(递减)的次序 排列起来,形成新的有序序列,称为排序。 设n个记录的序列为{R1,R2,…,Rn},其相 应关键字序列为{K1,K2,…,Kn},需确定 一种排序P1,P2,…,Pn,使其相应的关键 字满足递增(升序),或递减(降序)的关系: Kp1  Kp2 ... Kpn 或 Kp1  Kp2 ….  Kpn

排序分类 ●根据排序元素所在位置的不同,排序分: 内序和外芽序 ●内序 在排序过程中,所有元素调到内存中进行 的排序,称为内排序。内排序是排序的基 础。内排序效率用比较次数来衡量 外#序 上一页 在数据量大的情况下,只能分块排序,但 停止放映 块与块间不能保证有序。外排序用读/写 下一页 外存的次数来衡量其效率。 第6页

下一页 上一页 停止放映 第 6 页 排序分类 ⚫ 根据排序元素所在位置的不同,排序分: 内排序和外排序。 ⚫ 内排序 在排序过程中，所有元素调到内存中进行 的排序，称为内排序。内排序是排序的基 础。内排序效率用比较次数来衡量。 ⚫ 外排序 在数据量大的情况下，只能分块排序，但 块与块间不能保证有序。外排序用读/写 外存的次数来衡量其效率

内排序方法分类 内排序方法有许多种 按排序过程中依据的不同原则分类: 插入、交换、选择、归并和基数排序等; 按排序过程中所需工作量来区分: 简单排序(0(n)) 快速排序(0( nlogn)) 基数排序(0(d*n)) 上·排序过程中所需进行的操作 停止放映 比较两个关键字的大小 下一页 移动记录的位置 第7页

下一页 上一页 停止放映 第 7 页 内排序方法分类 ⚫ 内排序方法有许多种： –按排序过程中依据的不同原则分类： • 插入、交换、选择、归并和基数排序等； –按排序过程中所需工作量来区分： • 简单排序（O（n ）） • 快速排序（O（nlogn）） • 基数排序（O（d*n）） ⚫ 排序过程中所需进行的操作： –比较两个关键字的大小 –移动记录的位置 2

排序算法的稳定性 ●若待排序的序列中,存在多个具有相 同关键字的记录,经过排序,这些记 录的相对次序保持不变,则称该算法 是稳定的; ●若经排序后,记录的相对次序发生了 改变,则称该算法是不稳定的。 上一页 停止放映 下一页 第8页

下一页 上一页 停止放映 第 8 页 ⚫ 若待排序的序列中，存在多个具有相 同关键字的记录，经过排序，这些记 录的相对次序保持不变，则称该算法 是稳定的； ⚫ 若经排序后，记录的相对次序发生了 改变，则称该算法是不稳定的。 排序算法的稳定性

排序算法的数据结构 ●顺序存储结构(C语言描述) #define n struct record int key int otherterm t ypedef struct record RECOrd 上一页 RECORD file[N+1 停止放映 下一页 第9页

下一页 上一页 停止放映 第 9 页 ⚫ 顺序存储结构（C语言描述）： #define N n struct record { int key ； int otherterm； } ； typedef struct record RECORD； RECORD file[N+1]； 排序算法的数据结构

、典型排序算法 插入排序 选择排序 交换排序 快速排序 归并排序 上一页 停止放映 下一页 第10页

下一页 上一页 停止放映 第 10 页 二、典型排序算法 • 插入排序 • 选择排序 • 交换排序 • 快速排序 • 归并排序