[[379394]]

或許你已經(jīng)學(xué)過了這些常見的排序算法，或者你看過了別人寫的文章，但是這篇文章絕對(duì)不會(huì)浪費(fèi)你的時(shí)間，一定會(huì)有所收獲的。

寫在前面

這不快過年了嘛，袁廚想著給袁記菜館的各位同事發(fā)些年終獎(jiǎng)，讓大家回家過個(gè)好年。讓菜館的店小二，二蛋也回家娶個(gè)媳婦。

袁記菜館內(nèi)

袁廚：小二，最近快要過年了，咱們店也要給大家發(fā)點(diǎn)年終獎(jiǎng)啦，你去根據(jù)咱們的紅黑豆小本本，看一下大家都該發(fā)多少的年終獎(jiǎng)，然后根據(jù)金額從小到大排好，按順序一個(gè)個(gè)發(fā)錢，大家回去過個(gè)好年，你也老大不小了，回去娶個(gè)媳婦。

小二：好滴掌柜的，我現(xiàn)在馬上就去。

上面說到的按照金額從小到大排好就是我們今天要講的內(nèi)容 --- 排序。

排序是我們生活中經(jīng)常會(huì)面對(duì)的問題，體育課的時(shí)候，老師會(huì)讓我們從矮到高排列，考研錄取時(shí)，成績會(huì)按總分從高到底進(jìn)行排序(考研的各位讀者，你們必能收到心儀學(xué)校給你們寄來的大信封)，我們網(wǎng)購時(shí)，有時(shí)會(huì)按銷量從高到低，價(jià)格從低到高的順序?qū)⒆罘显蹅冾A(yù)期的商品列在前面，這些都是我們生活中的例子。

排序概念：將雜亂無章的數(shù)據(jù)元素，通過一定的方法(排序算法)按關(guān)鍵字順序排列的過程叫做排序。例如我們上面的銷量和價(jià)格就是關(guān)鍵字。

排序算法的穩(wěn)定性

什么是排序算法的穩(wěn)定性呢?

因?yàn)槲覀兇判虻挠涗浶蛄兄锌赡艽嬖趦蓚€(gè)或兩個(gè)以上的關(guān)鍵字相等的記錄，排序結(jié)果可能會(huì)存在不唯一的情況，所以我們排序之后，如果相等元素之間原有的先后順序不變。則稱所用的排序方法是穩(wěn)定的，反之則稱之為不穩(wěn)定的。見下圖

例如上圖，我們的數(shù)組中有兩個(gè)相同的元素 4， 我們分別用不同的排序算法對(duì)其排序，算法一排序之后，兩個(gè)相同元素的相對(duì)位置沒有發(fā)生改變，我們則稱之為穩(wěn)定的排序算法，算法二排序之后相對(duì)位置發(fā)生改變，則為不穩(wěn)定的排序算法。

那排序算法的穩(wěn)定性又有什么用呢?

在我們刷題中大多只是將數(shù)組進(jìn)行排序，只需考慮時(shí)間復(fù)雜度，空間復(fù)雜度等指標(biāo)，排序算法是否穩(wěn)定，一般不進(jìn)行考慮。但是在真正軟件開發(fā)中排序算法的穩(wěn)定性是一個(gè)特別重要的衡量指標(biāo)。繼續(xù)說我們剛才的例子。我們想要實(shí)現(xiàn)年終獎(jiǎng)從少到多的排序，然后相同年終獎(jiǎng)區(qū)間內(nèi)的紅豆數(shù)也按照從少到多進(jìn)行排序。

排序算法的穩(wěn)定性在這里就顯得至關(guān)重要。這是為什么呢?見下圖

第一次排序之后，所有的職工按照紅豆數(shù)從少到多有序。

第二次排序中，我們使用穩(wěn)定的排序算法，所以經(jīng)過第二次排序之后，年終獎(jiǎng)相同的職工，仍然保持著紅豆的有序(相對(duì)位置不變)，紅豆仍是從小到大排序。我們使用穩(wěn)定的排序算法，只需要兩次排序即可。

