冒泡排序

    /**
     * 冒泡排序
     * 需要N*（N-1）/2約等于N*N/2次比較，因為滿足條件才交換所以交換的次數(shù)少于比較的次數(shù)
     * 如果數(shù)據(jù)是隨機的那么大概一半數(shù)據(jù)需要交換，則交換次數(shù)為N*N/4。
     * 交換和比較操作次數(shù)都和N*N成正比。常數(shù)不算在大O表示法中可以忽悠2和4，
     * 所以冒泡排序運行需要O（N*N）時間級別。
     * 不變性：out右邊的數(shù)據(jù)總是有序的
     * 個人理解：N*N/2次比較+交換次數(shù)為N*N/4
     * @param arr
     */
    public void bubbleSort(int[] arr) {
        int length = arr.length;
        for(int out = length-1; out > 0; out--) {
            //下標(biāo)大于out的數(shù)據(jù)是已經(jīng)排好序了的所以沒有必要比較交換
            for(int in = 0; in < out; in++) {
                //比較
                if(arr[in] > arr[in+1]) {
                    //如果滿足左邊大于右邊則交換
                    int temp = arr[in];
                    arr[in] = arr[in+1];
                    arr[in+1] = temp;
                }
            }
        }
    }

選擇排序

    /**
     * 選擇排序
     * 選擇排序和冒泡排序執(zhí)行了相同次數(shù)的比較：N*(N-1)/2。
     * N值很大時，比較次數(shù)是主要的，所以結(jié)論是選擇排序和冒泡排序一樣運行了O(N*N)時間。
     * 但是選擇排序無疑更快，因為他進行交換次數(shù)少的多（O(N)）。
     * 當(dāng)N值較小時，特別是如果交換時間級比比較時間級大得多時，選擇排序?qū)嶋H上是相當(dāng)快的。
     * 不變性：out左邊的數(shù)據(jù)總是有序的
     * 個人理解：其實是N*(N-1)/2次比較+（O(N)）次交換+N*(N-1)/4復(fù)制
     * @param arr
     */
    public void selectionSort(int[] arr) {
        for(int out = 0; out < arr.length - 1; out++) {
            //尋找最小值的下標(biāo)
            int min = out;
            for(int in = out + 1; in < arr.length; in++) {
                if(arr[in] < arr[min]) {
                   //其實按照個人理解這個需要N*(N-1)/4復(fù)制
                    min = in;
                }
            }
            //把最小放在最左邊
            int temp = arr[min];
            arr[min] = arr[out];
            arr[out] = temp;
        }
    }

插入排序

    /**
     * 插入排序
     * 不變性：在每趟結(jié)束結(jié)束時，在講temp位置的項插入后，比out變量下標(biāo)小的數(shù)據(jù)項都是局部有序的。
     * 效率：在第一趟排序中最多比較一次，第二趟最多比較兩次，以此類推最后一躺最多比較N-1次。
     * 因此1+2+3+...+N-1 = N*(N-1)/2，然而因為在每一趟排序發(fā)現(xiàn)插入點之前，平均只有全體數(shù)據(jù)項的一半
     * 真的進行了比較，我們除以2得到N*(N-1)/4.
     * 復(fù)制次數(shù)大致等于比較次數(shù)。然后一次復(fù)制與一次交換的時間耗費不同，所以相對于隨機數(shù)據(jù)，這個算法比冒泡排序快一倍，
     * 比選擇排序略快。于其他簡單排序一樣對于隨機順序的數(shù)據(jù)進行插入排序也需要O(N*N)的時間級。
     * 對于已經(jīng)有序或基本有序的數(shù)據(jù)來說，插入排序要好得多。
     * 個人理解：N*(N-1)/4比較+N*(N-1)/4次復(fù)制+N次復(fù)制
     * @param arr
     */
    public void insertionSort(int[] arr) {
        for(int out = 1; out < arr.length; out++) {
            int temp = arr[out];
            int in = out;
            while (in > 0 && arr[in-1] >= temp) {
                 //個人理解這兒是N*(N-1)/4次復(fù)制
                arr[in] = arr[in-1];
                --in;
            }
             //個人理解這兒是N次復(fù)制
            arr[in] = temp;

        }
    }

排序算法的選擇

除非手邊沒有算法書可參考，一般情況幾乎不太用冒泡排序。選擇排序雖然把交換次數(shù)降到最低，但比較次數(shù)依然很大。當(dāng)數(shù)據(jù)量很小，并且交換數(shù)據(jù)相對于比較數(shù)據(jù)更加耗時的情況下可以用選擇排序。在大多數(shù)的情況下假設(shè)數(shù)據(jù)量比較小，或者基本有序時，插入排序是三種簡單排序中最好的選擇。對于更大數(shù)據(jù)量的排序來說，快速排序通常是更快的方法。
除了在速度方面比較排序算法外，還有一個衡量標(biāo)準(zhǔn)就是算法需要的內(nèi)存空間多大。這三種算法都除了數(shù)組外幾乎不需要其他的內(nèi)存空間。所有排序算法都需要一個額外的變量來暫時存儲變換時的數(shù)據(jù)項。