常用排序算法以及怎么用Java實(shí)現(xiàn)

本篇內(nèi)容主要講解“常用排序算法以及怎么用Java實(shí)現(xiàn)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“常用排序算法以及怎么用Java實(shí)現(xiàn)”吧!

一.直接插入排序

概述

插入排序是往有序的數(shù)組中快速插入一個(gè)新的元素。把要排序的數(shù)組分為了兩個(gè)部分, 一部分是數(shù)組的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先將第一部分排序完成, 然后再插入這個(gè)元素. 其中第一部分的排序也是通過(guò)再次拆分為兩部分來(lái)進(jìn)行的。（注：插入排序由于操作不盡相同, 可分為 直接插入排序 , 折半插入排序(又稱二分插入排序), 鏈表插入排序…）

實(shí)現(xiàn)方式

①. 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序
②. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
③. 如果該元素（已排序）大于新元素，將該元素移到下一位置
④. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
⑤. 將新元素插入到該位置后
⑥. 重復(fù)步驟②~⑤
如圖（1-1）所示：

（圖：1-1）

java代碼實(shí)現(xiàn)

  /**
     * 插入排序
     *
     * 1. 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序
     * 2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
     * 3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
     * 4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
     * 5. 將新元素插入到該位置后
     * 6. 重復(fù)步驟2~5
     * @param arr  待排序數(shù)組
     */
    public static void insertionSort(int[] arr){
        for( int i=0; i<arr.length-1; i++ ) {
            for( int j=i+1; j>0; j-- ) {
                if( arr[j-1] <= arr[j] )
                    break;
                int temp = arr[j];      //交換操作
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                System.out.println("Sorting:  " + Arrays.toString(arr));
            }
        }
    }

注意：
如果 比較操作 的代價(jià)比 交換操作 大的話，可以采用二分查找法來(lái)減少 比較操作 的數(shù)目。該算法可以認(rèn)為是 插入排序 的一個(gè)變種，稱為二分查找插入排序。
復(fù)雜分析如下：

總結(jié)：

1. 由于直接插入排序每次只移動(dòng)一個(gè)元素的位， 并不會(huì)改變值相同的元素之間的排序， 因此它是一種穩(wěn)定排序。

2. 插入排序所需的時(shí)間取決于輸入元素的初始順序，這樣數(shù)組有序或接近有序，更適合插入排序。

二. 希爾排序

概述

希爾排序，也稱 遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。希爾排序是 非穩(wěn)定排序算。
操作如下：
將待排序數(shù)組按照步長(zhǎng)gap進(jìn)行分組，然后將每組的元素利用直接插入排序的方法進(jìn)行排序；每次再將gap折半減小，循環(huán)上述操作；當(dāng)gap=1時(shí)，利用直接插入，完成排序。

實(shí)現(xiàn)方式

1. 選擇一個(gè)增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
2. 按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；
3. 每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

如圖（2-1）所示：

圖（2-1）

java代碼實(shí)現(xiàn)

/**
 * 希爾排序（Wiki官方版）
 *
 * 1. 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；（注意此算法的gap取值）
 * 2. 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；
 * 3. 每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。
 *    僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
 * @param arr  待排序數(shù)組
 */
public static void shell_sort(int[] arr) {
    int gap = 1, i, j, len = arr.length;
    int temp;
    while (gap < len / 3)
        gap = gap * 3 + 1;      // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
    for (; gap > 0; gap /= 3) {
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
                arr[j + gap] = temp;
        }
    }
}

復(fù)雜分析如下：

總結(jié)：

1. 選擇合理的步長(zhǎng)很重要，更好的步長(zhǎng)序列取值可以參考維基百科。

2. 排序更高效的原因是它權(quán)衡了子數(shù)組的規(guī)模和有序性。排序之初，各個(gè)子數(shù)組都很短，排序之后子數(shù)組都是部分有序的，這兩種情況都很適合插入排序。
   希爾排序與插入排序?qū)θ缦拢?/strong>

1. 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率；但插入排序一般來(lái)說(shuō)是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)。

2. 希爾排序是先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

三. 選擇排序

概述

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì) n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多 n-1 次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。

實(shí)現(xiàn)方式

1. 從未排序序列中，找到關(guān)鍵字最小的元素
2. 如果最小元素不是未排序序列的第一個(gè)元素，將其和未排序序列第一個(gè)元素互換
3. 重復(fù)1、2步，直到排序結(jié)束。

如圖（3-1）所示：

