轉(zhuǎn)自：https://zhuanlan.zhihu.com/p/80043870

1、冒泡排序（Bubble Sort）

冒泡排序：對每一對相鄰的元素比較大小，若順序錯誤則交換順序（正確的順序由排序方向決定，我們假定數(shù)組元素應(yīng)該從小到大排序）；這樣從頭到尾操作一遍，最大的元素將會在最后一個（操作的一組元素的最后一個）；對前面未確認順序的重復(fù)以上操作，直到?jīng)]有元素可操作即排序完成。

1.1 算法描述：

（1）對一組元素，將相鄰兩個元素比較大小，如果順序錯誤則交換順序；
（2）對每一對相鄰元素作同樣的操作，從每一組開頭一對到最后一對元素，這樣每一組元素最后一個元素會是最大；
（3）循環(huán)n次（n為數(shù)組長度），每次選擇前n - 1 - i個（i為第幾次循環(huán)）元素重復(fù)（1）、（2）步驟；

1.2 代碼實現(xiàn)：

    public static int[] bubbleSort(int[] arr){
        int len = arr.length;
        if (len == 0) return arr;
        for (int i = 0; i < len; i++){
            for (int j = 0; j < len - 1 - i; j++){
                if (arr[j+1] < arr[j]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

2、選擇排序（Selection Sort）

選擇排序：是一種簡單直接的排序算法，它的工作原理是：遍歷未排序元素，將最小值（或者最大值）和遍歷的第一個元素交換位置；然后繼續(xù)在剩余未排序的元素中重復(fù)以上操作，直到將所有元素排序完成。

2.1 算法描述：
（1）初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空；
（2）第i趟排序(i=1,2,3…n-1)開始時，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)；
（3）n-1趟結(jié)束，數(shù)組有序化了。

2.2 代碼實現(xiàn)：

    public static int[] selectorSort(int[] arr){
        int len = arr.length;
        if (len == 0) return arr;
        for (int i = 0; i < len-1; i++){
            int minIndex = i;
            //遍歷出每趟的最小值
            for (int j = i+1; j < len; j++){
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            //把最小值與每趟第一個元素交換位置
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }

3、插入排序（Insertion Sort）

插入排序：一種簡單直觀的排序算法。它的工作原理是：通過構(gòu)建有序序列，依次取未排序序列元素，在有序序列后面從后往前掃描，找到相應(yīng)位置插入，插入位置后面的元素需要依次外后移動，為新元素提供位置。

3.1 算法描述
（1）從第一個元素開始，可以認為是已經(jīng)排好序了
（2）取出下一個新元素，依次從后往前掃描；
（3）如果掃描到的元素比新元素大，則將掃描到的元素依次往后移動一個位置；
（4）重復(fù)步驟（3）直到掃描到的元素小于等于新元素，則將新元素插入該位置之后；
（5）重復(fù)步驟（2）~（4），直到最后一個元素被插入正確的位置。

3.2 代碼實現(xiàn)

    public static int[] insertionSort(int[] arr){
        int len = arr.length;
        if (len == 0) return arr;
        for (int i = 0;i < len -1; i++){
            int curr = arr[i+1];  //這是要插入的新元素
            int preIndex = i;
            //從后往前掃描有序序列，如果新元素小于等于掃描到的元素，則將被掃描的元素依次后移一個位置，注意不要下標不要越界
            while (preIndex >= 0 && arr[preIndex] > curr){
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            //上面的while循環(huán)跳出則表示當(dāng)前preIndex的元素比新元素小或者已經(jīng)越界，應(yīng)該把新元素插入preIndex+1位置
            arr[preIndex+1] = curr;
        }
        return arr;
    }

4、希爾排序（Shell Sort）

希爾排序：是插入排序的改良版本，又叫縮小增量排序。希爾排序是把記錄按下表的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。

4.1 算法描述：
在此我們選擇增量為gap = length / 2，繼續(xù)縮小增量gap = gap / 2直到 gap == 1，我們用一個序列來表示這些增量{len/2, (len/2)/2, ....,1} 這種增量序列的選擇和證明是一種數(shù)學(xué)難題，在此選擇的增量是比較常見的，也是希爾建議的稱之為希爾增量。

先將整個待排序的序列分割為若干個子序列分別進行插入排序，具體如下
（1）選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
（2）按增量序列個數(shù)k，對序列進行k 趟排序；
（3）每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

4.2 代碼實現(xiàn)：

    public static int[] shellSort(int[] arr){
        int len = arr.length;
        if (len == 0) return arr;
        int gap = len / 2;  //增量初始值
        while (gap > 0){
            for (int i = gap; i < len; i++){
                //對每個分組進行插入排序
                int curr = arr[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && arr[preIndex] > curr){
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                arr[preIndex + gap] = curr;
            }
            gap = gap / 2;  //縮小增量，重新分組進行插入排序
        }
        //gap==1時，將所有序列分為一組進行插入排序
        return arr;
    }

5、歸并排序（Merge Sort）

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。

5.1 算法描述：
（1）把長度為n的輸入序列分成兩個長度為n/2的子序列；
（2）對這兩個子序列分別采用歸并排序；
（3）將兩個排序好的子序列合并成一個最終的排序序列。

5.2 代碼實現(xiàn)：

    public static int[] mergeSort(int[] arr){
        if (arr.length < 2) return arr;
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0 , mid);
        int[] right = Arrays.copyOfRange(arr, mid , arr.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    /**
     * 將兩個有序序列 組合成一個新的有序序列
     */
    private static int[] merge(int[] left, int[] right){
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++){

            if (i < left.length && j < right.length){
                if (left[i] <= right[j]) {
                    result[index] = left[i++];
                } else if (left[i] > right[j]) {
                    result[index] = right[j++];
                }
            } else {
                if (i >= left.length) result[index] = right[j++];
                else if (j >= right.length) result[index] = left[i++];
            }

        }
        return result;
    }

未完待續(xù)。。。