1、 認(rèn)識(shí)排序

在學(xué)校中，如果我們要參加運(yùn)動(dòng)會(huì)，或者軍訓(xùn)的時(shí)候，會(huì)按照身高從矮到高進(jìn)行站隊(duì)，比如上課老師手上拿的考勤表，通常是按照學(xué)號(hào)從低到高進(jìn)行排序的。再比如編程語言排行榜，也是在排序。

生活中有相當(dāng)多的排序場(chǎng)景，由此可知，排序還是很重要的， 本章就會(huì)介紹常見的一些排序算法。

所謂排序呢，就拿我們上面的舉例來說，會(huì)按照某個(gè)或某些關(guān)鍵字的大小，遞增或者遞減排列起來的操作，這就是排序，這里面也涉及到排序的穩(wěn)定性，舉個(gè)例子：

比如有這樣的一組數(shù)據(jù)：B D A C A F，要按照他們的 ascll 碼來排序，這里出現(xiàn)了兩個(gè) A，我們把第一個(gè)出現(xiàn)的 A 稱為 A1，第二個(gè)出現(xiàn)的 A 稱為 A2。

假定排序后結(jié)果為：A1 A2 B C D F，那么這個(gè)排序算法就是穩(wěn)定的。

假設(shè)排序后結(jié)果為：A2 A1 B C D F，那么這個(gè)排序算法就是不穩(wěn)定的。

簡(jiǎn)而言之，如果待排序的數(shù)據(jù)中，有兩個(gè)相同的元素，排序結(jié)束后，這兩個(gè)元素的關(guān)系沒有發(fā)生改變，比如 A1 排序前在 A2 前面，排完序后，A1 還在 A2 前面，這就是穩(wěn)定的排序算法。

注意：一個(gè)不穩(wěn)定的排序算法，天生就是不穩(wěn)定的，但是一個(gè)穩(wěn)定的排序算法，你可以把它設(shè)計(jì)成不穩(wěn)定的。

2、常見排序的分類

這張圖，概括了我們后續(xù)要講的排序算法，接著正式進(jìn)入本章的學(xué)習(xí)吧！(排序算法章節(jié)，默認(rèn)都是升序排序) 注：后續(xù)所說的復(fù)雜度 log，都是以2為底，特殊的會(huì)標(biāo)注出來。

3、直接插入排序

現(xiàn)在想請(qǐng)各位小伙伴，想象一下自己在摸撲克牌，摸了第一張牌放在了自己的手中，接著再摸一張，把這張牌跟手上的一張牌進(jìn)行比較，把它放到合適的位置， 接著再摸一張，把這張牌跟手上的兩張牌進(jìn)行比較，放到合適的位置。

這就是直接插入排序，簡(jiǎn)單來說，我們每次取的元素，會(huì)往一個(gè)有序的序列中插入，也就是每次摸牌之前，手上的牌都是排好序的，我們只需要把新摸到的牌，依次與手上有序的牌進(jìn)行比較，把它放入合適的位置就行！

這里我們用一副靜態(tài)的圖來簡(jiǎn)單演示下：

大致的思想我們已經(jīng)明白了，接下來我們就需要用代碼來實(shí)現(xiàn)他：

