前段時間開始讀《算法導論》一書，第一次在譯本軟件類書看到這么大篇幅關于數學的內容，在驚訝之余更讓我堅定了讀完它的信念。虎頭蛇尾一直是我的弱點，就像之前看《head first design pattern》一樣，看了幾章后，因為英語的薄弱，暫停了（不過之后我一定會細細看完的）。所以前言往往是看得最細的，呵呵（有點象中國男籃）。在前言中，主要講了兩個排序算法：插入排序和分治法（快速排序）。于是先寫了個小測試，感受了兩種算法的時間復雜度：

insertionsort.java

/*
 * 插入排序法
 */
package com.algorithms.www;

public class insertionsort {
 private  ultility ut;
 private int[] Array;
 
 private void ShowArray(){
  ut.PrintArray(Array);
 }
 
 protected void sort(int[] arry)
 {
  int key,j =0;
  for(int i=1;i<=arry.length-1;i++)
  {
   key = arry[i];
   j = i-1;
   
   while((j>=0)&&(arry[j]>key))
   {
    arry[j+1]=arry[j];
    arry[j] = key;
    j--;
   }
  }
 }
 
 public  void Run()
 {
  ut = new ultility();
  Array = ut.GetIntArray(20000,20000);
  ut.StartTime();
  sort(Array);
  System.out.println("耗時："+ut.GetSeconds()+"毫秒");
  System.out.println("----------------------------------------");
 }
 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  insertionsort is = new insertionsort();
  is.Run();
  is.ShowArray();
 }

}

QuickSort.java

/*
 * 快速排序法
 */
package com.algorithms.www;

public class QuickSort {

 private final int Len = 10; //如果數組長度大于Len，則直接使用插入排序
 private insertionsort IsertSorts;
 private  ultility ut;
 private int[] Array;
 
 private void ShowArray(){
  ut.PrintArray(Array);
 }
 
 private void sort(int[] arry,int left,int right)
 {
  if ((arry.length -1)<= 10) {
   IsertSorts.sort(arry);
  }
  else{
   int i = left;
   int j = right;
   int middle = (left+right)/2;
   int Temp = 0;
   do{
    while((arry[i]    while((arry[j]>arry[middle])&&(j>middle)) j--;
    if(i<=j)
    {
     Temp = arry[i];
     arry[i] = arry[j];
     arry[j]=Temp;
     i++;
     j--;
    }
   }
   while(i<=j);
   if(left   if(right>i) sort(arry,i,right);
  }
 }
 
 public  void Run()
 {
  ut = new ultility();
  Array = ut.GetIntArray(20000,20000);
  ut.StartTime();
  sort(Array,0,Array.length-1);
  System.out.println("耗時："+ut.GetSeconds()+"毫秒");
  System.out.println("----------------------------------------");
 }

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  QuickSort qs = new QuickSort();
  qs.Run();
  qs.ShowArray();
 }

}

對20000個數進行排序，插入法耗時：5778ms（時間復雜度：n的平方）；快速插入法：10ms（時間復雜度：nlogn）