第9章内排序 9.1排序的基本概念 听谓排序,是要整理表中的记录,使之按关键字递增(或递 减)有序排列。其确切定义如下 输入:n个记录,R1,R1…,Rn1,其相应的关键字分别为 ko,k1,…,ykn1 输出:RoR;1…,Rn1,使得k0≤k≤…kn(或 ki0=k;12…,≥kn)。 本章仅考虑递增排序
9.1 排序的基本概念 所谓排序，是要整理表中的记录，使之按关键字递增（或递 减）有序排列。其确切定义如下： 输入： n个记录 ,R0 ,R1 ,…,Rn-1 , 其 相 应 的 关键 字 分 别 为 k0 ,k1 ,…,kn-1。 输出： Ri,0 ,Ri,1 ,…,Ri,n-1 , 使 得 ki,0≤ki,1≤…≤ki,n-1 ( 或 ki,0≥ki,1≥…≥ki,n-1 )。 本章仅考虑递增排序 第9章 内排序
算法的稳定性 当待排序记录的关键字均不相同时,排序的结果是惟一的 否则排序的结果不一定唯一。如果待排序的表中存在有多个 关键字相同的记录经过排序后这些具有相同关键字的记录之 间的相对次序保持不变则称这种排序方法是稳定的;反之若 具有相同关键字的记录之间的相对次序发生变化则称这种扎 序方法是不稳定的 内排序和外排序 在排序过程中,若整个表都是放在内存中处理,排序时 不涉及数据的内、外存交换,则称之为内排序;反之,若排 序过程中要进行数据的内、外存交换,则称之为外排序
当待排序记录的关键字均不相同时，排序的结果是惟一的, 否则排序的结果不一定唯一。如果待排序的表中,存在有多个 关键字相同的记录,经过排序后这些具有相同关键字的记录之 间的相对次序保持不变,则称这种排序方法是稳定的；反之,若 具有相同关键字的记录之间的相对次序发生变化,则称这种排 序方法是不稳定的。 在排序过程中，若整个表都是放在内存中处理，排序时 不涉及数据的内、外存交换，则称之为内排序；反之，若排 序过程中要进行数据的内、外存交换，则称之为外排序。 算法的稳定性 内排序和外排序
内排序的基本方法 内部排序的过程是一个逐步扩大记录的有序序 列长度的过程。 有序序列区元序序列区 经过一趟排序 有序序列区无序序列区
内排序的基本方法 内部排序的过程是一个逐步扩大记录的有序序 列长度的过程。 经过一趟排序 有序序列区 无 序 序 列 区 有序序列区 无 序 序 列 区
正序和反序 若待排序的表中元素已按关键字排好序,称此表中元素 为正序;反之,着待排序的表中元素的关键字顺序正好和排 好序的顺序相反,称此表中元素为反序 排序的分类 根据排序算法是否基于关键字的比较,将排序算法分为 基于比较的排序算法和不基于比较的排序算法。像插入排序、 交换排序、选择排序和归并排序都是基于比较的排序算法 而基数排序是不基于比较的排序算法
正序和反序 若待排序的表中元素已按关键字排好序，称此表中元素 为正序；反之，若待排序的表中元素的关键字顺序正好和排 好序的顺序相反，称此表中元素为反序。 排序的分类 根据排序算法是否基于关键字的比较，将排序算法分为 基于比较的排序算法和不基于比较的排序算法。像插入排序、 交换排序、选择排序和归并排序都是基于比较的排序算法； 而基数排序是不基于比较的排序算法
排序数据的组织 在本章中,以顺序表作为排序数据的存储结构(除基数 排序采用单链表外)。为简单起见,假设关键字类型为int 类型。待排序的顺序表中记录类型定义如下: struct RecType ∥记录类型 public int key; /1放关键字 public string data; /1放其他数据
排序数据的组织 在本章中，以顺序表作为排序数据的存储结构（除基数 排序采用单链表外）。为简单起见，假设关键字类型为int 类型。待排序的顺序表中记录类型定义如下： struct RecType //记录类型 { public int key; //存放关键字 public string data; //存放其他数据 };