圖（3-1）

java代碼實(shí)現(xiàn)

/**
 * 選擇排序
 *
 * 1. 從待排序序列中，找到關(guān)鍵字最小的元素；
 * 2. 如果最小元素不是待排序序列的第一個(gè)元素，將其和第一個(gè)元素互換；
 * 3. 從余下的 N - 1 個(gè)元素中，找出關(guān)鍵字最小的元素，重復(fù)①、②步，直到排序結(jié)束。
 *    僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
 * @param arr  待排序數(shù)組
 */
public static void selectionSort(int[] arr){
    for(int i = 0; i < arr.length-1; i++){
        int min = i;
        for(int j = i+1; j < arr.length; j++){    //選出之后待排序中值最小的位置
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        if(min != i){
            int temp = arr[min];      //交換操作
            arr[min] = arr[i];
            arr[i] = temp;
            System.out.println("Sorting:  " + Arrays.toString(arr));
        }
    }
}

復(fù)雜分析如下：

總結(jié)：
選擇排序的簡(jiǎn)單和直觀名副其實(shí)，這也造就了它”出了名的慢性子”，無(wú)論是哪種情況，哪怕原數(shù)組已排序完成，它也將花費(fèi)將近n2/2次遍歷來(lái)確認(rèn)一遍。即便是這樣，它的排序結(jié)果也還是不穩(wěn)定的。 唯一值得高興的是，它并不耗費(fèi)額外的內(nèi)存空間。

四. 堆排序

概述

堆：n個(gè)元素的序列{k1,k2,···,kn}，當(dāng)且僅當(dāng)滿足下關(guān)系時(shí)，稱之為堆。ki <= k(2i) 且 ki <= k(2i+1)或： ki >= k(2i) 且 ki >= k(2i+1)
把此序列對(duì)應(yīng)的二維數(shù)組看成一個(gè)完全二叉樹(shù)。那么堆的含義就是：完全二叉樹(shù)中任何一個(gè)非葉子節(jié)點(diǎn)的值均不大于（或不小于）其左，右孩子節(jié)點(diǎn)的值。由上述性質(zhì)可知大頂堆的堆頂?shù)年P(guān)鍵字肯定是所有關(guān)鍵字中最大的，小頂堆的堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最小的。因此我們可使用大頂堆進(jìn)行升序排序, 使用小頂堆進(jìn)行降序排序。

實(shí)現(xiàn)方式

1. 先將初始序列K[1…n]建成一個(gè)大頂堆, 那么此時(shí)第一個(gè)元素K1最大, 此堆為初始的無(wú)序區(qū).

2. 再將關(guān)鍵字最大的記錄K1 (即堆頂, 第一個(gè)元素)和無(wú)序區(qū)的最后一個(gè)記錄 Kn 交換, 由此得到新的無(wú)序區(qū)K[1…n-1]和有序區(qū)K[n], 且滿足K[1…n-1].keys <= K[n].key

3. 交換K1 和 Kn 后, 堆頂可能違反堆性質(zhì), 因此需將K[1…n-1]調(diào)整為堆. 然后重復(fù)步驟②, 直到無(wú)序區(qū)只有一個(gè)元素時(shí)停止.
   如圖（4-1）所示：

圖（4-1）

java代碼實(shí)現(xiàn)

從算法描述來(lái)看，堆排序需要兩個(gè)過(guò)程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成。一是建堆函數(shù)，二是反復(fù)調(diào)用建堆函數(shù)以選擇出剩余未排元素中最大的數(shù)來(lái)實(shí)現(xiàn)排序的函數(shù)。

總結(jié)起來(lái)就是定義了以下幾種操作：

1. 最大堆調(diào)整（Max_Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)

2. 創(chuàng)建最大堆（Build_Max_Heap）：將堆所有數(shù)據(jù)重新排序

3. 堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算

對(duì)于堆節(jié)點(diǎn)的訪問(wèn)：

父節(jié)點(diǎn)i的左子節(jié)點(diǎn)在位置：(2*i+1);
父節(jié)點(diǎn)i的右子節(jié)點(diǎn)在位置：(2*i+2);
子節(jié)點(diǎn)i的父節(jié)點(diǎn)在位置：floor((i-1)/2);

