第十一章 排序 11排⑧的害惑 11.2围久绑感 13换排愿 114选择排感 115详排感 116含数排感 117各种的排序法的匙较和择
1 11.6 基数排序 11.1 排序的基本概念 11.2 插入排序 11.3 交换排序 11.4 选择排序 11.5 归并排序 11.7 各种内排序方法的比较和选择 第十一章 内排序
11排序的基本概念 排序是计算机内经常进行的一种操作,其目的 是将一组“无序”的记录序列调整为“有序”的 记录序列。 所谓排就是要整理表中的记录使之按关键字 递增(或递减)有序排列。其确切定义如下 物入:n个记录,R,R1…,Rn1其相应的关键字 分别为kk1,…,kn1 轴出:RnR12,Rn1,使得ko≤k1≤≤kn1 2 (或k≥k1≥…≥kn1)
2 所谓排序,就是要整理表中的记录,使之按关键字 递增(或递减)有序排列。其确切定义如下： 输入：n个记录,R0 ,R1 ,…,Rn-1 ,其相应的关键字 分别为k0 ,k1 ,…,kn-1。 输出：Rio,Ri1 ,…,Ri,n-1 ,使得ki0≤ki1≤…≤ki,n-1 (或ki0≥ki1≥…≥ki,n-1 )。 排序是计算机内经常进行的一种操作，其目的 是将一组“无序”的记录序列调整为“有序”的 记录序列。 11.1 排序的基本概念
当待排序记录的关键字均不相同时排序的结果 是惟一的否则排序的结果不一定惟 如果待排序的表中存在有多个关键字相同的记 录经过排序后这些具有相同关键字的记录之间的 相对次序保持不变则称这种排序方法是稳定的; 反之若具有相同关键字的记录之间的相对次序发 生变化则称这种排序方法是不稳定的 注意: 排序算法的稳定性是针对所有输入实例而言 的。即在所有可能的输入实例中,只要有一个实 例使得算法不满足稳定性要求,则该排序算法就 是不稳定的
3 当待排序记录的关键字均不相同时,排序的结果 是惟一的,否则排序的结果不一定惟一。 如果待排序的表中,存在有多个关键字相同的记 录,经过排序后这些具有相同关键字的记录之间的 相对次序保持不变,则称这种排序方法是稳定的； 反之,若具有相同关键字的记录之间的相对次序发 生变化,则称这种排序方法是不稳定的。 注意： 排序算法的稳定性是针对所有输入实例而言 的。即在所有可能的输入实例中，只要有一个实 例使得算法不满足稳定性要求，则该排序算法就 是不稳定的
内部排序:若整个排序过程不需要访问外存便能 完成,则称些类排序问题为内部排房。 外部排序待排序纪录的数量很大,以致内 次不能容纳全部纪录,在排序过程中尚需对外存 进行访问的排序过程。 内新排的方法 内部排序的过程是一个逐步扩大记录的有序序 列长度的过程。 有序序列区无序序列区 一趟排序 有序序列区无序序列区 逐步扩大记录有序序列长度的方法大致有下列几类 4入类进择类交换类归并类其他方法
4 ➢内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序 列长度的过程。 有序序列区 无 序 序 列 区 一趟排序 有 序 序列区 无 序 序列区 逐步扩大记录有序序列长度的方法大致有下列几类： 插入类 选择类 交换类 归并类 其他方法 内部排序：若整个排序过程不需要访问外存便能 完成，则称此类排序问题为内部排序。 外部排序：待排序纪录的数量很大，以致内存一 次不能容纳全部纪录，在排序过程中尚需对外存 进行访问的排序过程
1.插入类 将无序子序列中的一个或几个记录“插入 到有序序列中,从而增加记录的有序子序列的 长度。 2.选择类 从记录的无序子序列中“涉却关键字最小或 最大的记录,并将它加入到有序子序列中,以此 方法增加记录的有序子序列的长度。 3.交换类 通过“交”无序序列中的记录从而得到其中 关键字最小或最大的记录,并将它加入到有序子 序列中,以方法增加记录的有序子序列的长度
5 1.插入类 将无序子序列中的一个或几个记录“插入” 到有序序列中，从而增加记录的有序子序列的 长度。 3.交换类 通过“交换”无序序列中的记录从而得到其中 关键字最小或最大的记录，并将它加入到有序子 序列中，以此方法增加记录的有序子序列的长度。 2.选择类 从记录的无序子序列中“选择”关键字最小或 最大的记录，并将它加入到有序子序列中，以此 方法增加记录的有序子序列的长度