全文大約【4400】字，不說(shuō)廢話，只講可以讓你學(xué)到技術(shù)、明白原理的純干貨!本文帶有豐富的案例及配圖視頻，讓你更好地理解和運(yùn)用文中的技術(shù)概念，并可以給你帶來(lái)具有足夠啟迪的思考......

　　一. 排序算法

　　1.概念

　　所謂排序，就是使一串記錄可以按照其中某個(gè)或某些關(guān)鍵字的大小，根據(jù)遞增或遞減的排列起來(lái)。而排序算法，就是使得數(shù)據(jù)按照特定要求排列的方法。我們?cè)陂_(kāi)發(fā)時(shí)常用的排序算法有如下幾個(gè)：

　　● 直接插入排序

　　● 希爾排序

　　● 簡(jiǎn)單選擇排序

　　● 堆排序

　　● 冒泡排序

　　● 快速排序

　　● 歸并排序

　　● 基數(shù)排序法

　　2.排序算法分類

　　以上排序算法都屬于內(nèi)部排序，也就是只考慮較小數(shù)據(jù)量且僅需使用內(nèi)存的排序算法，他們之間關(guān)系如下圖所示：

　　因?yàn)閷?shí)際上具體的排序算法非常多，小編這個(gè)是Java的系列學(xué)習(xí)文章，所以我這里不會(huì)把每個(gè)算法都講解到。后面我會(huì)出一個(gè)專門的算法系列文章，敬請(qǐng)大家持續(xù)關(guān)注哦。

　　接下來(lái)小編就以冒泡、選擇排序算法為例，重點(diǎn)給大家講解一下排序相關(guān)的內(nèi)容。

　　二. 冒泡排序

　　1.概念

　　冒泡排序(Bubble Sort)，可以說(shuō)是我們學(xué)習(xí)編程時(shí)必學(xué)且知名度最高的一個(gè)經(jīng)典排序算法，同時(shí)也是各種考試和面試中出鏡率最高的一個(gè)排序算法。

　　首先，我們要知道一點(diǎn)，冒泡排序?qū)儆诮粨Q排序算法的一種。所謂交換排序算法，是指在排序過(guò)程中，要發(fā)生數(shù)組元素的交換。

　　之所以要把該算法稱為“冒泡算法”，這是因?yàn)槊總€(gè)大的元素，每次經(jīng)過(guò)交換都會(huì)慢慢“浮”到數(shù)組的頂端，故名“冒泡排序”。

　　冒泡排序的核心思想，是把相鄰的元素進(jìn)行兩兩比較，當(dāng)一個(gè)元素大于右側(cè)相鄰的元素時(shí)，就交換它們的位置;當(dāng)一個(gè)元素小于或等于右側(cè)相鄰的元素時(shí)，則保持位置不變。大家注意，冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)。每次冒泡操作都是對(duì)相鄰的兩個(gè)元素進(jìn)行比較，看是否滿足大小關(guān)系。

　　2.實(shí)現(xiàn)步驟

　　接下來(lái)小編就以一個(gè)數(shù)值型的數(shù)組為例，向大家介紹冒泡排序的整個(gè)排序過(guò)程。

　　假設(shè)，我們現(xiàn)在有一個(gè)待排序的數(shù)組，其數(shù)組元素值依次為[5，8，6，3，9，,2，1，,7]。如果我們采用冒泡排序算法，按從小到大的規(guī)則對(duì)其排序，其詳細(xì)過(guò)程會(huì)如下所示：

　　(1). 將5和8進(jìn)行比較，因?yàn)闈M足左小右大的規(guī)則，不需要交換，保持元素位次不變;

　　(2). 將8和6進(jìn)行比較，因不滿足左小右大的規(guī)則，則需要交換。將8和6位置互換，互換位置后，元素6在下標(biāo)1這個(gè)位置上，元素8在下標(biāo)2這個(gè)位置上;

　　(3). 接著將8和3進(jìn)行比較，不滿足左小右大規(guī)則，需要交換。將8和3位置互換，互換位置后，元素3在下標(biāo)2的位置上，元素8在下標(biāo)3的位置上;

