思想:将整个数组分成已排(左边)和待排(右边)两个部分,开始时已排部分只有数组最左边的一个成员,其余成员均属于待排部分。排序时,每次取出待排部分最左边的一个值,根据它的大小插入已排部分的适应位置。这样,已排部分逐步扩大,待排部分逐步缩小,直到已排部分扩大到整个数组为止.
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;
}
}
责任编辑:小草