Java實現插入排序

問題：用插入排序算法對n個對象的數組進行升序排序。

插入排序算法描述：插入排序的基本思想是，在一個已經排好序的子數組中查找一個位置，在找到的位置中插入一個元素，元素插入后，子數組依然有序。算法步驟如下：

（1）初始狀態，子數組只包含數組的第一個元素，這樣，子數組自然

    public <T extends Comparable<T>> void sort(T[] a) {

        // TODO Auto-generated method stub

        int length = a.length;

        for(int i = 0; i < length; i++) {

            T key = a[i];

            // 需要與key比較的元素的位置

            int j = i - 1;

            /**


         * j >= 0保證a[j]存在； 
         * a[j].compareTo(key) > 0保證a[j] > key, a[j]的位置需要后移， 
         * 這時（a[j]后移之后，j自減1之前），j就是key的候選位置； 
         * 如果是因為j < 0而退出while循環的，說明子數組中沒有小于key的元素， 
         * 也就是說，0是key的正確位置。 
         */  
        while (j >= 0 && a[j].compareTo(key) > 0) {  
            // 元素后移一個位置  
            a[j+1] = a[j];  
            // 需要比較的元素的位置前移  
            j--;  
        }  
        // j+1就是key的正確位置  
        a[j+1] = key;  
    }  

}  </pre> 


 是有序的。
 （2）從數組的第二元素起，每一個元素依次插入子數組中的某一個位置，每次插入后，子 數組保持有序。查找插入位置的方法是：把待插入元素與子數組中的元素從右至左依次比較，比待插入元素大的元素就右移一個位置，遇到不比待插入元素大的元 素，就把待插入元素插入到這個元素的后面；如果子數組中沒有不比待插入元素大的元素，子數組中的所有元素都將右移一個位置，待插入元素插入到子數組的第一 個位置。