摘要：在上面的三種排序中，它們的效率為用大表示法來表示都是，但實(shí)際上按比較的次數(shù)和交換的次數(shù)來考慮，插入排序效率高于選擇排序，選擇排序效率高于冒泡排序。大表示法常見的基于的走勢圖如下圖所示

身在斯洛文尼亞的阿拉里克得到斯提里科被殺的消息后，仰天大笑：“終于沒有人能阻止我去羅馬了。”
當(dāng)他手下的將軍問：“不知大王打算走哪條路去羅馬？”
西哥特王哈哈大笑，說出了那句千古名言：All roads lead to Rome

條條大路通羅馬，這句著名的英語諺語告訴人們，達(dá)到同一目的可以有多種不同的方法和途徑。
在編程中同樣如此，同樣一個(gè)編程問題，十個(gè)程序員可能會(huì)寫出十種程序，算法各不相同，確實(shí)是條條大路通羅馬。
但程序員對(duì)算法的效率可不會(huì)像西哥特王那般豪放和豁達(dá)，程序員對(duì)于算法的效率十分在乎，盡管算法無論效率高低，均能解決問題，但效率高的算法，除了能解決問題，還可以在問題規(guī)模變大變復(fù)雜時(shí)，高效地解決問題。

于是，我們面臨一個(gè)問題，那就是如何評(píng)價(jià)，以及從什么角度去評(píng)價(jià)一個(gè)算法。

通常，我們可能說，這個(gè)算法比那個(gè)算法更快一點(diǎn)，但這個(gè)比較是沒有意義的。當(dāng)算法要處理的數(shù)據(jù)項(xiàng)數(shù)量不同時(shí)，誰快誰慢都要重新評(píng)價(jià)。

評(píng)價(jià)算法時(shí)，應(yīng)該結(jié)合數(shù)據(jù)量來評(píng)價(jià)，即當(dāng)數(shù)據(jù)量增大時(shí)，算法所消耗的時(shí)間變化趨勢。

在計(jì)算機(jī)世界中，這種粗略的評(píng)價(jià)方式被稱為大O表示法

冒泡排序先從數(shù)組最左邊開始，比較第1個(gè)和第2個(gè)元素的值，值比較高的往數(shù)組的高位排，然后依次比較第2和第3個(gè)元素，值比較大的往高位排，一直比較到倒數(shù)第2個(gè)和倒數(shù)第1個(gè)元素，這稱為第一趟排序，這一趟就能確定數(shù)組中值最大的那個(gè)元素，并把這個(gè)最大的元素排到數(shù)組的最高位。
依次類推，第二趟排序會(huì)確定數(shù)組中第二大的元素，并把它排在最大的元素前邊。
假設(shè)數(shù)組有n個(gè)元素，那么經(jīng)過n-1趟排序，數(shù)組的元素就是有序的。
因?yàn)槊恳惶酥?，最大的元素就像水泡一樣，冒到了?shù)組的高位，冒泡排序因此得名。

/**
 *
 *
 * @author beanlam
 * @date 2016年3月9日 下午11:26:20
 * @version 1.0
 *
 */
public class SimpleSort {

    public static void bubbleSort(final int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("array");
        }
        
        int length = array.length;
        for (int outLoop = length - 1; outLoop > 0; outLoop-- ) {
            for (int innerLoop = 0; innerLoop < outLoop; innerLoop++) {
                if (array[innerLoop] > array[innerLoop + 1]) {
                    swap(array, innerLoop, innerLoop + 1);
                }
            }
        }
    }
    
    private static void swap(final int[] array, final int left, final int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}

選擇排序的過程是從左向右掃描數(shù)組，并從中找出最小值的元素，把它放在左邊已知的最小位置上，比如第一趟掃描，找出最小的元素后，將該元素放到數(shù)組的下標(biāo)0處。第二趟掃描從下標(biāo)1開始掃描，找出最小元素后，放到下標(biāo)1處?？偣残枰獟呙鑞-1次，就能使該數(shù)組處于有序狀態(tài)。

/**
 *
 *
 * @author beanlam
 * @date 2016年3月9日 下午11:26:20
 * @version 1.0
 *
 */
public class SimpleSort {

    public static void selectionSort(final int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("array");
        }
        