穩(wěn)定排序可以讓第一個(gè)關(guān)鍵字排序的結(jié)果服務(wù)于第二個(gè)關(guān)鍵字排序中數(shù)值相等的那些數(shù)。

上述情況如果我們利用不穩(wěn)定的排序算法，實(shí)現(xiàn)這一效果是十分復(fù)雜的。

比較類和非比較類

我們根據(jù)元素是否依靠與其他元素的比較來決定元素間的相對(duì)次序。以此來區(qū)分比較類排序算法和非比較類排序算法。

內(nèi)排序和外排序

內(nèi)排序是在排序的整個(gè)過程中，待排序的所有記錄全部被放置在內(nèi)存中。外排序是由于排序的記錄個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存中，整個(gè)排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進(jìn)行，常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。

對(duì)我們內(nèi)排序來說，我們主要受三個(gè)方面影響，時(shí)間性能，輔助空間，算法的復(fù)雜性

時(shí)間性能

在我們的排序算法執(zhí)行過程中，主要執(zhí)行兩種操作比較和交換，比較是排序算法最起碼的操作，移動(dòng)指記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。所以我們一個(gè)高效的排序算法，應(yīng)該盡可能少的比較和移動(dòng)。

輔助空間

執(zhí)行算法所需要的輔助空間的多少，也是來衡量排序算法性能的一個(gè)重要指標(biāo)

算法的復(fù)雜度

這里的算法復(fù)雜度不是指算法的時(shí)間復(fù)雜度，而是指算法本身的復(fù)雜度，過于復(fù)雜的算法也會(huì)影響排序的性能。

下面我們一起先來復(fù)習(xí)兩種簡(jiǎn)單排序算法，冒泡排序和簡(jiǎn)單選擇排序，看看有沒有之前忽略的東西。后面會(huì)持續(xù)連載，把常見的和實(shí)用的排序算法都進(jìn)行總結(jié)。

冒泡排序(Bubble Sort)

我們?cè)诟鱾€(gè)算法書上學(xué)習(xí)排序時(shí)，第一個(gè)估計(jì)都是冒泡排序。主要是這個(gè)排序算法思路最簡(jiǎn)單，也最容易理解，(也可能是它的名字好聽，哈哈)，學(xué)過的老哥們也一起來復(fù)習(xí)一下吧，我們一起深挖一下冒泡排序。

冒泡排序的基本思想是，兩兩比較相鄰記錄的關(guān)鍵字，如果是反序則交換，直到?jīng)]有反序?yàn)橹埂Ｃ芭菖判蛞淮蚊芭輹?huì)讓至少一個(gè)元素移動(dòng)到它應(yīng)該在的位置，那么如果數(shù)組有 n 個(gè)元素，重復(fù) n 次后則一定能完成排序。根據(jù)定義可知那么冒泡排序顯然是一種比較類排序。

最簡(jiǎn)單的排序?qū)崿F(xiàn)

我們先來看一下這段代碼

class Solution { 
    public int[] sortArray(int[] nums) { 
        int len = nums.length; 
        for (int i = 0; i < len; ++i) { 
            for (int j = i+1; j < len; ++j) { 
                if (nums[i] > nums[j]) { 
                    swap(nums,i,j); 
                } 
            } 
        } 
        return nums; 
          
    } 
    public void swap(int[] nums,int i,int j) { 
        int temp = nums[i]; 
        nums[i] = nums[j]; 
        nums[j] = temp; 
    } 
} 

我們來思考一下上面的代碼，每次讓關(guān)鍵字 nums[i] 和 nums[j] 進(jìn)行比較如果 nums[i] > nums[j] 時(shí)則進(jìn)行交換，這樣 nums[0] 在經(jīng)過一次循環(huán)后一定為最小值。

