插入排序

引用

插入排序策略:排序值列中的前2个值，并在必要时交换它们。在相对于前2个值（有序的）的适当位置插入值列的第三个值。然后，在相对于前 3个值（有序的）的适当位置插入值列的第4个值。每进行一次插入操作，有序子集中的数值个数将递增1。重复该过程，直至值列中的所有值都按照次序排列为 止。插入过程需要移动数组中的其他值，为插入的元素腾出存储空间。

//写法1
public class InsertionSort {  
      
    public static void insertSort(int[] a){  
        int j;  
          
        for(int p = 1; p < a.length; p++){  
              
            int temp = a[p];  
            for(j = p; (j > 0) && (temp < a[j-1]); j--){  
                a[j] = a[j-1];  
            }  
            a[j] = temp;  
        }  
          
    }  
      
    public static void main(String[] args){  
        int[] b = {9,8,5,2,1,7,3,4,8888,43,23525,232,12,34,53,75,13,15,17};  
        insertSort(b);  
        for(int i = 0; i < b.length; i++)  
            System.out.print(b[i] + " , ");  
    }  
  
} 

//写法2
public class InsertionSort2 {  
      
    public static void insertSort(Comparable[] data){  
        int j;  
        for(int p = 1; p < data.length; p++){  
            Comparable key = data[p];  
            for(j = p; j > 0 && (key.compareTo(data[j-1]) < 0); j--)  
                data[j] = data[j-1];  
            data[j] = key;  
        }  
    }  
      
    public static void main(String[] args){  
        Comparable[] b = {6,3,1,8,22,34,2,12,15,7,99,11};  
        insertSort(b);  
        for(int i = 0; i < b.length; i++)  
            System.out.print(b[i] + ",");  
    }  
  
}