[[379394]]

或許你已經學過了這些常見的排序算法，或者你看過了別人寫的文章，但是這篇文章絕對不會浪費你的時間，一定會有所收獲的。

寫在前面

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

袁記菜館內

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

小二：好滴掌柜的，我現在馬上就去。

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

排序是我們生活中經常會面對的問題，體育課的時候，老師會讓我們從矮到高排列，考研錄取時，成績會按總分從高到底進行排序(考研的各位讀者，你們必能收到心儀學校給你們寄來的大信封)，我們網購時，有時會按銷量從高到低，價格從低到高的順序將最符合咱們預期的商品列在前面，這些都是我們生活中的例子。

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

排序算法的穩定性

什么是排序算法的穩定性呢?

因為我們待排序的記錄序列中可能存在兩個或兩個以上的關鍵字相等的記錄，排序結果可能會存在不唯一的情況，所以我們排序之后，如果相等元素之間原有的先后順序不變。則稱所用的排序方法是穩定的，反之則稱之為不穩定的。見下圖

例如上圖，我們的數組中有兩個相同的元素 4， 我們分別用不同的排序算法對其排序，算法一排序之后，兩個相同元素的相對位置沒有發生改變，我們則稱之為穩定的排序算法，算法二排序之后相對位置發生改變，則為不穩定的排序算法。

那排序算法的穩定性又有什么用呢?

在我們刷題中大多只是將數組進行排序，只需考慮時間復雜度，空間復雜度等指標，排序算法是否穩定，一般不進行考慮。但是在真正軟件開發中排序算法的穩定性是一個特別重要的衡量指標。繼續說我們剛才的例子。我們想要實現年終獎從少到多的排序，然后相同年終獎區間內的紅豆數也按照從少到多進行排序。

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

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

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

穩定排序可以讓第一個關鍵字排序的結果服務于第二個關鍵字排序中數值相等的那些數。

上述情況如果我們利用不穩定的排序算法，實現這一效果是十分復雜的。

比較類和非比較類

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

內排序和外排序

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

對我們內排序來說，我們主要受三個方面影響，時間性能，輔助空間，算法的復雜性

時間性能

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

輔助空間

執行算法所需要的輔助空間的多少，也是來衡量排序算法性能的一個重要指標

算法的復雜度

這里的算法復雜度不是指算法的時間復雜度，而是指算法本身的復雜度，過于復雜的算法也會影響排序的性能。

下面我們一起先來復習兩種簡單排序算法，冒泡排序和簡單選擇排序，看看有沒有之前忽略的東西。后面會持續連載，把常見的和實用的排序算法都進行總結。

冒泡排序(Bubble Sort)

我們在各個算法書上學習排序時，第一個估計都是冒泡排序。主要是這個排序算法思路最簡單，也最容易理解，(也可能是它的名字好聽，哈哈)，學過的老哥們也一起來復習一下吧，我們一起深挖一下冒泡排序。

冒泡排序的基本思想是，兩兩比較相鄰記錄的關鍵字，如果是反序則交換，直到沒有反序為止。冒泡排序一次冒泡會讓至少一個元素移動到它應該在的位置，那么如果數組有 n 個元素，重復 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; 
    } 
} 

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

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

冒泡排序代碼

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; 
    } 
} 

上圖中的代碼則為正宗的冒泡排序代碼，但是我們是不是發現了這個問題

我們此時數組已經完全有序了，可以直接返回，但是動圖中并沒有返回，而是繼續執行，那我們有什么辦法讓其完全有序時，直接返回，不繼續執行呢?

我們設想一下，我們是通過 nums[j] 和 nums[j+1] 進行比較，如果大于則進行交換，那我們設想一下，如果一個完全有序的數組，我們進行冒泡排序，每次比較發現都不用進行交換。那么如果沒有發生交換則說明當前完全有序。

那我們可不可以通過一個標志位來進行判斷是否發生了交換呢?當然是可以的

我們來對冒泡排序進行改進

改進的冒泡排序代碼

class Solution { 
    public int[] sortArray (int[] nums) { 
        int len = nums.length; 
        //標志位 
        boolean flag = true; 
        //注意看 for 循環條件 
        for (int i = 0; i < len && flag; ++i) { 
            //如果沒發生交換，則依舊為false，下次就會跳出循環 
            flag = false; 
            for (int j = 0; j < len - i - 1; ++j) { 
                if (nums[j] > nums[j+1]) { 
                    swap(nums,j,j+1); 
                    //發生交換，則變為true,下次繼續判斷 
                    flag = true; 
                } 
            }           
        } 
        return nums;          
    } 
    public void swap (int[] nums,int i,int j) { 
        int temp = nums[i]; 
        nums[i] = nums[j]; 
        nums[j] = temp; 
    } 
} 

這樣我們就避免掉了已經有序的情況下無意義的循環判斷。

時間復雜度分析

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

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

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

空間復雜度分析

因為冒泡排序只是相鄰元素之間的交換操作，只用到了常量級的額外空間，所以空間復雜度為 O(1)

穩定性分析

那么冒泡排序是穩定的嗎?當然是穩定的，我們代碼中，當 nums[j] > nums[j + 1] 時，才會進行交換，相等時不會交換，相等元素的相對位置沒有改變，所以冒泡排序是穩定的。

簡單選擇排序(Simple Selection Sort)

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

例如上圖，綠色代表已經排序的元素，紅色代表未排序的元素。我們當前指針指向 4 ，則我們遍歷紅色元素，從中找到最小值，然后與 4 交換。我們發現選擇排序執行完一次循環也至少可以將 1 個元素歸位。

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

注：我們為了更容易理解，min 值保存的是值，而不是索引，實際代碼中保存的是索引

簡單選擇排序代碼

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; 
    } 
} 

時間復雜度分析

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

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

空間復雜度分析

由我們的動圖可知，我們的簡單選擇排序只用到了常量級的額外空間，所以空間復雜度為 O(1)。

穩定性分析

我們思考一下，我們的簡單選擇排序是穩定的嗎?

顯然不是穩定的，因為我們需要在指針后面找到最小的值，與指針指向的值交換，見下圖。

此時我們需要從后面元素中找到最小的元素與指針指向元素交換，也就是元素 2 。但是我們交換后發現，兩個相等元素 3 的相對位置發生了改變，所以簡單選擇排序是不穩定的排序算法。

本文轉載自微信公眾號「袁廚的算法小屋」，可以通過以下二維碼關注。轉載本文請聯系袁廚的算法小屋公眾號。