摘要：這個版本和上一版對比很有趣，乍看上去多了嵌套了一個循環，可是大多情況卻比第一個快，有人可能會說這個根本不是插入排序，而我卻覺得，只不過上一個是針對于元素本身的數據進行插入，問我這個是針對于位置的插入，就我而言其實這個才更像插入排序。

冒泡排序就是每次量量比較相鄰的元素，進行判斷大小然后進行值的交換，如果把數組中的待比較的元素當做在水中的混亂的元素的話，那么這個排序過程就像是一個個水泡在往上冒出來，這也是冒泡排序的名字來由，不多說，見代碼示例：

public void bubbleSort(Integer[] array) {
        BigDecimal timeStart = new BigDecimal(System.currentTimeMillis());
        BigDecimal spendTime = null;
        System.out.println("-----bubbleSort-----");
        // System.out.println("排序前: " + Arrays.asList(array));
        Integer temp = null;
        boolean exchanged = false;
        for (int i = 1; i < array.length; i++) {
            for (int j = 0; j < array.length - i; j++) {

                if (array[j].intValue() > array[j + 1].intValue()) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    exchanged = true;
                }
            }
            // 如果沒有交換過說明順序是本來就正確的 不需要排序 直接跳出
            if (!exchanged)
                break;
        }
        spendTime = new BigDecimal(System.currentTimeMillis()).subtract(timeStart);
        // System.out.println("排序后: " + Arrays.asList(array));
        System.out.println("排序時間: " + spendTime);
    }

值得注意的是常見的冒泡排序很多人是僅僅追求了自己實現冒泡排序的正確性，而沒有考慮過是否可以優化，本文中，其中利用的exchanged標志就是優化的方案，可以發現這短短幾句代碼對于時間上有了很大的提升，效果見下:

//這里使用JUnit進行測試
    @Test
    public void testSort() {
    //這里利用大一點的Integer對象數組更加可以體現時間的差異性
        Integer[] array = new Integer[50000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(999999);
        }
        bubbleSort(array);
    }

這是沒有設置flag的情況：

這是設置了flag的情況

（此數據在本臺計算機結果是這樣，不同時間也可能不同，與計算機環境有關，但是大多情況是設置這樣一個標志的方式會對性能進行一定的提升）

那么，為什么會出現這樣一個差別呢？
設立標志exchanged的時候，我們可以這樣想：如果當前的兩個發生了交換，說明了之前的是已經交換好了的，因此不需要做多余的判斷與交換。

選擇排序就是假定數組第一個位置為最小的值的位置，然后與剩下的進行一個一個對比，找到最小的元素的位置，然后進行交換，接著假設第二個位置作為最小數據的位置，重復以上步驟。看看實現吧：

    public void selectSort(Integer[] array) {
        BigDecimal timeStart = new BigDecimal(System.currentTimeMillis());
        BigDecimal spendTime = null;
        System.out.println("-----selectSort-----");
        System.out.println("排序前: " + Arrays.asList(array));
        int minIndex;
        Integer temp = null;

        for (int i = 0; i < array.length - 1; i++) {

            minIndex = i;

            for (int j = i + 1; j < array.length; j++) {

                if (array[minIndex].intValue() > array[j].intValue()) {
                    minIndex = j;
                }
            }

//以下的判斷其實不是必須的，但是可以減少對空間的占用，減少交換的操作。
            if (minIndex != i) {
                temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
        spendTime = new BigDecimal(System.currentTimeMillis()).subtract(timeStart);
        System.out.println("排序后: " + Arrays.asList(array));
        System.out.println("排序時間: " + spendTime);

    }

插入排序通過對沒有排序的元素進行適當的插入作為排序思想，大概流程如下：

首先對前連個數據進行比較，小一點的元素入到大一點的數據后邊

接著用以第三個數據與前兩個元素進行比較 插入到合適位置 （注意：這里的比較應該是從當前位置向前比較，而不是從第一個元素進行比較）

然后第四個元素進行同樣的做法進行插入，直到最后一個元素

于是乎......

version 1.0 插入排序：大眾普遍版

public void insertionSort(Integer[] array) {
       BigDecimal timeStart = new BigDecimal(System.currentTimeMillis());
       BigDecimal spendTime = null;
       Integer temp = null;
       int position;
       System.out.println("-----insertionSort-----");
       // System.out.println("排序前: " + Arrays.asList(array));
       for (int i = 1; i < array.length; i++) {

           temp = array[i];
           position = i - 1;

           while (position >= 0 && temp < array[position]) {
               array[position + 1] = array[position];
               position--;
           }
           array[position + 1] = temp;

       }
       spendTime = new BigDecimal(System.currentTimeMillis()).subtract(timeStart);
       // System.out.println("排序后: " + Arrays.asList(array));
       System.out.println("排序時間: " + spendTime);
   }

version 2.0 插入排序：就如該函數名字一樣，ByFindingPosition 這個思路是先找到最合適（即最終需要插入的位置）的位置，記錄下位置，然后根據記錄下的位置進行元素的插入，偏移。2.0這個版本和上一版對比很有趣，乍看上去多了嵌套了一個循環，可是大多情況卻比第一個快，有人可能會說這個根本不是插入排序，而我卻覺得，只不過上一個是針對于元素本身的數據進行插入，問我這個是針對于位置的插入，就我而言 其實這個才更像插入排序。

public void insertionSortByFindingPosition(Integer[] array) {
        BigDecimal timeStart = new BigDecimal(System.currentTimeMillis());
        BigDecimal spendTime = null;
        Integer temp = null;
        int position;
        System.out.println("-----insertionSortByFindingPosition-----");
        System.out.println("排序前: " + Arrays.asList(array));
        for (int i = 1; i < array.length; i++) {

            position = i;

            // 找到position即往前挪的位置
            while (position > 0 && array[i] < array[position - 1]) {
                position--;
            }
            // 找到位置之後需要進行移位 然后把array[i]放在position位置
            temp = array[i];
            for (int j = i; j > position; j--) {
                array[j] = array[j - 1];
            }
            array[position] = temp;

        }
        spendTime = new BigDecimal(System.currentTimeMillis()).subtract(timeStart);
        System.out.println("排序后: " + Arrays.asList(array));
        System.out.println("排序時間: " + spendTime);
    }