那么這段代碼是冒泡排序嗎?顯然不是，我們冒泡排序的思想是兩兩比較相鄰記錄的關(guān)鍵字，注意里面有相鄰記錄，所以這段代碼不是我們的冒泡排序，下面我們用動(dòng)圖來模擬一下冒泡排序的執(zhí)行過程，看完之后一定可以寫出正宗的冒泡排序。

冒泡排序代碼

class Solution { 
    public int[] sortArray(int[] nums) { 
        int len = nums.length; 
        for (int i = 0; i < len; ++i) { 
            for (int j = 0; j < len - i - 1; ++j) { 
                if (nums[j] > nums[j+1]) { 
                    swap(nums,j,j+1); 
                } 
            } 
        } 
        return nums;        
    } 
    public void swap(int[] nums,int i,int j) { 
        int temp = nums[i]; 
        nums[i] = nums[j]; 
        nums[j] = temp; 
    } 
} 

上圖中的代碼則為正宗的冒泡排序代碼，但是我們是不是發(fā)現(xiàn)了這個(gè)問題

我們此時(shí)數(shù)組已經(jīng)完全有序了，可以直接返回，但是動(dòng)圖中并沒有返回，而是繼續(xù)執(zhí)行，那我們有什么辦法讓其完全有序時(shí)，直接返回，不繼續(xù)執(zhí)行呢?

我們?cè)O(shè)想一下，我們是通過 nums[j] 和 nums[j+1] 進(jìn)行比較，如果大于則進(jìn)行交換，那我們?cè)O(shè)想一下，如果一個(gè)完全有序的數(shù)組，我們進(jìn)行冒泡排序，每次比較發(fā)現(xiàn)都不用進(jìn)行交換。那么如果沒有發(fā)生交換則說明當(dāng)前完全有序。

那我們可不可以通過一個(gè)標(biāo)志位來進(jìn)行判斷是否發(fā)生了交換呢?當(dāng)然是可以的

我們來對(duì)冒泡排序進(jìn)行改進(jìn)

改進(jìn)的冒泡排序代碼

class Solution { 
    public int[] sortArray (int[] nums) { 
        int len = nums.length; 
        //標(biāo)志位 
        boolean flag = true; 
        //注意看 for 循環(huán)條件 
        for (int i = 0; i < len && flag; ++i) { 
            //如果沒發(fā)生交換，則依舊為false，下次就會(huì)跳出循環(huán) 
            flag = false; 
            for (int j = 0; j < len - i - 1; ++j) { 
                if (nums[j] > nums[j+1]) { 
                    swap(nums,j,j+1); 
                    //發(fā)生交換，則變?yōu)?span id="k6zqhab033oa"    class="keyword">true,下次繼續(xù)判斷 
                    flag = true; 
                } 
            }           
        } 
        return nums;          
    } 
    public void swap (int[] nums,int i,int j) { 
        int temp = nums[i]; 
        nums[i] = nums[j]; 
        nums[j] = temp; 
    } 
} 

這樣我們就避免掉了已經(jīng)有序的情況下無意義的循環(huán)判斷。

時(shí)間復(fù)雜度分析

最好情況，就是要排序的表完全有序的情況下，根據(jù)改進(jìn)后的代碼，我們只需要一次遍歷即可，只需 n -1 次比較，時(shí)間復(fù)雜度為 O(n)。

最壞情況時(shí)，即待排序表逆序的情況，則需要比較(n-1) + (n-2) +.... + 2 + 1= n*(n-1)/2 ，并等量級(jí)的交換，則時(shí)間復(fù)雜度為O(n^2)。

平均情況下，需要 n*(n-1)/4 次交換操作，比較操作大于等于交換操作，而復(fù)雜度的上限是 O(n^2)，所以平均情況下的時(shí)間復(fù)雜度就是 O(n^2)。

空間復(fù)雜度分析

因?yàn)槊芭菖判蛑皇窍噜徳刂g的交換操作，只用到了常量級(jí)的額外空間，所以空間復(fù)雜度為 O(1)