　　(4). 繼續(xù)將8和9進(jìn)行比較，滿足左小右大規(guī)則，不需要交換，保持元素位次不變;

　　(5). 將9和2進(jìn)行比較，不滿足左小右大的規(guī)則，需要交換。將9和2位置互換，互換位置后，元素2在下標(biāo)4的位置上，元素9在下標(biāo)5的位置上;

　　(6). 將9和1進(jìn)行比較，不滿足左小右大的規(guī)則，需要交換。將9和1位置互換，互換位置后，元素1在下標(biāo)5的位置上，元素9在下標(biāo)6的位置上。

　　(7). 繼續(xù)將9和7進(jìn)行比較，不滿足左小右大的規(guī)則，需要交換?；Q位置后，元素7在下標(biāo)6的位置上，元素9在下標(biāo)7的位置上。

　　如果我們把上述的文字描述，轉(zhuǎn)換為圖片，則會(huì)如下圖所示：

　　這樣就完成了第一輪的交換比較。經(jīng)過(guò)第一輪交換后，元素9作為數(shù)列中最大的元素，就像是汽水里的氣泡一樣浮到了最右側(cè)。接著我們繼續(xù)如此重復(fù)上述的比較過(guò)程，每一輪結(jié)束后，都會(huì)有一個(gè)本輪最大的元素被移到了最右側(cè)，如下所示：

　　每一輪的排序結(jié)果最終會(huì)如上圖所示，所以最終的排序結(jié)果就是最后一排的數(shù)值結(jié)果。最后我們來(lái)總結(jié)下，冒泡排序算法的3個(gè)核心步驟：

　　● 第1步：比較相鄰的元素。如果第一個(gè)元素比第二個(gè)元素大，就將兩者交換;

　　● 第2步：對(duì)每一對(duì)相鄰的兩個(gè)元素進(jìn)行同樣的操作。從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，最后的元素就是最大的數(shù)。

　　● 第3步：針對(duì)所有元素重復(fù)以上步驟。每重復(fù)一輪上述步驟，需要操作的元素就會(huì)越來(lái)越少，直到?jīng)]有任何一對(duì)元素需要比較。

　　這樣我們就理解了冒泡排序的實(shí)現(xiàn)思路和過(guò)程，接下來(lái)我們?cè)賮?lái)看看該如何在Java中通過(guò)代碼實(shí)現(xiàn)冒泡排序。

　　3. 編碼實(shí)現(xiàn)

　　我們根據(jù)上述冒泡排序算法的文字描述步驟，利用Java語(yǔ)言進(jìn)行編程實(shí)現(xiàn)，代碼如下所示：　　

public static void bubbleSort(int[] arr) {
    int count = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1-i; j++) {
            count++;
            //臨時(shí)變量 用于交換
            int tmp = 0;
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

　　最終執(zhí)行完上述代碼后，arr數(shù)組就變成了一個(gè)有序的數(shù)組。

　　大家要注意，在上述代碼中，bubbleSort方法可以接收一個(gè)整數(shù)類型的數(shù)組arr，通過(guò)兩層for循環(huán)，最終就可以實(shí)現(xiàn)整型數(shù)組元素的冒泡排序。其中：

　　● 內(nèi)層for循環(huán)是將相鄰的兩個(gè)元素進(jìn)行比較。如果不滿足左小右大的規(guī)則，就將兩個(gè)元素進(jìn)行交換。

　　● 交換相鄰的元素時(shí)，使用到了臨時(shí)變量tmp。

　　● 外層for循環(huán)，用來(lái)控制需要進(jìn)行幾輪比較，即比較的輪次。

　　4. 算法總結(jié)

　　通過(guò)上述Java程序，我們就實(shí)現(xiàn)了冒泡算法的代碼實(shí)現(xiàn)，最后小編再來(lái)給大家總結(jié)一下冒泡排序算法的時(shí)間和空間復(fù)雜度等情況。

　　(1). 冒泡排序的平均時(shí)間復(fù)雜度是O(n²)。如果數(shù)組本身已經(jīng)排好了順序，在優(yōu)化后的算法中，需要比較n-1次，此時(shí)的時(shí)間復(fù)雜度是O(n)。而當(dāng)數(shù)組是無(wú)序的，在優(yōu)化后的算法中，需要比較的次數(shù)是n(n-1)/2次，此時(shí)的時(shí)間復(fù)雜度是O(n²)。

　　(2). 冒泡排序的空間復(fù)雜度為O(1) 。

　　(3). 冒泡排序是原地排序。

　　(4). 冒泡排序的重點(diǎn)是左右相鄰的兩個(gè)元素進(jìn)行兩兩比較，當(dāng)兩個(gè)元素?cái)?shù)值相同時(shí)不換位，所以是穩(wěn)定排序。

