顺序表查找类SqListSortclass（除基数排序外）//顺序表排序类public class SgListSortclassfinal int MAxN=100;//表示最多元素个数一//存放排序的元素RecType[] R;int n;//实际元素个数public void swap(int i,int j)//交换R[i]和R[j]RecType tmp=R[i];R[i]=R[j]; R[j]=tmp;LpublicvoidCreateR（int[]a）//由关键字序列a构造顺序表R[o..n-1]R=new RecType[MAXN];for （int i=o;i<a.length;i++)R[i]=new RecType(a[i]);n=a.length;public void Disp()//输出顺序表R[0..n-1]for（inti=o:i<n;i++）System.out.print(R[i].key+"");System.out.println();11/69
顺序表查找类SqListSortClass （除基数排序外） public class SqListSortClass //顺序表排序类 { final int MAXN=100; //表示最多元素个数 RecType[] R; //存放排序的元素 int n; //实际元素个数 public void swap(int i,int j) //交换R[i]和R[j] { RecType tmp=R[i]; R[i]=R[j]; R[j]=tmp; } public void CreateR(int[] a) //由关键字序列a构造顺序表R[0.n-1] { R=new RecType[MAXN]; for (int i=0;i<a.length;i++) R[i]=new RecType(a[i]); n=a.length; } public void Disp() //输出顺序表R[0.n-1] { for (int i=0;i<n;i++) System.out.print(R[i].key+" "); System.out.println(); } 11/69
publicvoidCreateR1（int[]a）//由关键字序列a构造R[1..n]，用于堆排序( R=new RecType[MAXN];for(int i=o;i<a.length;i++)R[i+1]=new RecType(a[i]);n=a.length;//输出顺序表R[1..n]，用于堆排序public void Disp1()(for(int i=1;i<=n;i++)System.out.print(R[i].key+"");System.out.println();各种基于比较的排序方法，后面讨论12/69
public void CreateR1(int[] a) //由关键字序列a构造R[1.n]，用于堆排序 { R=new RecType[MAXN]; for (int i=0;i<a.length;i++) R[i+1]=new RecType(a[i]); n=a.length; } public void Disp1() //输出顺序表R[1.n] ，用于堆排序 { for (int i=1;i<=n;i++) System.out.print(R[i].key+" "); System.out.println(); } //各种基于比较的排序方法，后面讨论 } 12/69
插入排序10.2基本思路有序区无序区一个一个地插入不是全局有序，全局有序区中的元素在后面排序中不再发生位置的改变主要的插入排序方法：（1）直接插入排序（2）折半插入排序（3）希尔排序13/69
有序区 无序区 一个一个地插入 不是全局有序，全局有序区中的元素在后面排序中不 再发生位置的改变 主要的插入排序方法： 13/69
直接插入排序10.2.1排序思路1.有序区无序区R[0]R[i-1]R[]R[n-1]......一趟排序R[0]R[i］]R[i-1]R[i+1]R[n-1]有序区无序区初始时，有序区只有一个元素R[0]i=1~n-1，共经过n-1趟排序14/69
1. 排序思路 有序区 R[0] . R[i-1] 无序区 R[i] . R[n-1] 有序区 R[0] . R[i-1] R[i] 无序区 R[i+1] . R[n-1] 一趟排序 初始时，有序区只有一个元素R[0] i＝1~n-1，共经过n-1趟排序 14/69
一趟直接插入排序：在有序区中插入R1的过程有序区R[0..i-1]R[i] 当R[i].key<R[i-1].key时7j-i-1tmp鹿分笑爵使后移R[j+1]=tmp使R[0..i有序扩大有序区15/69
j R[i] j=i-1 插入位置 一趟直接插入排序：在有序区中插入R[i]的过程。 有序区R[0.i-1] R[j+1]=tmp tmp 使R[0.i]有序 扩大有序区 R[j]大时便后移 当R[i].key<R[i-1].key时 15/69