插入排序算法

思想：将整个数组分成已排（左边）和待排（右边）两个部分，开始时已排部分只有数组最左边的一个成员，其余成员均属于待排部分。排序时，每次取出待排部分最左边的一个值，根据它的大小插入已排部分的适应位置。这样，已排部分逐步扩大，待排部分逐步缩小，直到已排部分扩大到整个数组为止. 
import java.util.*; 

public class InsertSort{ 
public void InsertSorting(Comparable[] arr){ 
Comparable temp; 
for(int i=1;i<arr.length;i++){ 
int j=i; 
while(j>0 && arr[j].compareTo(arr[j-1])<0){ 
temp=arr[j]; 
arr[j]=arr[j-1]; 
arr[j-1]=temp; 
--j; 
} 
} 
} 

public void PrintArr(Comparable[] arr){ 
for(int i=0;i<arr.length;i++){ 
System.out.println(arr[i]); 
} 
} 
public static void main(String[] args){ 
Animal[] arr=new Animal[]{new Animal("dog"),new Animal("cat"),new Animal("rat"), 
new Animal("pig"),new Animal("fox"),new Animal("eel"),new Animal("ant"), 
new Animal("hen"),new Animal("bat")}; 
InsertSort is=new InsertSort(); 
is.InsertSorting(arr); 
is.PrintArr(arr); 
} 
} 

class Animal implements Comparable{ 
private String name; 
public Animal(String s){ 
name=s; 
} 
public int compareTo(Object o){ 
if(name.compareTo(((Animal)o).getName())>0) 
return 1; 
else if(name.compareTo(((Animal)o).getName())<0) 
return -1; 
else 
return 0; 
} 
public String getName(){ 
return name; 
} 
public String toString(){ 
return name; 
} 
}