java插入排序算法

/**


插入排序：
*
每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。
/

public class InsertSort {

/**
 * 排序算法的實現，對數組中指定的元素進行排序
 *
 * @param array
 *            待排序的數組
 * @param from
 *            從哪里開始排序
 * @param end
 *            排到哪里
 * @param c
 *            比較器
 */
public void insert(Integer[] array, int from, int end) {

    /*
     * 第一層循環：對待插入（排序）的元素進行循環 從待排序數組斷的第二個元素開始循環，到最后一個元素（包括）止
     */
    for (int i = from + 1; i <= end; i++) {
        /**
         * 第二層循環：對有序數組進行循環，且從有序數組最第一個元素開始向后循環 找到第一個大于待插入的元素
         * 有序數組初始元素只有一個，且為源數組的第一個元素，一個元素數組總是有序的
         */
        for (int j = 0; j < i; j++) {
            Integer insertedElem = array[i];// 待插入到有序數組的元素
            // 從有序數組中最一個元素開始查找第一個大于待插入的元素
            if ((array[j].compareTo(insertedElem)) > 0) {
                // 找到插入點后，從插入點開始向后所有元素后移一位
                move(array, j, i - 1);
                // 將待排序元素插入到有序數組中
                array[j] = insertedElem;
                break;
            }
        }
    }

    // =======以下是java.util.Arrays的插入排序算法的實現
    /*
     * 該算法看起來比較簡潔一j點，有點像冒泡算法。 將數組邏輯上分成前后兩個集合，前面的集合是已經排序好序的元素，而后面集合為待排序的
     * 集合，每次內層循從后面集合中拿出一個元素，通過冒泡的形式，從前面集合最后一個元素開
     * 始往前比較，如果發現前面元素大于后面元素，則交換，否則循環退出
     *
     * 總感覺這種算術有點怪怪，既然是插入排序，應該是先找到插入點，而后再將待排序的元素插
     * 入到的插入點上，那么其他元素就必然向后移，感覺算法與排序名稱不匹，但返過來與上面實
     * 現比，其實是一樣的，只是上面先找插入點，待找到后一次性將大的元素向后移，而該算法卻 是走一步看一步，一步一步將待排序元素往前移
     */
    /*
     * for (int i = from; i <= end; i++) { for (int j = i; j > from &&
     * c.compare(array[j - 1], array[j]) > 0; j--) { swap(array, j, j - 1);
     * } }
     */
}

/**
 * 數組元素后移
 *
 * @param array
 *            待移動的數組
 * @param startIndex
 *            從哪個開始移
 * @param endIndex
 *            到哪個元素止
 */
public void move(Integer[] array, int startIndex, int endIndex) {
    for (int i = endIndex; i >= startIndex; i--) {
        array[i + 1] = array[i];
    }
}

/**
 * 測試
 *
 * @param args
 */
public static void main(String[] args) {
    Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7, 15, -1, -9, 0 };
    InsertSort insertSort = new InsertSort();
    insertSort.insert(intgArr, 0, intgArr.length - 1);
    for (Integer intObj : intgArr) {
        System.out.print(intObj + " ");
    }
}

}</pre>