package sort;
public class SortTest {
  public static void main(String[] args) throws Exception{
      int[] d={52, 39, 67, 95, 70, 8, 25, 52};
    SeqList seqList=new SeqList(20);
    for (int i = 0; i < d.length; i++) {
      RecordNode r=new RecordNode(d[i]);
      seqList.insert(seqList.length(), r);
    }
    seqList.display();
/*    seqList.insertSort();
 * 
*/    
    seqList.insert(0, new  RecordNode(0));
    seqList.insertSortWithGuard();
    seqList.display(9);
  }
}

package sort;
/*
 * 顺序表的
 */
public class RecordNode {
  public Comparable key;//关键字
  public Object element;//数据元素
  public RecordNode(){//无参构造函数
  } 
  public RecordNode(Comparable key){
    this.key=key;
  }
  public RecordNode(Comparable key,Object element){
    this.key=key;
    this.element=element;
  }
/*  public String toString(){//重写toStirng()
    return "["+key+","+element+"]";
  }*/
}

package sort;
/*
 * 我的数据结构>>>插入排序
 */
public class SeqList {
  public RecordNode[] r;//结点数组
  public int curLen;//顺序表长度
  public SeqList(){}
  public SeqList(int maxSize){
    this.r=new RecordNode[maxSize];
    this.curLen=0;
  }
  public int length(){
    return curLen;
  }
  /*
   * 插入操作
   */
  public void insert(int i,RecordNode x) throws Exception{
    if(this.curLen==this.r.length){
      throw new Exception("顺序表已满");
    }
    if(i<0 || i>this.curLen){
      throw new Exception("插入位置不合理");
    }
    for(int j=this.curLen;j>i;j--){
      this.r[j]=this.r[j-1];
    }
    this.r[i]=x;
    this.curLen++;
  }
  public void display() {
    for (int i = 0; i < this.curLen; i++) {
      System.out.print(" "+r[i].key.toString());
    }
    System.out.println();
  }
  public void display(int sortMode){
    int i;
    if(sortMode==9)
      i=1;
    else
      i=0;
    for(;i<this.curLen;i++){
      System.out.print(" "+r[i].key.toString());
    }
    System.out.println();
  }
  public void insertSort(){
    RecordNode temp;
    int i,j;
    for(i=1;i<curLen;i++){
      temp=r[i];
      //t<r[j]
      for(j=i-1;j>=0&&temp.key.compareTo( r[j].key)<0;j--){
        r[j+1]=r[j];
      }
      r[j+1]=temp;
    }
  }
  public void insertSortWithGuard(){
    int i, j;
        for (i = 2; i <this.curLen; i++) {      //n-1趟扫描
            r[0] = r[i]; //将待插入的第i条记录暂存在r[0]中，同时r[0]为监视哨
            for (j = i - 1; r[0].key.compareTo(r[j].key) < 0; j--) { //将前面较大元素向后移动
                r[j + 1] = r[j];
            }
            r[j + 1] = r[0];          // r[i]插入到第j+1个位置
        //    System.out.println("第" + i + "趟: ");
        //    display();
        }
  }
}