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

　　一. 排序算法

　　1.概念

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

　　● 直接插入排序

　　● 希爾排序

　　● 簡單選擇排序

　　● 堆排序

　　● 冒泡排序

　　● 快速排序

　　● 歸并排序

　　● 基數(shù)排序法

　　2.排序算法分類

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

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

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

　　二. 冒泡排序

　　1.概念

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

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

　　之所以要把該算法稱為“冒泡算法”，這是因為每個大的元素，每次經(jīng)過交換都會慢慢“浮”到數(shù)組的頂端，故名“冒泡排序”。

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

　　2.實現(xiàn)步驟

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

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

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

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

　　(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ī)則，需要交換。互換位置后，元素7在下標(biāo)6的位置上，元素9在下標(biāo)7的位置上。

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

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

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

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

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

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

　　這樣我們就理解了冒泡排序的實現(xiàn)思路和過程，接下來我們再來看看該如何在Java中通過代碼實現(xiàn)冒泡排序。

　　3. 編碼實現(xiàn)

　　我們根據(jù)上述冒泡排序算法的文字描述步驟，利用Java語言進(jìn)行編程實現(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++;
            //臨時變量 用于交換
            int tmp = 0;
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

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

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

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

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

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

　　4. 算法總結(jié)

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

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

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

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

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

　　三. 選擇排序

　　1.概念

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

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

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

　　2.實現(xiàn)思路

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

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

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

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

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

　　但是如何選出最小的一個元素呢?

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

　　3.實現(xiàn)步驟

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

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

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

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

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

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

　　4.編碼實現(xiàn)

　　接下來小編也使用Java語言，把選擇排序的算法通過編程給大家實現(xiàn)一下：　

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

　　5.算法總結(jié)

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

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

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

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

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

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