//本程序取自Clifford A.Shaffer著張銘等譯“數(shù)據(jù)結(jié)構(gòu)與算法分析”第 157 頁，例8.2.1
//插入排序問題解法
//insertion sort
import java.io.*;
class Examp8_2_1
 {
  static void inssort(int[] array)
     {
     for(int i=1;i<array.length;i++)
      for(int j=i;(j>0)&&(key(array,j)<key(array,j-1));j--)
       swap(array,j,j-1);
     }
   public static void swap(int[] q,int i,int j)
     {
      int temp;
      temp=q[i];q[i]=q[j];q[j]=temp;
     }
  public static int key( int [] q,int p)
     {  return q[p];}
  public static void main(String args[]) 
     {
     int[] a={42,20,17,13,28,14,23,15};
     System.out.println("插入排序之前");
     for(int i=0;i<=a.length-1;i++)
     System.out.print(a[i]+"  ");
     System.out.println();
   inssort(a);
     System.out.println("插入排序之后");
     for(int i=0;i<=a.length-1;i++)
     System.out.print(a[i]+"  ");
     System.out.println();
    }
 }