public class Sort {
 
 /**
  * 插入排序的基本思想为：首先å¯ÀL‰¾ä¸€ä¸ªæœ‰åºæ•°åˆ—，然后ž®†æ•°¾l„中的每个元素插入到该有序序列中åQ?br />   * 则该数组序列卛_¯å˜äؓ有序数列。具体实施办法äØ“åQŒé¦–选将½W¬ä¸€ä¸ªå…ƒç´ çœ‹ä½œæ˜¯ä¸€ä¸ªæœ‰åºåºåˆ—，然后
  * 从第二个元素开始遍历数¾l„，ž®†æ¯ä¸ªå…ƒç´ æ’入到从第一个元素到前一个元素的有序序列中，卛_¯å®?br />   * 成排序ã€?br />   * @param temp
  */
 /*
 public static void insertSort(int[] temp)
 {
  int length = temp.length;
  
  for (int i = 1; i < length; i++) // 把第一个元素看作一个有序序列，从第二个元素开始遍åŽ?br />   {
   int tempNo = temp[i];
   
   for (int j = 0; j < i; j++)
   {
    if (tempNo < temp[j])
    {
     for (int k = i; k > j; k--) // ž®†å…¶éåŽ†æ•°å’Œæ¯”较æ•îC¹‹é—´çš„æ•îC¾‹Æ¡å‘后移动一ä½?br />       temp[k] = temp[k-1];
     temp[j] = tempNo;
    }
   }
  }
 }
 */
 
 /**
  * javaeye上看到的另外一¿Uå†™æ³•ï¼Œä¸åŒä¹‹å¤„是其与前è¾ÒŽ(gu¨©)•°å­—一个一个比较，然后一‹Æ¡ä¸€‹Æ¡é€æ¸¿UÕdŠ¨ã€?br />   */
 /*
 public static void insertSort(int[] a) 
    { 
        for(int i = 1; i < a.length; i++) 
        { 
            int temp = a[i]; 
            int j = i - 1; 
            while (j >= 0 && temp < a[j]) 
            { 
                a[j+1] = a[j]; 
                j--; 
            } 
            a[j+1] = temp; 
        }  
    }
    */
 
 /**
  * 数据¾l“构书上原版½Ž—法的java代码实现
  */
 public static void insertSort(int[] temp)
 {
  int j = 0;
  int length = temp.length;
  int[] a = new int[length+1];
  System.arraycopy(temp, 0, a, 1, length);
  for(int i = 2; i < a.length; i++)
  {
   if(a[i] < a[i-1])
   {
    a[0] = a[i];
    a[i] = a[i-1];
    for (j = i - 2; a[i] < a[i-1]; j--)
    {
     a[j+1] = a[j];
    }
    a[j+1] = a[0];
   }
  }
  
  for (int i = 1; i < a.length; i++)
  {
   System.out.println(a[i]);
  }
 }
 
 /**
  * 折半插入排序½Ž—法的java实现
  * @param temp
  */
 public static void bInsertSort(int[] temp)
 {
  int length = temp.length;
  for (int i = 1; i < length; i++)
  {
   int tempVal = temp[i];
   int low = 0;
   int high = i - 1;
   while (low <= high)
   {
    int middle = (low + high) / 2;
    if (tempVal < temp[middle])
     high = middle - 1;
    else
     low = middle + 1;
   }
   for (int j = i; j > high + 1; j--)
    temp[j] = temp[j-1];
   temp[high+1] = tempVal;
  }
 }
 
 public static void buddleSort(int[] temp)
 {
     for (int i = 0; i < temp.length - 1; i++)
     {
      for (int j = i + 1; j < temp.length; j++)
      {
       if (temp[i] > temp[j])
       {
        int tempVal = temp[i];
        temp[i] = temp[j];
        temp[j] = tempVal;
       }
      }
     }
 }
 
 
 public static void main(String[] args)
 {
  int a[] = {113, 3, 24, 24, 78, 96};
  Sort.bInsertSort(a);
  //Sort.insertSort(a);
  //Sort.buddleSort(a);
  for (int i = 0; i < a.length; i++)
  {
   System.out.println(a[i]);
  }
 }

}