排序，也稱為排序算法，可以說是我們學習算法的過程中遇到的第一個門檻，也是實際應用中使用得較為頻繁的算法，我將自己對所學的排序算法進行一個歸納總結與分享，如有錯誤，歡迎指正！

(一)排序的分類

排序算法主要分為內部排序與外部排序，當數據量大時，數據無法全部加載到內存中，因此需要接抓外部存儲(文件、磁盤等)進行排序。而內部排序則是指將要處理的所有數據加載到內部存儲器中，并在內存中就完成排序。

本文針對的為內部排序。

(二)內部排序

2 交換排序

之前介紹了選擇排序，而選擇排序之所以叫選擇排序就是因為是選擇指定的元素放在指定的位置上。而這里我們介紹的交換排序自然就是通過交換元素來完成排序了(不是說其他排序方法不使用交換，而是核心思想是否是交換)。

本次介紹的兩種交換排序算法，一種是學習排序第一步都會學的冒泡排序算法，另一種則是應用得比較多的快速排序算法。

2.1 冒泡排序(Bubble Sort)

冒泡排序(Bubble Sort)，這是一個非常有意思的名字。我們看到這個名字不妨去想一下：

又一個大水缸，我們往水缸底部注射泡泡，泡泡就會一直往上冒。而冒泡排序就是越小的元素會經過不斷交換，慢慢“冒”到數列的前端。

而冒泡排序是排序辦法中的一種“笨”辦法，之所以它“笨”，就是因為他在每一輪中都要將每兩個相鄰元素兩兩比較，逐步地將小的元素往數組前面“冒”，將較大的元素逐步往后“沉”。

不難想到，第n輪的比較交換結束后，倒數第n個元素就是排列好，有序的了。舉第一輪的例子來說，當第一個和第二個元素相比較交換后，后者的元素是前兩個元素里的最大值，那么第二個元素和第三個元素相比較交換后，第三個元素就是前三個元素里的最大值，那么一直比較交換到最后一個元素的時候，最后一個元素就是整個數組的最大值了。

那么我們可以借助這個特性，使得第二輪只排序交換第一個到第 n - 1 個元素，第三輪只排序交換第一個到第 n - 2 個元素，依此類推下去，最后一輪只需要排序第一個元素，也就是排序完成。

那么我們一共需要比較多少輪呢？由于我們不知道原數組的情況，最保險的做法是排序的輪數等于數組的元素數量減一，這樣才能保證數組的每個元素都在應在的位置上，即是有序的。

但是假如我們實際上并不需要排列那么多次呢？舉一個極端的例子，就是數組本身就是有序的，那么我們的比較就顯得很多余了，這時我們可以做一個小小的優化，就是設定一個標志，標志本輪排序是否發生了交換，如果沒有發生交換則說明數組已經有序，就可以中斷排列了。

下面上張圖來說明這個過程：橙色是排列好的有序數組段，圖源網絡

由于冒泡排序算法實在是入門級的排序算法，下面就不多贅述了，直接上代碼：

冒泡排序是一個時間復雜度為O(n2)的穩定的算法，不管是否需要交換，都需要經過兩兩的比較。經過優化過的冒泡排序的最好情況是數組本身就是順序的，最壞情況是數組逆序的(但是直接寫個逆序就好了啊，為啥要用冒泡排序)。冒泡排序實際上應用得較少，但是是排序算法中最為基礎的一種，還是需要理解和掌握的。

看起來交換排序很“笨”，但實際上并不是，接下來介紹的另一種交換排序方法卻很快，應用得也十分頻繁，那就是快速排序算法，也稱為“快排”。

2.2 快速排序(Quick Sort)

快速排序，名字簡單粗暴，而它之所以叫這個名字的原因就是因為其特性：快。

快速排序是冒泡排序的改進，冒泡排序的比較是比較“笨”的方法，要將一一去將兩個相鄰的元素比較。但快速排序的比較就十分的聰明了，這里會用到兩個重要的思想，分而治之(Divide and conquer)和遞歸(recursive)的思想。

我們都學過二分法，對一個數組采用二分法一直分下去分到最底層就只剩一個或者兩個元素，而對一個或兩個元素的操作是很輕松的。那么我們想要排序一個數組，可以將一個數組利用一個數作為基準值(pivot)去分成兩段，使得左邊一段的數全比這個數小，右邊一段的數全比這個數大，然后再分別將左邊與右邊再一次按照這種規則分段，一直到分最底層并將其排序。

這就是快速排序的思想，我們用一個實際生活中的例子來說明：