　　三. 選擇排序

　　1.概念

　　選擇排序(Selection Sort)是一種最簡(jiǎn)單直觀的排序算法。即使在我們的日常生活中，大家可能都會(huì)經(jīng)常無(wú)意地進(jìn)行選擇排序。比如我們?nèi)コ匈I蘋(píng)果，你拿了一個(gè)袋子，從眾多的蘋(píng)果中挑了一個(gè)最大的放入袋中，然后又從剩下的蘋(píng)果中挑了一個(gè)最大的放入袋子。這樣如此反復(fù)，直到挑夠了需要的蘋(píng)果去結(jié)賬。這其實(shí)就是選擇排序的實(shí)現(xiàn)思想，就是不斷地從未排序的元素中選擇最大(或最小)的元素，放入到已排好序的元素集合中，直到未排序的元素為空。

　　基于上述實(shí)現(xiàn)思想，我們就可以提取出選擇排序的實(shí)現(xiàn)原理：

　　將一個(gè)數(shù)組分成有序的區(qū)間和無(wú)序的區(qū)間兩部分，初始時(shí)有序區(qū)間為空，每次從無(wú)序區(qū)間中選出最小的元素，并放到有序區(qū)間的末尾，直到無(wú)序區(qū)間為空。

　　2.實(shí)現(xiàn)思路

　　按照選擇排序的實(shí)現(xiàn)原理，接下來(lái)小編再把選擇排序的實(shí)現(xiàn)思路再細(xì)化一下：

　　● 假設(shè)，給定一個(gè)數(shù)組 int[] arr = {n個(gè)數(shù)據(jù)};

　　● 第1趟排序，在無(wú)序數(shù)列 arr[0] ~ arr[n-1]中選出最小的數(shù)據(jù)，將它與arr[0]交換;

　　● 第2趟，在無(wú)序數(shù)列 arr[1] ~ arr[n-1]中選出最小的數(shù)據(jù)，將它與arr[1]交換;

　　● 依此類推，第i趟在無(wú)序數(shù)列arr[i]~arr[n-1]中選出最小的數(shù)據(jù)，將它與arr[i]交換，直到全部排序完成。

　　但是如何選出最小的一個(gè)元素呢?

　　我們先任意選一個(gè)元素，假設(shè)它就是最小的元素(默認(rèn)為無(wú)序區(qū)間的第一個(gè)元素)，然后讓這個(gè)元素與無(wú)序區(qū)間中的每一個(gè)元素挨個(gè)進(jìn)行比較。如果遇到比自己小的元素，則更新最小值的下標(biāo)，直到把無(wú)序區(qū)間遍歷完。最后的那個(gè)最小值下標(biāo)對(duì)應(yīng)的數(shù)值，就是該無(wú)序區(qū)間的最小值。

　　3.實(shí)現(xiàn)步驟

　　同樣的，小編仍然以一個(gè)示例來(lái)給大家解釋選擇排序的實(shí)現(xiàn)步驟。假如我們現(xiàn)在有一個(gè)待排序的數(shù)組[5，8，6，3，9，2，1，7]，若采用選擇排序算法進(jìn)行排序，其實(shí)現(xiàn)步驟如下：

　　(1). 初始化待排序數(shù)組[5，8，6，3，9，2，1，7];

　　(2). 從待排序數(shù)組中，選出最小值1，和第一個(gè)元素5進(jìn)行交換，即將最小的元素放在下標(biāo)0的位置上;

