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、插入排序 ◼ 基本方法：每步将一个待排序的记录按其关键字大小 插入到前面已排序表中的适当位置，直到全部插入完 为止
Algorithms and DataStructures:Sorting 2、插入排序 1、直接插入排序 e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。 0 2 3 4 5 36 24 10 6 12 r[0]用作哨兵。共执行5遍操作。 每遍操作：先将元素复制内容放入[0]，再将本元素同已排序的序列，从尾 开始进行比较。在已排序的序列中寻找自己的位置，进行插入。或者寻找 不到，则一直进行到哨兵为止。意味着本元素最小，应该放在1]。 每一遍，排序的序列将增加一个元素。如果序列中有个元素，那么最多 进行n遍即可。以 6 SORT
6 物料管理 SORT Algorithms and DataStructures:Sorting 6 r[0] 用作哨兵。共执行 5 遍操作。 每遍操作：先将元素复制内容放入r[0]，再将本元素同已排序的序列，从尾 开始进行比较。在已排序的序列中寻找自己的位置，进行插入。或者寻找 不到，则一直进行到哨兵为止。意味着本元素最小，应该放在r[1] 。 每一遍，排序的序列将增加一个元素。如果序列中有 n 个元素，那么最多 进行n 遍即可。 （实际只需要n-1遍） 2、插入排序 e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。 1、直接插入排序 0 1 2 36 24 10 6 12 3 4 5
Algorithms and DataStructures:Sorting 2、插入排序 1、直接插入排序 e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。 0 1 2 3 4 5 36 24 10 6 12 卫 24 36 24 > SORT
7 物料管理 SORT Algorithms and DataStructures:Sorting 7 2、插入排序 e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。 1、直接插入排序 0 1 2 36 24 10 6 12 3 4 5 24 36 24 i
Algorithms and DataStructures:Sorting 2、插入排序 1、直接插入排序 e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。 0 1 2 3 4 5 36 24 10 6 12 ↓ 24 36 8 SORT
8 物料管理 SORT Algorithms and DataStructures:Sorting 8 2、插入排序 e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。 1、直接插入排序 0 1 2 36 24 10 6 12 3 4 5 24 36 i
Algorithms and DataStructures:Sorting 2、插入排序 1、直接插入排序 e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。 0 1 2 3 4 5 36 24 10 6 12 卫 24 24 36 9 SORT
9 物料管理 SORT Algorithms and DataStructures:Sorting 9 2、插入排序 e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。 1、直接插入排序 0 1 2 36 24 10 6 12 3 4 5 24 36 i 24
Algorithms and DataStructures:Sorting 2、插入排序 1、直接插入排序 e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。 0 1 2 3 4 5 36 24 10 6 12 ↓ 10 24 36 10 10 SORT
10 物料管理 SORT Algorithms and DataStructures:Sorting 10 2、插入排序 e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。 1、直接插入排序 0 1 2 36 24 10 6 12 3 4 5 10 36 i 24 10