第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; //存放其他数据 };
设计用于内排序的 InterSort clas类如下: class InterSort Class /内排序类 const int maxsize=10000;最多要排序的元素个数 public recType r; /1放顺序表中元素 public int length; /存放顺序表的长度 string sstr 用于返回排序时的每趟结果 public Inter SortClasso/构造函数,用于顺序表等初始化 R=new RecType Maxsize: length=0 h=new RadixNode0; /顺序表的基本运算及相关的排序算法
设计用于内排序的InterSortClass类如下 : class InterSortClass //内排序类 { … const int MaxSize=10000; //最多要排序的元素个数 public RecType [] R; //存放顺序表中元素 public int length; //存放顺序表的长度 string sstr; //用于返回排序时的每趟结果 public InterSortClass() //构造函数，用于顺序表等初始化 { R=new RecType[MaxSize]; length=0; h=new RadixNode(); } //顺序表的基本运算及相关的排序算法 }
9.2插入排序 插入排序的基本思想是:每次将一个待排序的记录按其关 键字大小插入到前面已经排好序的子表中的适当位置直到全 部记录插入完成为止。 两种插入排序方法: (1)直接插入排序(含二分插入排序) (2)希尔排序
9.2 插入排序 插入排序的基本思想是：每次将一个待排序的记录,按其关 键字大小插入到前面已经排好序的子表中的适当位置,直到全 部记录插入完成为止。 两种插入排序方法： （1）直接插入排序（含二分插入排序） （2）希尔排序
921直接插入排序 假设待排序的记录存放在数组R0.n-1中,排序过程的某 中间时刻,R被划分成两个子区间R|0.1和Rn-1,其中: 前一个子区间是已排好序的有序区,后一个子区间则是当前未 排序的部分,不妨称其为无序区。 直接插入排序的基本操作是将当前无序区的第1个记录R 插入到有序区R0.i1中适当的位置上,使R0.变为新的有 序区。这种方法通常称为增量法,因为它每次使有序区增加1 个记录
9.2.1 直接插入排序 假设待排序的记录存放在数组R[0..n-1]中，排序过程的某一 中间时刻，R被划分成两个子区间R[0..i-1]和R[i..n-1]，其中： 前一个子区间是已排好序的有序区，后一个子区间则是当前未 排序的部分，不妨称其为无序区。 直接插入排序的基本操作是将当前无序区的第1个记录R[i] 插入到有序区R[0..i-1]中适当的位置上，使R[0..i]变为新的有 序区。这种方法通常称为增量法，因为它每次使有序区增加1 个记录
有序区 无序区 R[0]…Ri 可. R[n-1] 一趟排序 01……R[i-]R]R[+1]1…Rn-1 有序区 无序区
R[0]R[i-1] 有序区 R[i]R [n-1 ] 无序区 一趟排序 R[0]R[i-1] R[i] R[i+1]R[n-1] 有序区 无序区
插入位置 RIOT R j=i-1 在有序区中插入R的过程
R[0] j R[i] j=i-1 插入位置 在有序区中插入R[i]的过程