/**
 * 堆排序
 *
 * 1. 先將初始序列K[1..n]建成一個(gè)大頂堆, 那么此時(shí)第一個(gè)元素K1最大, 此堆為初始的無(wú)序區(qū).
 * 2. 再將關(guān)鍵字最大的記錄K1 (即堆頂, 第一個(gè)元素)和無(wú)序區(qū)的最后一個(gè)記錄 Kn 交換, 由此得到新的無(wú)序區(qū)K[1..n?1]和有序區(qū)K[n], 且滿足K[1..n?1].keys?K[n].key
 * 3. 交換K1 和 Kn 后, 堆頂可能違反堆性質(zhì), 因此需將K[1..n?1]調(diào)整為堆. 然后重復(fù)步驟②, 直到無(wú)序區(qū)只有一個(gè)元素時(shí)停止.
 * @param arr  待排序數(shù)組
 */
public static void heapSort(int[] arr){
    for(int i = arr.length; i > 0; i--){
        max_heapify(arr, i);

        int temp = arr[0];      //堆頂元素(第一個(gè)元素)與Kn交換
        arr[0] = arr[i-1];
        arr[i-1] = temp;
    }
}

private static void max_heapify(int[] arr, int limit){
    if(arr.length <= 0 || arr.length < limit) return;
    int parentIdx = limit / 2;

    for(; parentIdx >= 0; parentIdx--){
        if(parentIdx * 2 >= limit){
            continue;
        }
        int left = parentIdx * 2;       //左子節(jié)點(diǎn)位置
        int right = (left + 1) >= limit ? left : (left + 1);    //右子節(jié)點(diǎn)位置，如果沒(méi)有右節(jié)點(diǎn)，默認(rèn)為左節(jié)點(diǎn)位置

        int maxChildId = arr[left] >= arr[right] ? left : right;
        if(arr[maxChildId] > arr[parentIdx]){   //交換父節(jié)點(diǎn)與左右子節(jié)點(diǎn)中的最大值
            int temp = arr[parentIdx];
            arr[parentIdx] = arr[maxChildId];
            arr[maxChildId] = temp;
        }
    }
    System.out.println("Max_Heapify: " + Arrays.toString(arr));
}

復(fù)雜分析如下：

總結(jié)：

1. 建立堆的過(guò)程, 從length/2 一直處理到0, 時(shí)間復(fù)雜度為O(n);
2. 調(diào)整堆的過(guò)程是沿著堆的父子節(jié)點(diǎn)進(jìn)行調(diào)整, 執(zhí)行次數(shù)為堆的深度, 時(shí)間復(fù)雜度為O(lgn);
3. 堆排序的過(guò)程由n次第2步完成, 時(shí)間復(fù)雜度為O(nlgn).

總結(jié)：由于堆排序中初始化堆的過(guò)程比較次數(shù)較多, 因此它不太適用于小序列。 同時(shí)由于多次任意下標(biāo)相互交換位置, 相同元素之間原本相對(duì)的順序被破壞了, 因此, 它是不穩(wěn)定的排序。

五. 冒泡排序

概述

冒泡排序（Bubble Sort）是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

實(shí)現(xiàn)方式

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的1-3步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

如圖（5-1） 所示：

圖（5-1）

Java實(shí)現(xiàn)方式

/**
 * 冒泡排序
 *
 * 1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
 * 2. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
 * 3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
 * 4. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的1-3步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
 * @param arr  待排序數(shù)組
 */
public static void bubbleSort(int[] arr){
    for (int i = arr.length - 1; i > 0; i--) {      //外層循環(huán)移動(dòng)游標(biāo)
        for(int j = 0; j < i; j++){    //內(nèi)層循環(huán)遍歷游標(biāo)及之后(或之前)的元素
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                System.out.println("Sorting: " + Arrays.toString(arr));
            }
        }
    }
}

復(fù)雜分析如下：

總結(jié)：

1. 冒泡排序是最容易實(shí)現(xiàn)的排序，最壞的情況是每次都需要交換， 共需遍歷并交換將近n2/2次， 時(shí)間復(fù)雜度為O(n2)， 最佳的情況是內(nèi)循環(huán)遍歷一次后發(fā)現(xiàn)排序是對(duì)的，因此退出循環(huán)， 時(shí)間復(fù)雜度為O(n)。 平均來(lái)講， 時(shí)間復(fù)雜度為O(n2) 由于冒泡排序中只有緩存的temp變量需要內(nèi)存空間， 因此空間復(fù)雜度為常量O(1)。

2. 由于冒泡排序只在相鄰元素大小不符合要求時(shí)才調(diào)換他們的位置, 它并不改變相同元素之間的相對(duì)順序, 因此它是穩(wěn)定的排序算法。

