Algorithms and DataStructures:Sorting 目录 第十章内部排序 1、 概述 插入排序 3、 快速排序 4、 选择排序 5、 归并排序 6、 基数排序 7、 讨论 SORT
1 物料管理 SORT Algorithms and DataStructures:Sorting 1、概述 2、插入排序 3、快速排序 4、选择排序 5、归并排序 6、基数排序 7、讨论 目录 第十章 内部排序
Algorithms and DataStructures:Sorting 1、概述 ·分类：内部排序：全部记录都可以同时调入内存进行的排序。 外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。 ·定义：设有记录序列：{R1、R2.Rn}其相应的关键字序列为： {K1、K2.Kn;若存在一种确定的关系：Kx<=Ky<=<=K 则将记录序列{R1、R2. Rn}排成按该关键字有序的序列： {Rx、Ry.Rz}的操作，称之为排序。 关系是任意的，如通常经常使用的小于、大于等关系。 ·稳定与不稳定：若记录序列中的任意两个记录Rx、Ry的关键字Kx=Ky;如果在 排序之前和排序之后，它们的相对位置保持不变，则这种排序方法 是稳定的，否则是不稳定的。 (有哪些排序方法是稳定的？哪些不稳定？？) define MAXSIZE 20 typedefstruct{ typedefint KeyType: RedType r[MAXSIZE+1];∥rO]空或作哨兵 typedefstruct{ int length; KeyType key; }SqList; InfoType otherinfo; }RedType; SORT
2 物料管理 SORT Algorithms and DataStructures:Sorting 1、概述 • 分类：内部排序：全部记录都可以同时调入内存进行的排序。 外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。 • 定义：设有记录序列：{ R1、R2 . Rn } 其相应的关键字序列为： { K1、K2 . Kn }; 若存在一种确定的关系： Kx <= Ky <= . <= Kz 则将记录序列 { R1、R2 . Rn } 排成按该关键字有序的序列： { Rx、Ry . Rz } 的操作，称之为排序。 关系是任意的，如通常经常使用的小于、大于等关系。 • 稳定与不稳定：若记录序列中的任意两个记录 Rx、Ry 的关键字 Kx = Ky ；如果在 排序之前和排序之后，它们的相对位置保持不变，则这种排序方法 是稳定的，否则是不稳定的。 (有哪些排序方法是稳定的？哪些不稳定？？） ＃ define MAXSIZE 20 typedef int KeyType； typedef struct { KeyType key; InfoType otherinfo; } RedType; typedef struct { RedType r [MAXSIZE + 1 ] ; // r[0] 空或作哨兵 int length; } SqList;
Algorithms and DataStructures:Sorting 1、概述 ■排序中的基本操作： (1)比较关键字大小 (2)移动记录 前个醭奇桥繩怼态多整孱磊跨圣業？霓后 ■待排序记录的存储方式： (1)存放套典共连续的一组存储单元史之记录之间的 关系由存储位置沃定，罪序必须移动记录； 集静意素来，：畏醉系由指针指不· (3)待排序记录本身存储在一组地址连续的存储单元 动，示出餐高显条盐 学过程甲不移动记录，「 聚语：骨接地阊量中斋阔蠡的 录的存储位置。 SORT
3 物料管理 SORT Algorithms and DataStructures:Sorting 1、概述 ◼ 排序中的基本操作： (1)比较关键字大小 (2)移动记录 前一种基本操作对大多数的排序方法是必须的，而后 一个操作可以通过改变记录的存储方式来予以避免。 ◼ 待排序记录的存储方式： (1)存放在地址连续的一组存储单元中，记录之间的 关系由存储位置决定，排序必须移动记录； (2)存在静态链表中，记录之间的关系由指针指示， 排序不用移动记录，只需修改指针； (3)待排序记录本身存储在一组地址连续的存储单元 内，同时附设一个指示记录存储位置的地址向量，排 序过程中不移动记录，而移动地址向量中这些记录的 地址，在排序结束后，再按照地址向量中的值调整记 录的存储位置
Algorithms and DataStructures:Sorting 1、概述 ■排序评价标准 执行时间 ◆比较次数 ◆移动次数 所需附加空间 算法复杂程度 SORT
4 物料管理 SORT Algorithms and DataStructures:Sorting 1、概述 ◼ 排序评价标准 执行时间 ◆比较次数 ◆移动次数 所需附加空间 算法复杂程度
Algorithms and DataStructures:Sorting 2、插入排序 基本方法：每步将一个待排序的记录按其关键字大小 插入到前面已排序表中的适当位置，直到全部插入完 为止。 SORT
5 物料管理 SORT Algorithms and DataStructures:Sorting 2、插入排序 ◼ 基本方法：每步将一个待排序的记录按其关键字大小 插入到前面已排序表中的适当位置，直到全部插入完 为止