/**
 * 插入排序：
 *
 * 每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。
 *
 */
 
public class InsertSort {
 
    /**
     * 排序算法的實現(xiàn)，對數(shù)組中指定的元素進行排序
     *
     * @param array
     *            待排序的數(shù)組
     * @param from
     *            從哪里開始排序
     * @param end
     *            排到哪里
     * @param c
     *            比較器
     */
    public void insert(Integer[] array, int from, int end) {
 
        /*
         * 第一層循環(huán)：對待插入（排序）的元素進行循環(huán) 從待排序數(shù)組斷的第二個元素開始循環(huán)，到最后一個元素（包括）止
         */
        for (int i = from + 1; i <= end; i++) {
            /**
             * 第二層循環(huán)：對有序數(shù)組進行循環(huán)，且從有序數(shù)組最第一個元素開始向后循環(huán) 找到第一個大于待插入的元素
             * 有序數(shù)組初始元素只有一個，且為源數(shù)組的第一個元素，一個元素數(shù)組總是有序的
             */
            for (int j = 0; j < i; j++) {
                Integer insertedElem = array[i];// 待插入到有序數(shù)組的元素
                // 從有序數(shù)組中最一個元素開始查找第一個大于待插入的元素
                if ((array[j].compareTo(insertedElem)) > 0) {
                    // 找到插入點后，從插入點開始向后所有元素后移一位
                    move(array, j, i - 1);
                    // 將待排序元素插入到有序數(shù)組中
                    array[j] = insertedElem;
                    break;
                }
            }
        }
 
        // =======以下是java.util.Arrays的插入排序算法的實現(xiàn)
        /*
         * 該算法看起來比較簡潔一j點，有點像冒泡算法。 將數(shù)組邏輯上分成前后兩個集合，前面的集合是已經(jīng)排序好序的元素，而后面集合為待排序的
         * 集合，每次內(nèi)層循從后面集合中拿出一個元素，通過冒泡的形式，從前面集合最后一個元素開
         * 始往前比較，如果發(fā)現(xiàn)前面元素大于后面元素，則交換，否則循環(huán)退出
         *
         * 總感覺這種算術有點怪怪，既然是插入排序，應該是先找到插入點，而后再將待排序的元素插
         * 入到的插入點上，那么其他元素就必然向后移，感覺算法與排序名稱不匹，但返過來與上面實
         * 現(xiàn)比，其實是一樣的，只是上面先找插入點，待找到后一次性將大的元素向后移，而該算法卻 是走一步看一步，一步一步將待排序元素往前移
         */
        /*
         * 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);
         * } }
         */
    }
 
    /**
     * 數(shù)組元素后移
     *
     * @param array
     *            待移動的數(shù)組
     * @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 + " ");
        }
    }
}

標簽： swap

版權申明：本站文章部分自網(wǎng)絡，如有侵權，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權歸原作者所有，如需使用，請與原作者聯(lián)系。