六. 快速排序

概述

快速排序是在平均狀況下，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)。

實(shí)現(xiàn)方式

快速排序使用分治策略來(lái)把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。步驟為：

1. 從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot）。

2. 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。

3. 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。遞歸到最底部時(shí)，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

如圖（6-1）所示：

圖（6-1）

java 代碼實(shí)現(xiàn)

/**
 * 快速排序（遞歸）
 *
 * ①. 從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot）。
 * ②. 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
 * ③. 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
 * @param arr   待排序數(shù)組
 * @param low   左邊界
 * @param high  右邊界
 */
public static void quickSort(int[] arr, int low, int high){
    if(arr.length <= 0) return;
    if(low >= high) return;
    int left = low;
    int right = high;

    int temp = arr[left];   //挖坑1：保存基準(zhǔn)的值
    while (left < right){
        while(left < right && arr[right] >= temp){  //坑2：從后向前找到比基準(zhǔn)小的元素，插入到基準(zhǔn)位置坑1中
            right--;
        }
        arr[left] = arr[right];
        while(left < right && arr[left] <= temp){   //坑3：從前往后找到比基準(zhǔn)大的元素，放到剛才挖的坑2中
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = temp;   //基準(zhǔn)值填補(bǔ)到坑3中，準(zhǔn)備分治遞歸快排
    System.out.println("Sorting: " + Arrays.toString(arr));
    quickSort(arr, low, left-1);
    quickSort(arr, left+1, high);
}

上面是遞歸版的快速排序：通過(guò)把基準(zhǔn)temp插入到合適的位置來(lái)實(shí)現(xiàn)分治，并遞歸地對(duì)分治后的兩個(gè)劃分繼續(xù)快排。那么非遞歸版的快排如何實(shí)現(xiàn)呢？

因?yàn)檫f歸的本質(zhì)是棧，所以我們非遞歸實(shí)現(xiàn)的過(guò)程中，可以借助棧來(lái)保存中間變量就可以實(shí)現(xiàn)非遞歸了。在這里中間變量也就是通過(guò)Pritation函數(shù)劃分區(qū)間之后分成左右兩部分的首尾指針，只需要保存這兩部分的首尾指針即可。

/**
 * 快速排序（非遞歸）
 *
 * ①. 從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot）。
 * ②. 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
 * ③. 把分區(qū)之后兩個(gè)區(qū)間的邊界（low和high）壓入棧保存，并循環(huán)①、②步驟
 * @param arr   待排序數(shù)組
 */
public static void quickSortByStack(int[] arr){
    if(arr.length <= 0) return;
    Stack<Integer> stack = new Stack<Integer>();

    //初始狀態(tài)的左右指針入棧
    stack.push(0);
    stack.push(arr.length - 1);
    while(!stack.isEmpty()){
        int high = stack.pop();     //出棧進(jìn)行劃分
        int low = stack.pop();

        int pivotIdx = partition(arr, low, high);

        //保存中間變量
        if(pivotIdx > low) {
            stack.push(low);
            stack.push(pivotIdx - 1);
        }
        if(pivotIdx < high && pivotIdx >= 0){
            stack.push(pivotIdx + 1);
            stack.push(high);
        }
    }
}

private static int partition(int[] arr, int low, int high){
    if(arr.length <= 0) return -1;
    if(low >= high) return -1;
    int l = low;
    int r = high;

    int pivot = arr[l];    //挖坑1：保存基準(zhǔn)的值
    while(l < r){
        while(l < r && arr[r] >= pivot){  //坑2：從后向前找到比基準(zhǔn)小的元素，插入到基準(zhǔn)位置坑1中
            r--;
        }
        arr[l] = arr[r];
        while(l < r && arr[l] <= pivot){   //坑3：從前往后找到比基準(zhǔn)大的元素，放到剛才挖的坑2中
            l++;
        }
        arr[r] = arr[l];
    }
    arr[l] = pivot;   //基準(zhǔn)值填補(bǔ)到坑3中，準(zhǔn)備分治遞歸快排
    return l;
}

復(fù)雜分析如下：

總結(jié)：

1. 快速排序是通常被認(rèn)為在同數(shù)量級(jí)（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時(shí)，快排序反而蛻化為冒泡排序。為改進(jìn)之，通常以“三者取中法”來(lái)選取基準(zhǔn)記錄，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄。快速排序是一個(gè)不穩(wěn)定的排序方法。

2. 快速排序排序效率非常高。 雖然它運(yùn)行最糟糕時(shí)將達(dá)到O(n2)的時(shí)間復(fù)雜度, 但通常平均來(lái)看, 它的時(shí)間復(fù)雜為O(nlogn), 比同樣為O(nlogn)時(shí)間復(fù)雜度的歸并排序還要快. 快速排序似乎更偏愛(ài)亂序的數(shù)列, 越是亂序的數(shù)列, 它相比其他排序而言, 相對(duì)效率更高.

七. 歸并排序

概述

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，且各層分治遞歸可以同時(shí)進(jìn)行。

實(shí)現(xiàn)方式

歸并排序算法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。

注：歸并排序可通過(guò)兩種方式實(shí)現(xiàn)（自上而下的遞歸，自下而上的迭代）
遞歸法（假設(shè)序列共有n個(gè)元素）：

1. 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成 floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素；

2. 將上述序列再次歸并，形成 floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素；

3. 重復(fù)步驟2，直到所有元素排序完畢。

如圖（7-1）所示：

圖（7-1）

迭代法

1. 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列

2. 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置

3. 比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

4. 重復(fù)步驟3直到某一指針到達(dá)序列尾

5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

java代碼實(shí)現(xiàn)

歸并排序其實(shí)要做兩件事：

1. 分解：將序列每次折半拆分

2. 合并：將劃分后的序列段兩兩排序合并

因此，歸并排序?qū)嶋H上就是兩個(gè)操作，拆分+合并