有十個高矮不一的男同學，現在需要我們去給他們從低個到高個排隊。我們沒辦法去知道這十個同學身高的中值，于是我們隨便挑了一個男同學作為基準(pivot)，將比他個子低的男同學排到他的左邊，將比他個子高的男同學排在他的右邊(這個過程稱為分區partition)，這樣這個作為pivot的男同學位置就排好了。

那么我們再分別在比他個子低的男同學里再隨便找一個男同學作為基準(pivot),按照第一輪的方式排隊，不難發現，作為基準的每個同學的位置都能排好，一直到作為我們第一個基準的男同學的左邊的每一個同學的位置都排好為止。右邊也同理。

當最后一個作為基準的同學隊排完的時候，整個隊列就排好了。而我們不斷在分段中找基準的過程，就是遞歸。

快速排列的思想就是這樣子了，并不算很難理解，快速排列借助的就是分而治之和遞歸的思想去完成的，但是在程序中應該如何實現呢？選擇基準由于是隨機的，很容易實現，但是快速排序的最大難點在于怎么將基準左右兩端的元素正確的放在兩端(也就是怎么實現分區)。

分區(partition)的實現思路

實現分區的原理就是不斷將比基準值小的元素放在前面，比基準值大的數放在后面。

分區的實現方法有很多，這里我只介紹我常用的兩種實現思路。

思路一：用一個數組實例來說明：

10，8，22，34，5，12，28，21，11

先選定第一個元素10作為pivot,相當于將10移除出數組作為基準值，然后在剩下的數組里找到比10小的元素就往前面放，比如先找到8，就將8放到10之后的第一位，在找到5放在10之后的第二位。當整個數組遍歷完畢，將所有的比10小的數都盡可能往前放后：

10，8，5，34，22，12，28，21，11

此時我們在將基準值10與最后一個比10小的數交換：

5，8，10，34，22，12，28，21，11

這樣以10為基準的分區就完成了，接下來就是向10的左邊和右邊分別遞歸的過程了。

思路二：用同樣的一個數組實例來說明：

10，8，22，34，5，12，28，21，11

先選定第一個元素 10 作為pivot,那么我們就從第二個元素開始查找比10大的元素，一直查找到第三個元素22的時候，將22標記，然后在從第四個元素開始找比10小的元素，一直查找到第五個元素5，然后將22和5的位置交換。

10，8，5，34，22，12，28，21，11

再從5開始移動標記，移動到34，發現也比10大，標記34，再開始從22向后查找，查找到最后也沒有比10大的數了，這時將基準值10放在標記的34的位置，這樣第一輪的分區就完成了。接下來的就是向10的左邊和10的右邊分別遞歸分區過程。

在這查找比基準大的值的過程中，如果沒有發現比基準值大的值，說明這個值就是在這個遞歸中的最大值，只需要將第一位和最后一位交換位置即可。

該思路坑太多，慎入！！！

再上一張圖來說明整個排序過程：黃色為基準值pivot，橙色為已排列，圖源網絡

下面上根據思路一實現快速排序的代碼：

思路二的代碼我寫了六十多行才實現，有想法的小伙伴可以嘗試一下(如果三四十行實現了請務必要私信我)，基準值的選取也可以不選擇第一個，隨機選擇其他的值也是可行的(但是一定要找到結束分區的條件)，快排的寫法非常的多，大家也可以多試試其他的思路。

我們在開始介紹快速排序的時候，就提到快速排序的特點就是速度快。

快速排序的平均時間復雜度是O(nlogn)，最壞情況達到O(n2)(順序數列的快排，每次都會比較，實際上跟冒泡排序基本沒有區別)，那就有人問了，時間復雜度達到O(n2)的算法怎么能算快呢？但是實際上快速排序很少會出現最壞情況，在處理數據的時候一般都是O(nlogn)，而且快排之所以快，是因為它在大多數情況會比其他O(nlogn)時間復雜度的算法表現的要更好。

因為快速排序的O(nlogn)中的隱含的常數因子通常很小，比復雜度穩定為O(nlogn)的歸并排序要小很多，所以在遇到順序性較弱的隨機數列來說，它的性能通常要比歸并排序要優秀很多。

最后總結一下，快速排序是冒泡排序算法的改進，本質上是在利用了分治思想的冒泡排序算法。冒泡算法是兩兩比較小的往前“冒”，大的往后“沉”；而快速排序則就是與基準值(pivot)比較小的往前“冒，”大的往后“沉”。

快速排序還有一個重點：分區?；旧险莆樟朔謪^(partition)，就掌握了快速排序。

總結

以上是生活随笔為你收集整理的交换排序图解_排序算法学习分享（二）交换排序---冒泡排序与快速排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。