        int length = array.length;
        int minIndex;
        for (int outLoop = 0; outLoop < length - 1; outLoop++) {
            minIndex = outLoop;
            for (int innerLoop = outLoop + 1;innerLoop < length; innerLoop++) {
                if (array[innerLoop] < array[minIndex]) {
                    minIndex = innerLoop;
                }
            }
            swap(array, outLoop, minIndex);
        }
    }
    
    private static void swap(final int[] array, final int left, final int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}

插入排序的精髓在于先令局部有序，先令左邊一部分?jǐn)?shù)據(jù)有序，然后這部分有序的元素的下一位再與這些有序的元素比較，尋找合適自己站立的位置，插隊(duì)排進(jìn)去，插隊(duì)也意味著右邊的有序元素要挪動(dòng)身子。
一下提供基于for循環(huán)和while循環(huán)的兩種插入排序?qū)崿F(xiàn)方式：

/**
 *
 *
 * @author beanlam
 * @date 2016年3月9日 下午11:26:20
 * @version 1.0
 *
 */
public class SimpleSort {
    public static void insertionSort(final int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("array");
        }
        
        int length = array.length;
        for (int outLoop = 1; outLoop < length; outLoop++) {
            int temp = array[outLoop];
            for (int innerLoop = outLoop - 1; innerLoop >= 0; innerLoop--) {
                if (array[innerLoop] > temp) {
                    array[innerLoop + 1] = array[innerLoop];
                    if (innerLoop == 0) {
                        array[innerLoop] = temp;
                    }
                } else {
                    array[innerLoop + 1] = temp;
                    break;
                }
            }
        }
    }
    
    public static void insertionSort1(final int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("array");
        }
        
        int length = array.length;
        int temp;
        int innerLoop;
        for (int outLoop = 1; outLoop < length; outLoop++) {
            temp = array[outLoop];
            innerLoop = outLoop;
            while (innerLoop > 0 && array[innerLoop - 1] >= temp) {
                array[innerLoop] = array[innerLoop-1];
                --innerLoop;
            }
            array[innerLoop] = temp;
        }
    }
     
    private static void swap(final int[] array, final int left, final int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}

假設(shè)需要比較的數(shù)組中有N個(gè)元素，
冒泡排序中，需要掃描N-1趟，每掃描一趟就要多次對(duì)兩個(gè)元素做比較，并且在必要時(shí)需要對(duì)兩個(gè)元素做位置的交換，由于數(shù)據(jù)是隨機(jī)的，所以平均下來，一趟中大概有一半被掃描的數(shù)據(jù)需要作位置的交換。
第1趟需要N-1次比較，第2趟需要N-2次比較，以此類推，總共需要N(N-1)/2趟比較，而元素的交換次數(shù)平均下來需要做NN/4次。

選擇排序和冒泡排序進(jìn)行了相同次數(shù)的比較N*(N-1)/2，但每一趟只有一次交換，甚至沒有任何交換。因此，選擇排序比冒泡排序更有效率，因?yàn)樗鼫p少了很多交換。

插入排序卻又要比選擇排序更有效率一點(diǎn)，因?yàn)榈?趟排序中，它最多比較1次，第2趟排序中，最多比較2次， 依次類推，最后一趟，最多比較N-1次，
平均只有全體數(shù)據(jù)的一半被比較，因此比較的次數(shù)為N*(N-1)/4，與冒泡和選擇排序不同的是，插入排序不需要交換數(shù)據(jù)，只是把一個(gè)值賦給數(shù)組的某一個(gè)下標(biāo)，賦值的速度比交換數(shù)據(jù)的速度要快很多，因此插入排序比選擇排序和冒泡排序更有效率。

大O表示法只是一個(gè)粗略的估算值，它關(guān)注與隨著數(shù)據(jù)量N的增大，算法速度的變化。

對(duì)于數(shù)組某個(gè)下標(biāo)的賦值，算法消耗的時(shí)間是個(gè)常數(shù)K
對(duì)于線性的查找，算法的消耗時(shí)間與N成正比。
對(duì)于二分查找，算法消耗時(shí)間與log(N)成正比。

大O表示法通常會(huì)忽略常數(shù)，因?yàn)樗P(guān)注的是算法的消耗時(shí)間隨著N的變化而怎么變化。常數(shù)通常與處理器芯片或者編譯器有關(guān)。

在上面的三種排序中，它們的效率為用大O表示法來表示都是O(N^2)，但實(shí)際上按比較的次數(shù)和交換的次數(shù)來考慮，插入排序效率高于選擇排序，選擇排序效率高于冒泡排序。

大O表示法常見的基于N的走勢圖如下圖所示：