/**
 * 歸并排序（遞歸）
 *
 * ①. 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成 floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素；
 * ②. 將上述序列再次歸并，形成 floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素；
 * ③. 重復(fù)步驟②，直到所有元素排序完畢。
 * @param arr    待排序數(shù)組
 */
public static int[] mergingSort(int[] arr){
    if(arr.length <= 1) return arr;

    int num = arr.length >> 1;
    int[] leftArr = Arrays.copyOfRange(arr, 0, num);
    int[] rightArr = Arrays.copyOfRange(arr, num, arr.length);
    System.out.println("split two array: " + Arrays.toString(leftArr) + " And " + Arrays.toString(rightArr));
    return mergeTwoArray(mergingSort(leftArr), mergingSort(rightArr));      //不斷拆分為最小單元，再排序合并
}

private static int[] mergeTwoArray(int[] arr1, int[] arr2){
    int i = 0, j = 0, k = 0;
    int[] result = new int[arr1.length + arr2.length];  //申請(qǐng)額外的空間存儲(chǔ)合并之后的數(shù)組
    while(i < arr1.length && j < arr2.length){      //選取兩個(gè)序列中的較小值放入新數(shù)組
        if(arr1[i] <= arr2[j]){
            result[k++] = arr1[i++];
        }else{
            result[k++] = arr2[j++];
        }
    }
    while(i < arr1.length){     //序列1中多余的元素移入新數(shù)組
        result[k++] = arr1[i++];
    }
    while(j < arr2.length){     //序列2中多余的元素移入新數(shù)組
        result[k++] = arr2[j++];
    }
    System.out.println("Merging: " + Arrays.toString(result));
    return result;
}

復(fù)雜分析如下：

總結(jié)：

從效率上看，歸并排序可算是排序算法中的”佼佼者”. 假設(shè)數(shù)組長(zhǎng)度為n，那么拆分?jǐn)?shù)組共需logn，, 又每步都是一個(gè)普通的合并子數(shù)組的過(guò)程， 時(shí)間復(fù)雜度為O(n)， 故其綜合時(shí)間復(fù)雜度為O(nlogn)。另一方面， 歸并排序多次遞歸過(guò)程中拆分的子數(shù)組需要保存在內(nèi)存空間， 其空間復(fù)雜度為O(n)。

八. 基數(shù)排序

概述

基數(shù)排序（Radix sort）是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。

實(shí)現(xiàn)方式

將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開(kāi)始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個(gè)有序序列。

基數(shù)排序按照優(yōu)先從高位或低位來(lái)排序有兩種實(shí)現(xiàn)方案：

1. MSD（Most significant digital） 從最左側(cè)高位開(kāi)始進(jìn)行排序。先按k1排序分組, 同一組中記錄, 關(guān)鍵碼k1相等, 再對(duì)各組按k2排序分成子組, 之后, 對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組, 直到按最次位關(guān)鍵碼kd對(duì)各子組排序后. 再將各組連接起來(lái), 便得到一個(gè)有序序列。MSD方式適用于位數(shù)多的序列。