穩(wěn)定性分析

那么冒泡排序是穩(wěn)定的嗎?當(dāng)然是穩(wěn)定的，我們代碼中，當(dāng) nums[j] > nums[j + 1] 時(shí)，才會(huì)進(jìn)行交換，相等時(shí)不會(huì)交換，相等元素的相對(duì)位置沒有改變，所以冒泡排序是穩(wěn)定的。

簡(jiǎn)單選擇排序(Simple Selection Sort)

我們的冒泡排序不斷進(jìn)行交換，通過交換完成最終的排序，我們的簡(jiǎn)單選擇排序的思想也很容易理解，主要思路就是我們每一趟在 n-i+1 個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列的第 i 個(gè)記錄，見下圖

例如上圖，綠色代表已經(jīng)排序的元素，紅色代表未排序的元素。我們當(dāng)前指針指向 4 ，則我們遍歷紅色元素，從中找到最小值，然后與 4 交換。我們發(fā)現(xiàn)選擇排序執(zhí)行完一次循環(huán)也至少可以將 1 個(gè)元素歸位。

下面我們來看一下代碼的執(zhí)行過程，看過之后肯定能寫出代碼的。

注：我們?yōu)榱烁菀桌斫猓琺in 值保存的是值，而不是索引，實(shí)際代碼中保存的是索引

簡(jiǎn)單選擇排序代碼

class Solution { 
    public int[] sortArray(int[] nums) { 
 
        int len = nums.length; 
        int min = 0; 
        for (int i = 0; i < len; ++i) { 
            min = i; 
            //遍歷找到最小值 
            for (int j = i + 1; j < len; ++j) {               
                if (nums[min] > nums[j]) min = j;               
            } 
            if (min != i) swap(nums,i,min);         
        } 
        return nums; 
    } 
    public void swap (int[] nums, int i, int j) { 
        int temp = nums[i]; 
        nums[i] = nums[j]; 
        nums[j] = temp; 
    } 
} 

時(shí)間復(fù)雜度分析

從簡(jiǎn)單選擇排序的過程來看，他最大的特點(diǎn)就是交換移動(dòng)元素次數(shù)相當(dāng)少，這樣也就節(jié)省了排序時(shí)間，簡(jiǎn)單選擇和冒泡排序不一樣，我們發(fā)現(xiàn)無論最好情況和最壞情況，元素間的比較次數(shù)是一樣的，第 i 次排序，需要 n - i 次比較,n 代表元素個(gè)數(shù)，則一共需要比較(n-1) + (n-2) +.... + 2 + 1= n*(n-1)/2 次。

對(duì)于交換而言，最好情況交換 0 次，最壞情況(逆序時(shí))交換 n - 1次。那么簡(jiǎn)單選擇排序時(shí)間復(fù)雜度也為 O(n^2) 但是其交換次數(shù)遠(yuǎn)小于冒泡排序，所以其效率是好于冒泡排序的。

空間復(fù)雜度分析

由我們的動(dòng)圖可知，我們的簡(jiǎn)單選擇排序只用到了常量級(jí)的額外空間，所以空間復(fù)雜度為 O(1)。

穩(wěn)定性分析

我們思考一下，我們的簡(jiǎn)單選擇排序是穩(wěn)定的嗎?

顯然不是穩(wěn)定的，因?yàn)槲覀冃枰谥羔樅竺嬲业阶钚〉闹?，與指針指向的值交換，見下圖。

此時(shí)我們需要從后面元素中找到最小的元素與指針指向元素交換，也就是元素 2 。但是我們交換后發(fā)現(xiàn)，兩個(gè)相等元素 3 的相對(duì)位置發(fā)生了改變，所以簡(jiǎn)單選擇排序是不穩(wěn)定的排序算法。

本文轉(zhuǎn)載自微信公眾號(hào)「袁廚的算法小屋」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系袁廚的算法小屋公眾號(hào)。