public void insertSort(int[] array) {     // 外循環(huán)控制趟數(shù), 第一張牌默認(rèn)有序, 所以 i 從 1 開始     for (int i = 1; i < array.length; i++) {         int tmp = array[i]; //當(dāng)前摸到的牌         // 每次從手中牌的最后一張牌開始比較, 一直比到第一張牌         int j = i - 1;         for (; j >= 0; j--) {             //如果當(dāng)前位置的牌,大于我摸到的牌,就往后挪             if (array[j] > tmp) {                 array[j + 1] = array[j];             } else {                 break;             }         }         // 把摸到的牌放到對(duì)應(yīng)位置上         array[j + 1] = tmp;     } }

• 時(shí)間復(fù)雜度分析：外循環(huán)一共要 n – 1 次，內(nèi)循環(huán)每次最差的情況下要比較 1….n 次，那么去掉 n 前面的小項(xiàng)，也就是 (n – 1) * n 次，即 n^2 – n，去掉最小項(xiàng)，最后的時(shí)間復(fù)雜度為 O(n^2)
• 空間復(fù)雜度分析：只是開辟了一個(gè) tmp 的變量 i，j，常數(shù)，即空間復(fù)雜度：O(1)
• 穩(wěn)定性：穩(wěn)定
• 該排序再數(shù)據(jù)越接近有序的情況，時(shí)間效率越高。

4、希爾排序(縮小增量排序)

這個(gè)排序是直接插入排序的一種優(yōu)化，你可以想象一下，你面前有并排放好的 8 個(gè)愛心號(hào)碼牌，但是它們是無序的，我們要給號(hào)碼牌分組，按要求，第一次間隔為 4 個(gè)號(hào)碼牌的為一組，分完組后進(jìn)行直接插入排序，第二次間隔為 2 個(gè)號(hào)碼牌的為一組，進(jìn)行直接插入排序，第三次間隔為 1 個(gè)號(hào)碼牌為一組，進(jìn)行直接插入排序。

聽到這有點(diǎn)沒理解，沒關(guān)系，我們就通過畫圖來把我上述說的內(nèi)容再次理解下：

由上圖我們可以發(fā)現(xiàn)，當(dāng)間隔 > 1 的時(shí)候，都是預(yù)排序，也就是讓我們的數(shù)據(jù)更接近有序，但是當(dāng)間隔為 1 的時(shí)候，就是直接插入排序了，前面我們說過，直接插入排序，再數(shù)據(jù)接近有序的時(shí)候時(shí)間效率是很快的。由此可見，希爾排序，是直接插入排序的優(yōu)化版。

如何在代碼中實(shí)現(xiàn)呢？間隔的值如何取呢？代碼中把這個(gè)間隔的值稱為 gap，這個(gè) gap 的取值方法有很多，有的人提出 gap 為奇數(shù)好，有的提出 gap 為偶數(shù)好，我們就采取一種比較簡(jiǎn)單的方法來取 gap 值，首次取數(shù)組長(zhǎng)度一半的值為 gap，后續(xù) gap /= 2，即可。當(dāng) gap 為 1，也就是直接插入排序了。

代碼實(shí)現(xiàn)如下：

public void shellSort(int[] array) {     // gap初始值設(shè)置成數(shù)組長(zhǎng)度的一半     int gap = array.length >> 1;     // gap 為 1 的時(shí)候直接插入排序     while (gap >= 1) {         shell(array, gap);         gap >>= 1; // 更新 gap 值 等價(jià)于 -> gap /= 2;     } } private void shell(int[] array, int gap) {     for (int i = gap; i < array.length; i++) {         int tmp = array[i];         int j = i - gap;         for (; j >= 0; j -= gap) {             if (array[j] > tmp) {                 array[j + gap] = array[j];             } else {                 break;             }         }         array[j + gap] = tmp;     } }

如果實(shí)在是不好理解，就結(jié)合上邊講的直接插入排序來理解，相信你能理解到的。

• 時(shí)間復(fù)雜度分析：希爾排序的時(shí)間復(fù)雜度不好分析， 這里我們就大概記一下，約為 O(n^1.3)，感興趣的話，可以查閱一下相關(guān)書籍。
• 空間復(fù)雜度分析：仍然開辟的是常數(shù)個(gè)變量，空間復(fù)雜度為 O(1)
• 穩(wěn)定性：不穩(wěn)定

5、選擇排序

這個(gè)排序是個(gè)很簡(jiǎn)單的排序，你想象一下，有個(gè)小屁孩，喜歡玩小球，我給他安排了個(gè)任務(wù)，把這一排小球從小到大排列起來，擺給我看，于是小屁孩就找，每次從一排小球中找出最大的，放到最后，固定不動(dòng)，那是不是也就是說，每次能確定一個(gè)最大的石子的最終位置了。我們來看圖：

通過圖片我們也能看出來，每次找到最大值于最后一個(gè)值交換，所以每趟都能把最大的放到最后固定不動(dòng)，每趟能排序一個(gè)元素出來，那這樣用代碼來實(shí)現(xiàn)就很簡(jiǎn)單了：

public void selectSort(int[] array) {     int end = array.length - 1;     // 剩最后一個(gè)元素的時(shí)候, 不用比較了, 已經(jīng)有序了     // 所以 i < array.length - 1     for (int i = 0; i < array.length - 1; i++) {         int max = 0;         int j = 0;         while (j <= end) {             if (array[j] > array[max]) {                 max = j;             }             j++;         }         //找到了最大值的下標(biāo), 把最大值與最后一個(gè)值交換         swap(array, max, end--); // end-- 最后一個(gè)元素固定了, 不用參與比較     } }

這個(gè)算法有沒有可以優(yōu)化的空間呢？

有！那么既然小屁孩能一次找出最大的球，那能不能讓小屁孩一次找出兩個(gè)球出來呢？分別是這些球中，最大的和最小的，最大的放在最右邊，最小的放在最左邊，那么我們每次就能確定兩個(gè)球的最終位置，也就是我們一次能排序兩個(gè)元素。圖解：

代碼實(shí)現(xiàn)如下：

public void selectSort(int[] array) {     int left = 0;     int right = array.length - 1;     while (left < right) {         int maxIndex = left;         int minIndex = left;         // i = left + 1 -> 每次找最大最小值下標(biāo)的時(shí)候, 可以不用算默認(rèn)給的最大值和最小值下標(biāo)         for (int i = left + 1; i <= right; i++) {             if (array[i] > array[maxIndex]) {                 maxIndex = i;             }             if (array[i] < array[minIndex]) {                 minIndex = i;             }         }         swap(array, minIndex, left);         // 如果最大值為 left 的位置情況的話, 走到這, 最大值已經(jīng)被交換到 min 位置上了         if (maxIndex == left) {             // 更新最大值的位置             maxIndex = minIndex;         }         swap(array, maxIndex, right);         left++;         right--;     } }

• 時(shí)間復(fù)雜度分析：雖然是優(yōu)化了，但去小項(xiàng)之后，還是 O(n^2)
• 空間復(fù)雜度分析：O(1)
• 穩(wěn)定性：不穩(wěn)定
• 實(shí)際開發(fā)中用的不多

6、堆排序

如果你有學(xué)習(xí)過優(yōu)先級(jí)隊(duì)列，或者看過博主優(yōu)先級(jí)隊(duì)列的文章，那么這個(gè)排序?qū)τ谀銇碚f還是很輕松的，當(dāng)然在堆排序的講解中，不會(huì)過多的去介紹堆的概念，如果對(duì)這部分概念還不理解，可以移至博主的上一篇文章進(jìn)行學(xué)習(xí)。

堆排序，簡(jiǎn)單來說，就是把一組數(shù)據(jù)，看成一個(gè)完全二叉樹，再把這棵樹，建大堆或者建小堆，接著進(jìn)行排序的一種思路。至于如何建大堆或小堆，和向上調(diào)整算法以及向下調(diào)整算法，這里也不多介紹了，博主的上篇文章都詳細(xì)介紹過。

這里我們來分析一下，排升序應(yīng)該建什么堆？大堆！排降序建小堆！

這里我們來排升序，建大堆，因?yàn)榇蠖讯秧斣匾欢ㄊ嵌阎凶畲蟮模晕覀兛梢园讯秧斣睾妥詈笠粋€(gè)元素進(jìn)行交換，這樣我們就確認(rèn)了最大值的位置，接著將交換后的堆頂元素進(jìn)行向下調(diào)整，仍然使得該數(shù)組滿足大堆的特性！圖解如下：

如上圖步驟也很簡(jiǎn)單，先是將數(shù)組建成大堆，然后利用大堆來進(jìn)行堆排序，首先將堆頂元素和最后一個(gè)元素交換，由此最大的元素就有序了，接著將該堆進(jìn)行向下調(diào)整，使繼續(xù)滿足大堆性質(zhì)，依次進(jìn)行下去即可。

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

public void heapSort(int[] array) {     // 建大堆 從最后一個(gè)非葉子節(jié)點(diǎn)開始向下調(diào)整     // 非葉子節(jié)點(diǎn)下標(biāo) = (孩子節(jié)點(diǎn)下標(biāo) - 1) / 2     for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {         shiftDown(array, parent, array.length);     }     // 建大堆完成后, 每次堆頂元素與最后一個(gè)元素交換, 鎖定最大元素的位置     for (int len = array.length - 1; len > 0; len--) {         swap(array, 0, len); //根節(jié)點(diǎn)與最后一個(gè)元素交換         shiftDown(array, 0, len); //根節(jié)點(diǎn)位置向下調(diào)整     } } private void shiftDown(int[] array, int parent, int len) {     int child = parent * 2 + 1;     while (child < len) {         if (child + 1 < len && array[child + 1] > array[child]) {             child++;         }         // 判斷父節(jié)點(diǎn)是否大于較大的孩子節(jié)點(diǎn)         if (array[parent] < array[child]) {             swap(array, parent, child);             // 更新下標(biāo)的位置             parent = child;             child = parent * 2 + 1;         } else {             return;         }     } }

• 時(shí)間復(fù)雜度分析：建堆的時(shí)間復(fù)雜度優(yōu)先級(jí)隊(duì)列那期有說過為 O(n)，排序調(diào)整堆的時(shí)候，一共要調(diào)整 n-1 次，每次向下調(diào)整的時(shí)間復(fù)雜度是 logn，所以即 logn(n – 1)，即 O(n*logn)，加上面建堆的時(shí)間復(fù)雜度：O(n) + O(n*logn)，最終時(shí)間復(fù)雜度也就是：O(n*logn)。
• 空間復(fù)雜度分析：O(1)
• 穩(wěn)定性：不穩(wěn)定