　　(3). 在剩下的無(wú)序區(qū)間的元素中，選擇最小的元素2，并將最小的元素2與無(wú)序區(qū)間的第一個(gè)元素8進(jìn)行交換。交換后，有序區(qū)間的元素變?yōu)?個(gè)，分別是1和2，剩余的為無(wú)序區(qū)間。

　　(4). 依次類推，將所有的元素通過(guò)不斷選擇的方式，按有序的方式放到有序區(qū)間，最終把整個(gè)數(shù)組全部排好順序。

　　我們把上述選擇排序的文字描述內(nèi)容，變成對(duì)應(yīng)的圖片，會(huì)如下圖所示：

　　4.編碼實(shí)現(xiàn)

　　接下來(lái)小編也使用Java語(yǔ)言，把選擇排序的算法通過(guò)編程給大家實(shí)現(xiàn)一下：　

public static void selectionSort(int[] arr) {
    int count = 0;
    //第一個(gè)循環(huán)用來(lái)遍歷數(shù)組中的所有數(shù)字
    for (int i = 0; i < arr.length; i++) {
        //初始化一個(gè)變量，用來(lái)記錄最小數(shù)字的下標(biāo)。初始默認(rèn)假設(shè)第一個(gè)數(shù)字就是最小數(shù)字
        int minIndex = i;
        //第二個(gè)循環(huán)，通過(guò)比較獲取數(shù)組中最小的數(shù)字的下標(biāo)
        for (int j = i + 1; j < arr.length; j++) {
            count++;
            //如果找到更小的數(shù)字
            if (arr[minIndex] > arr[j]) {
                //將minIndex變量的值修改為新的最小數(shù)字的下標(biāo)
                minIndex = j;
            }
        }
        //所有數(shù)字一個(gè)個(gè)比較結(jié)束之后，就能確認(rèn)那個(gè)數(shù)字最小了。
        //將最小的數(shù)字替換到第一個(gè)位置，將第一個(gè)位置的數(shù)字放到最小數(shù)字原來(lái)的位置，就是一次交換。
        arr[i] = arr[i] + arr[minIndex] - (arr[minIndex] = arr[i]);
    }
}

　　5.算法總結(jié)

　　選擇排序基于最簡(jiǎn)單的思路，依次把待排序的數(shù)據(jù)放入到已經(jīng)排好序的數(shù)列中，并繼續(xù)保持有序。但選擇排序的效率較低，時(shí)間復(fù)雜度是O(n2)。另外隨著排序的數(shù)據(jù)量增長(zhǎng)，效率降低的會(huì)很快。這里小編也把選擇排序給大家總結(jié)一下，核心要點(diǎn)如下：

　　(1). 選擇排序最大的特點(diǎn)，就是不論數(shù)列是否有序或亂序，選擇排序都要花費(fèi)一樣的時(shí)間來(lái)計(jì)算。比如，利用選擇排序?qū)?shù)組[1, 2, 3, 4, 5]和[3, 1, 4, 2, 5]排序，其所需要執(zhí)行的步驟是一樣的。如果用冒泡排序執(zhí)行已經(jīng)排好序的數(shù)列，則只需要一輪比較就可以得出結(jié)果。

　　(2). 選擇排序算法，無(wú)論是已排好序或未排序，都需要循環(huán)比較n(n-1)/2次。當(dāng)n->∞時(shí)，無(wú)限接近于n²，所以選擇排序算法的時(shí)間復(fù)雜度為O(n²)。

　　(3). 選擇排序算法的空間復(fù)雜度是O(1)。

　　(4). 選擇排序算法是原地排序算法，且會(huì)發(fā)生數(shù)據(jù)交換操作。

　　(5). 選擇排序是一種簡(jiǎn)單的排序算法，適用于數(shù)據(jù)量較小的情況。根據(jù)時(shí)間復(fù)雜度分析，選擇排序所花費(fèi)的時(shí)間會(huì)隨著數(shù)據(jù)量增大按照平方倍數(shù)增?，數(shù)據(jù)量越大，排序效率就越低。但是選擇排序也有優(yōu)勢(shì)，即它的實(shí)現(xiàn)思維邏輯特別簡(jiǎn)單，比較容易理解。