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

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

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);
    }

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

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

這是沒有設(shè)置flag的情況：

這是設(shè)置了flag的情況

（此數(shù)據(jù)在本臺計算機(jī)結(jié)果是這樣，不同時間也可能不同，與計算機(jī)環(huán)境有關(guān)，但是大多情況是設(shè)置這樣一個標(biāo)志的方式會對性能進(jìn)行一定的提升）

那么，為什么會出現(xiàn)這樣一個差別呢？
設(shè)立標(biāo)志exchanged的時候，我們可以這樣想：如果當(dāng)前的兩個發(fā)生了交換，說明了之前的是已經(jīng)交換好了的，因此不需要做多余的判斷與交換。

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

    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);

    }

插入排序通過對沒有排序的元素進(jìn)行適當(dāng)?shù)牟迦胱鳛榕判蛩枷耄蟾帕鞒倘缦拢?/p>

首先對前連個數(shù)據(jù)進(jìn)行比較，小一點的元素入到大一點的數(shù)據(jù)后邊

接著用以第三個數(shù)據(jù)與前兩個元素進(jìn)行比較 插入到合適位置 （注意：這里的比較應(yīng)該是從當(dāng)前位置向前比較，而不是從第一個元素進(jìn)行比較）

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

于是乎......

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

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--;
            }
            // 找到位置之後需要進(jìn)行移位 然后把a(bǔ)rray[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);
    }