排序问题和插入排序

排序问题和插入排序

排序问题和插入排序排序问题 插入排序 小结和作业

排序问题和插入排序

排序问题排序的定义 内部排序和外部排序 内部排序方法的分类

排序问题和插入排序

排序的定义排序是计算机内经常进行的一种操作， 排序是计算机内经常进行的一种操作，其目的是 将一组“无序”的记录序列调整为“ 将一组“无序”的记录序列调整为“按关键字有 序”的记录序列。 的记录序列。 52, 49, 80, 36, 14, 58, 61, 23, 97, 75

14, 23, 36, 49, 52, 58, 61 ,75, 80, 97

排序问题和插入排序

排序的定义一般情况下， 一般情况下， 假设含n个记录的序列为 个记录的序列为{ 假设含 个记录的序列为 R1, R2, …, Rn } , 其相应的关键字序列为 { K1, K2, …,Kn } , 这些关键字相互之间可以进行比较， 这些关键字相互之间可以进行比较，即在 它们之间存在着这样一个关系 ： Kp1≤Kp2≤…≤Kpn 按此固有关系将上式记录序列重新排列为 { Rp1, Rp2, …,Rpn } , 的操作称作排序 排序。 的操作称作排序。

排序问题和插入排序

排序的定义关键字(key): 关键字(key): 数据对象有多个属性域, 数据对象有多个属性域, 即多个数据成员组 其中有一个属性域可用来区分对象, 成, 其中有一个属性域可用来区分对象, 作 为排序依据，称为关键字 也称为排序码 关键字。 排序码。 为排序依据，称为关键字。也称为排序码。

排序问题和插入排序

排序的定义排序方法的稳定性: 排序方法的稳定性个对象r[i]和 如果在对象序列中有两 个对象 和r[j], 它们 且在排序之前, 对象r[i]排 的排序码 k[i] = k[j] , 且在排序之前 对象 排 前面。 在r[j]前面。 前面 如果在排序之后, 对象r[i]仍在对象 的前面, 仍在对象r[j]的前面 如果在排序之后 对象 仍在对象 的前面 则称这个排序方法是稳定的 稳定的, 则称这个排序方法是稳定的 否则称这个排序 方法是不稳定的 不稳定的。 方法是不稳定的。

排序问题和插入排序

内部排序和外部排序由于待排序的记录数量不同， 由于待排序的记录数量不同，使得排序过程中 涉及的存储器不同，可将排序方法分为： 涉及的存储器不同，可将排序方法分为：1.内部排序：整个排序过程不需要访问外存便能 1.内部排序：整个排序过程不需要访问外存便能 内部排序 完成。 完成。 2.外部排序：参加排序的记录数量很大， 2.外部排序：参加排序的记录数量很大，整个序 外部排序 列的排序过程不可能在内存中完成 不可能在内存中完成。 列的排序过程不可能在内存中完成。

排序问题和插入排序

内部排序方法的分类内部排序的过程是一个逐步扩大 逐步扩大记录的有 逐步扩大 有 序序列长度的过程。 序序列长度 有序序列区 无 序 序 列 区

有序序列区

无 序 序 列 区

排序问题和插入排序

内部排序方法的分类基于不同的“扩大 有序序列长度的方法， 扩大” 方

法， 扩大 方法 内部排序方法大致可分下列几种类型： 内部排序方法内 部 排 序 方 法

1.插入排序 1.插入排序 2.交换排序 2.交换排序 3.选择排序 3.选择排序 4.归并排序 4.归并排序 5.基数排序 5.基数排序

排序问题和插入排序

各种排序方法的定义插入排序：将无序子序列中的一个或几个记录 插入排序：将无序子序列中的一个或几个记录 插入”到有序序列中， “插入”到有序序列中，从而增加记录的有序 子序列的长度。 子序列的长度。 交换排序：通过“交换” 交换排序：通过“交换”无序序列中的记录从而 得到其中关键字最小或最大的记录，并将它加入 最小或最大的记录 得到其中关键字最小或最大的记录，并将它加入 到有序子序列中 到有序子序列中，以此方法增加记录的有序子序 列的长度。 列的长度。

排序问题和插入排序

各种排序方法的定义选择排序： 选择排序：从记录的无序子序列中“选择”关键字最小或 从记录的无序子序列中“选择”关键字最小或 最大的记录 并将它加入到有序子序列中 的记录， 有序子序列中， 最大的记录，并将它加入到有序子序列中，以 此方法增加记录的有序子序列的长度。 此方法增加记录的有序子序列的长度。

排序问题和插入排序

各种排序方法的定义归并排序： 归并排序：通过“归并” 通过“归并”两个或两个以上的记录有序 子序列，逐步增加记录有序序列的长度。 子序列，逐步增加记录有序序列的长度。

基数排序： 基数排序：是一种借助多关键字排序的思想对单逻辑 关键字进行排序的方法。 关键字进行排序的方法。

排序问题和插入排序

内部排序方法的分类待排记录的数据类型定义如下: 待排记录的数据类型定义如下:#define MAXSIZE 1000 // 待排顺序表最大长度 typedef int KeyType; // 关键字类型为整数类型 typedef struct { KeyType key; } RcdType; // 关键字项 // 记录类型 InfoType otherinfo; // 其它数据项

排序问题和插入排序

内部排序方法的分类typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置 闲置 int length; // 顺序表长度 } SqList; // 顺序表类型

排序问题和插入排序

插入排序一趟插入排序的基本思想： 一趟插入排序的基本思想： …… 此处隐藏：552字，全部文档内容请下载后查看。喜欢就下载吧 ……