插入排序算法
public class InsertSortTest {
/**
* @param args
*/
public static void main(String[] args) {
int[] a={3,5,9,16,29,47,78,89,94};
int key=47;
int[] b=insertSort(a,key);
for(int i=0;i<b.length;i++){
System.out.print(b[i]+" ");
}
}
public static int[] insertSort(int[] unsorted,int key){
int len=unsorted.length;
int[] sorted=new int[len+1];
for(int i=0;i<len;i++){
//when key exists in edge of array
if(key<unsorted[0]){
sorted[0]=key;
System.arraycopy(unsorted, 0, sorted, 1, len);
}
if(key>unsorted[len-1]){
sorted[sorted.length-1]=key;
System.arraycopy(unsorted, 0, sorted, 0, len);
}
//when key exists in mid of array
if(key>unsorted[i]){
sorted[i]=unsorted[i];
}else{
sorted[i]=key;
System.arraycopy(unsorted, i, sorted, i+1, len-i);
break;
}
}
return sorted;
}
}
单元测试源码：（使用junit4）
public class InsertSortUnitTest {
@Test
public void testLT() {
int[] a={3,5,9,16,29,47,78,89,94};
int key=-5;
int[] result={-5,3,5,9,16,29,47,78,89,94};
int[] b=InsertSortTest.insertSort(a,key);
for(int i=0;i<result.length;i++){
assertEquals(result[i],b[i]);
}
}
@Test
public void testGT() {
int[] a={3,5,9,16,29,47,78,89,94};
int key=205;
int[] result={3,5,9,16,29,47,78,89,94,205};
int[] b=InsertSortTest.insertSort(a,key);
for(int i=0;i<result.length;i++){
assertEquals(result[i],b[i]);
}
}
@Test
public void testMid() {
int[] a={3,5,9,16,29,47,78,89,94};
int key=50;
int[] result={3,5,9,16,29,47,50,78,89,94};
int[] b=InsertSortTest.insertSort(a,key);
for(int i=0;i<result.length;i++){
assertEquals(result[i],b[i]);
}
}
@Test
public void testEqual(){
int[] a={3,5,9,16,29,47,78,89,94};
int key=47;
int[] result={3,5,9,16,29,47,47,78,89,94};
int[] b=InsertSortTest.insertSort(a,key);
for(int i=0;i<result.length;i++){
assertEquals(result[i],b[i]);
}
}
}
程序进一步优化：
public class InsertSortTest {
/**
* @param args
*/
public static void main(String[] args) {
Comparable[] a={3f,5f,9f,16f,29f,47f,78f,89f,94f};
Comparable key=47.78f;
Comparable[] b=insertSort(a,key);
for(int i=0;i<b.length;i++){
System.out.print(b[i]+" ");
}
}
public static Comparable[] insertSort(Comparable[] unsorted,Comparable key){
int len=unsorted.length;
Comparable[] sorted=new Comparable[len+1];
for(int i=0;i<len;i++){
//when key exists in edge of array
if(key.compareTo(unsorted[0])<0){
sorted[0]=key;
System.arraycopy(unsorted, 0, sorted, 1, len);
}
if(key.compareTo(unsorted[len-1])>0){
sorted[sorted.length-1]=key;
System.arraycopy(unsorted, 0, sorted, 0, len);
}
//when key exists in mid of array
if(key.compareTo(unsorted[i])>0){
sorted[i]=unsorted[i];
}else{
sorted[i]=key;
System.arraycopy(unsorted, i, sorted, i+1, len-i);
break;
}
}
return sorted;
}
}
单元测试的就略过了吧。