设计用于内排序的 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]的过程