2. LSD （Least significant digital）從最右側(cè)低位開(kāi)始進(jìn)行排序。先從kd開(kāi)始排序，再對(duì)kd-1進(jìn)行排序，依次重復(fù)，直到對(duì)k1排序后便得到一個(gè)有序序列。LSD方式適用于位數(shù)少的序列。

如圖（8-1）所示：

圖（8-1）

我們以LSD為例，從最低位開(kāi)始，具體算法描述如下：

1. 取得數(shù)組中的最大數(shù)，并取得位數(shù)；

2. arr為原始數(shù)組，從最低位開(kāi)始取每個(gè)位組成radix數(shù)組；

3. 對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；

java實(shí)現(xiàn)方式

基數(shù)排序：通過(guò)序列中各個(gè)元素的值，對(duì)排序的N個(gè)元素進(jìn)行若干趟的“分配”與“收集”來(lái)實(shí)現(xiàn)排序。

分配：我們將L[i]中的元素取出，首先確定其個(gè)位上的數(shù)字，根據(jù)該數(shù)字分配到與之序號(hào)相同的桶中

收集：當(dāng)序列中所有的元素都分配到對(duì)應(yīng)的桶中，再按照順序依次將桶中的元素收集形成新的一個(gè)待排序列L[]。對(duì)新形成的序列L[]重復(fù)執(zhí)行分配和收集元素中的十位、百位…直到分配完該序列中的最高位，則排序結(jié)束

/**
 * 基數(shù)排序（LSD 從低位開(kāi)始）
 *
 * 基數(shù)排序適用于：
 *  (1)數(shù)據(jù)范圍較小，建議在小于1000
 *  (2)每個(gè)數(shù)值都要大于等于0
 *
 * ①. 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
 * ②. arr為原始數(shù)組，從最低位開(kāi)始取每個(gè)位組成radix數(shù)組；
 * ③. 對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；
 * @param arr    待排序數(shù)組
 */
public static void radixSort(int[] arr){
    if(arr.length <= 1) return;

    //取得數(shù)組中的最大數(shù)，并取得位數(shù)
    int max = 0;
    for(int i = 0; i < arr.length; i++){
        if(max < arr[i]){
            max = arr[i];
        }
    }
    int maxDigit = 1;
    while(max / 10 > 0){
        maxDigit++;
        max = max / 10;
    }
    System.out.println("maxDigit: " + maxDigit);

    //申請(qǐng)一個(gè)桶空間
    int[][] buckets = new int[10][arr.length];
    int base = 10;

    //從低位到高位，對(duì)每一位遍歷，將所有元素分配到桶中
    for(int i = 0; i < maxDigit; i++){
        int[] bktLen = new int[10];        //存儲(chǔ)各個(gè)桶中存儲(chǔ)元素的數(shù)量

        //分配：將所有元素分配到桶中
        for(int j = 0; j < arr.length; j++){
            int whichBucket = (arr[j] % base) / (base / 10);
            buckets[whichBucket][bktLen[whichBucket]] = arr[j];
            bktLen[whichBucket]++;
        }

        //收集：將不同桶里數(shù)據(jù)挨個(gè)撈出來(lái),為下一輪高位排序做準(zhǔn)備,由于靠近桶底的元素排名靠前,因此從桶底先撈
        int k = 0;
        for(int b = 0; b < buckets.length; b++){
            for(int p = 0; p < bktLen[b]; p++){
                arr[k++] = buckets[b][p];
            }
        }

        System.out.println("Sorting: " + Arrays.toString(arr));
        base *= 10;
    }
}

復(fù)雜分析如下：

其中，d 為位數(shù)，r 為基數(shù)，n 為原數(shù)組個(gè)數(shù)。在基數(shù)排序中，因?yàn)闆](méi)有比較操作，所以在復(fù)雜上，最好的情況與最壞的情況在時(shí)間上是一致的，均為 O(d*(n + r))。

總結(jié)：

1. 基數(shù)排序更適合用于對(duì)時(shí)間, 字符串等這些 整體權(quán)值未知的數(shù)據(jù) 進(jìn)行排序。

2. 基數(shù)排序不改變相同元素之間的相對(duì)順序，因此它是穩(wěn)定的排序算法。

到此，相信大家對(duì)“常用排序算法以及怎么用Java實(shí)現(xiàn)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！