㈠ 常見排序演算法歸納
排序演算法一般分類：
比較兩個相鄰的元素，將值大的元素交換至右端。
依次比較兩個相鄰的數，將小數放到前面，大數放到後面
即在第一趟：首先比較第1個數和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此一直繼續下去，直到比較最後兩個數，將小數放前，大數放後。然後重復第一趟步驟，直到所有排序完成。
第一趟比較完成後，最後一個數一定是數組中最大的一個數，所以第二趟比較的時候最後一個數不參與比較。
第二趟完成後，倒數第二個數也一定是數組中第二大的數，所以第三趟比較的時候最後兩個數不參與比較。
依次類推......
輸出結果：
冒泡排序的優點： 每進行一趟排序，就會少比較一次，因為每進行一趟排序都會找出一個較大值。如上例：第一趟比較之後，排在最後的一個數一定是最大的一個數，第二趟排序的時候，只需要比較除了最後一個數以外的其他的數，同樣也能找出一個最大的數排在參與第二趟比較的數後面，第三趟比較的時候，只需要比較除了最後兩個數以外的其他的數，以此類推……也就是說，沒進行一趟比較，每一趟少比較一次，一定程度上減少了演算法的量。
用時間復雜度來說：
從一個數組中隨機選出一個數N，通過一趟排序將數組分割成三個部分，1、小於N的區域 2、等於N的區域 3、大於N的區域，然後再按照此方法對小於區的和大於區分別遞歸進行，從而達到整個數據變成有序數組。
如下圖：
假設最開始的基準數據為數組的第一個元素23，則首先用一個臨時變數去存儲基準數據，即 tmp=23 ，然後分別從數組的兩端掃描數組，設兩個指示標志： low 指向起始位置， high 指向末尾。
首先從後半部分開始，如果 掃描到的值大於基準數據 就讓 high-1 ，如果發現有元素比該基準數據的值小，比如上面的 18 <= tmp ，就讓 high位置的值賦值給low位置 ，結果如下：
然後開始從前往後掃描，如果掃描到的值小於基準數據就讓 low+1 ，如果發現有元素大於基準數據的值，比如上圖 46 >= tmp ，就再將 low 位置的值賦值給 high 位置的值，指針移動並且數據交換後的結果如下：
然後再開始從前往後遍歷，直到 low=high 結束循環，此時low或者high的下標就是 基準數據23在該數組中的正確索引位置 ，如下圖所示：
這樣一遍遍的走下來，可以很清楚的知道，快排的本質就是把比基準數據小的都放到基準數的左邊，比基準數大的數都放到基準數的右邊，這樣就找到了該數據在數組中的正確位置。
然後採用遞歸的方式分別對前半部分和後半部分排序，最終結果就是自然有序的了。
輸出結果：
最好情況下快排每次能恰好均分序列，那麼時間復雜度就是O(nlogn)，最壞情況下，快排每次劃分都只能將序列分為一個元素和其它元素兩部分，這時候的快排退化成冒泡排序，時間復雜度為O(n^2)。
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。
將一個數據插入到 已經排好序的有序數據 中
第一趟排序：
用數組的第二個數與第一個數( 看成是已有序的數據 )比較
第二趟排序：
用數組的第三個數與已是有序的數據 {2,3} (剛才在第一趟排的)比較
在第二步中：
...
後面依此類推
輸出結果：
選擇排序是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。
舉例：數組 int[] arr={5,2,8,4,9,1}
第一趟排序 ： 原始數據： 5 2 8 4 9 1
最小數據1，把1放在首位，也就是1和5互換位置，
排序結果： 1 2 8 4 9 5
第二趟排序 ：
第1以外的數據 {2 8 4 9 5} 進行比較，2最小，
排序結果： 1 2 8 4 9 5
第三趟排序 ：
除 1、2 以外的數據 {8 4 9 5} 進行比較，4最小，8和4交換
排序結果： 1 2 4 8 9 5
第四趟排序 :
除第 1、2、4 以外的其他數據 {8 9 5} 進行比較，5最小，8和5交換
排序結果： 1 2 4 5 9 8
第五趟排序：
除第 1、2、4、5 以外的其他數據 {9 8} 進行比較，8最小，8和9交換
排序結果： 1 2 4 5 8 9
輸出結果：
歸並排序（merge sort）是利用歸並的思想實現的排序方法，該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。
比如我們對 [8,4,5,7,1,3,6,2] 這個數組進行歸並排序，我們首先利用分治思想的「分」將數組拆分。
輸出結果：
㈡ 常見查找和排序演算法
查找成功最多要n 次，平均（n+1）/2次， 時間復雜度為O(n) 。
優點：既適用順序表也適用單鏈表，同時對表中元素順序無要求，給插入帶來方便，只需插入表尾即可。
缺點：速度較慢。
改進：在表尾設置一個崗哨，這樣不用去循環判斷數組下標是否越界，因為最後必然成立。
適用條件：
二分查找的判定樹不僅是二叉排序樹，而且是一棵理想平衡樹。 時間復雜度為O(lbn) 。
循環實現
遞歸實現
待排序的元素需要實現 Java 的 Comparable 介面，該介面有 compareTo() 方法，可以用它來判斷兩個元素的大小關系。
從數組中選擇最小元素，將它與數組的第一個元素交換位置。再從數組剩下的元素中選擇出最小的元素，將它與數組的第二個元素交換位置。不斷進行這樣的操作，直到將整個數組排序。
選擇排序需要 ~N2/2 次比較和 ~N 次交換，==它的運行時間與輸入無關==，這個特點使得它對一個已經排序的數組也需要這么多的比較和交換操作。
從左到右不斷 交換相鄰逆序的元素 ，在一輪的循環之後，可以讓未排序的最大元素上浮到右側。
在一輪循環中，如果沒有發生交換，那麼說明數組已經是有序的，此時可以直接退出。
每次都 將當前元素插入到左側已經排序的數組中 ，使得插入之後左側數組依然有序。
對於數組 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交換相鄰元素，令逆序數量減少 1，因此插入排序需要交換的次數為逆序數量。
==插入排序的時間復雜度取決於數組的初始順序，如果數組已經部分有序了，那麼逆序較少，需要的交換次數也就較少，時間復雜度較低==。
對於大規模的數組，插入排序很慢，因為它只能交換相鄰的元素，每次只能將逆序數量減少 1。希爾排序的出現就是為了解決插入排序的這種局限性，它通過交換不相鄰的元素，每次可以將逆序數量減少大於 1。
希爾排序使用插入排序對間隔 h 的序列進行排序。通過不斷減小 h，最後令 h=1，就可以使得整個數組是有序的。
希爾排序的運行時間達不到平方級別，使用遞增序列 1, 4, 13, 40, ... 的希爾排序所需要的比較次數不會超過 N 的若干倍乘於遞增序列的長度。後面介紹的高級排序演算法只會比希爾排序快兩倍左右。
歸並排序的思想是將數組分成兩部分，分別進行排序，然後歸並起來。
歸並方法將數組中兩個已經排序的部分歸並成一個。
將一個大數組分成兩個小數組去求解。
因為每次都將問題對半分成兩個子問題，這種對半分的演算法復雜度一般為 O(NlogN)。
先歸並那些微型數組，然後成對歸並得到的微型數組。
取 a[l] 作為切分元素，然後從數組的左端向右掃描直到找到第一個大於等於它的元素，再從數組的右端向左掃描找到第一個小於它的元素，交換這兩個元素。不斷進行這個過程，就可以保證左指針 i 的左側元素都不大於切分元素，右指針 j 的右側元素都不小於切分元素。當兩個指針相遇時，將切分元素 a[l] 和 a[j] 交換位置。
快速排序是原地排序，不需要輔助數組，但是遞歸調用需要輔助棧。
快速排序最好的情況下是每次都正好將數組對半分，這樣遞歸調用次數才是最少的。這種情況下比較次數為 CN=2CN/2+N，復雜度為 O(NlogN)。
最壞的情況下，第一次從最小的元素切分，第二次從第二小的元素切分，如此這般。因此最壞的情況下需要比較 N2/2。為了防止數組最開始就是有序的，在進行快速排序時需要隨機打亂數組。
因為快速排序在小數組中也會遞歸調用自己，對於小數組，插入排序比快速排序的性能更好，因此在小數組中可以切換到插入排序。
最好的情況下是每次都能取數組的中位數作為切分元素，但是計算中位數的代價很高。一種折中方法是取 3 個元素，並將大小居中的元素作為切分元素。
對於有大量重復元素的數組，可以將數組切分為三部分，分別對應小於、等於和大於切分元素。
三向切分快速排序對於有大量重復元素的隨機數組可以在線性時間內完成排序。
快速排序的 partition() 方法，會返回一個整數 j 使得 a[l..j-1] 小於等於 a[j]，且 a[j+1..h] 大於等於 a[j]，此時 a[j] 就是數組的第 j 大元素。
可以利用這個特性找出數組的第 k 大的元素。
該演算法是線性級別的，假設每次能將數組二分，那麼比較的總次數為 (N+N/2+N/4+..)，直到找到第 k 個元素，這個和顯然小於 2N。
堆中某個節點的值總是大於等於其子節點的值，並且堆是一顆完全二叉樹。
堆可以用數組來表示，這是因為堆是完全二叉樹，而完全二叉樹很容易就存儲在數組中。位置 k 的節點的父節點位置為 k/2，而它的兩個子節點的位置分別為 2k 和 2k+1。這里不使用數組索引為 0 的位置，是為了更清晰地描述節點的位置關系。
在堆中，當一個節點比父節點大，那麼需要交換這個兩個節點。交換後還可能比它新的父節點大，因此需要不斷地進行比較和交換操作，把這種操作稱為上浮。
類似地，當一個節點比子節點來得小，也需要不斷地向下進行比較和交換操作，把這種操作稱為下沉。一個節點如果有兩個子節點，應當與兩個子節點中最大那個節點進行交換。
將新元素放到數組末尾，然後上浮到合適的位置。
從數組頂端刪除最大的元素，並將數組的最後一個元素放到頂端，並讓這個元素下沉到合適的位置。
把最大元素和當前堆中數組的最後一個元素交換位置，並且不刪除它，那麼就可以得到一個從尾到頭的遞減序列，從正向來看就是一個遞增序列，這就是堆排序。
一個堆的高度為logN，因此在堆中插入元素和刪除最大元素的復雜度都為 logN。
對於堆排序，由於要對 N 個節點進行下沉操作，因此復雜度為 NlogN。
堆排序是一種原地排序，沒有利用額外的空間。
現代操作系統很少使用堆排序，因為它無法利用局部性原理進行緩存，也就是數組元素很少和相鄰的元素進行比較和交換。
計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，==計數排序要求輸入的數據必須是有確定范圍的整數==。
當輸入的元素是 n 個 0 到 k 之間的整數時，它的==運行時間是 O(n + k)==。計數排序不是比較排序，排序的速度快於任何比較排序演算法。由於用來計數的數組C的長度取決於待排序數組中數據的范圍（等於待排序數組的最大值與最小值的差加上1），這使得計數排序對於數據范圍很大的數組，需要大量時間和內存。比較適合用來排序==小范圍非負整數數組的數組==。
桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在於這個映射函數的確定。為了使桶排序更加高效，我們需要做到這兩點：
同時，對於桶中元素的排序，選擇何種比較排序演算法對於性能的影響至關重要。
當輸入數據均勻分配到每一個桶時最快，當都分配到同一個桶時最慢。
實間復雜度N*K
快速排序是最快的通用排序演算法，它的內循環的指令很少，而且它還能利用緩存，因為它總是順序地訪問數據。它的運行時間近似為 ~cNlogN，這里的 c 比其它線性對數級別的排序演算法都要小。
使用三向切分快速排序，實際應用中可能出現的某些分布的輸入能夠達到線性級別，而其它排序演算法仍然需要線性對數時間。
㈢ O（n2）排序演算法的總結
最近在慕課網上學習了O（n2）時間復雜度的相關演算法，總算是對這些演算法的優缺點有了詳細的特點。其實對於任何的演算法，沒有優點和缺點，而是有相應的特點。所以我們應該結合不同的排序環境來選擇不同的排序演算法，從而達到在實現時間和執行效率上的平衡。這是因為，越是簡單的排序演算法，實現起來肯定是越容易，而且出現BUG的概率也不會太大。相反，復雜演算法可能效率更高，但是出現問題的可能性也會更大。下面，我就結合O（n2）時間復雜度的四個經典排序演算法，為您詳細講解這四個演算法的特點。
定義：選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。
圖示說明：
源碼實現：
分析：通過選擇排序的圖示和源碼我們可以看出來，選擇排序要進行兩次循環，而且最關鍵的是內層循環在每一次執行時都是全部執行完的。那我們有沒有辦法讓內層循環不用每次都執行完呢？方法肯定是有的，這就是冒泡排序。
定義：冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。它重復地走訪過要排序的元素列，一次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素已經排序完成。
圖示說明：
源碼實現：
分析：從圖示和源碼可以看出來，從執行次數上來說，冒泡排序是比選擇排序的循環次數更少的。那是不是就可以說，如果待排序的數組中元素比較合適，冒泡排序在時間復雜度上是不是會比選擇排序更好呢？真的是這樣的嗎？
其實不是的，經過多次測試驗證，冒泡排序基本上是比選擇排序的時間復雜度要差的，這是為什麼呢？從源碼中我們可以很明顯的看出來，雖然冒泡排序是比選擇排序執行次數少了，但是交換的次數明顯增多了，而如果你對計算機程序指令的實現原理只要有一個基本的認識，就應該知道交換動作比賦值動作是需要更多指令操作的。所以說，最終冒泡排序大部分情況下，比選擇排序的時間復雜度都要高。
既然交換動作這么消耗資源，那有沒有一種方法，即能夠減少內層循環的執行次數，又可以減少甚至是無需交換操作呢？這就要請出插入排序了。
定義：插入排序（Insertion Sort）的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，即每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。
圖示說明：
源碼實現：
分析：從圖示和源碼可以看出來，插入排序（優化後的）是沒有交換操作的，而且對於內層循環來說，如果待排序的元素是比較大的值，那內層循環執行的次數會非常的少。因此，如果原始數據基本上是有序的，那使用插入排序的效率會非常的高。在O（n2）級別的排序演算法還可以再優化嗎？如果可以從哪裡優化呢？下面我們來介紹希爾排序，正是這個排序演算法的提出，使得排序演算法打破了O（n2）時間復雜度的禁錮。
定義：希爾排序(Shell's Sort)是插入排序的一種又稱「縮小增量排序」（Diminishing Increment Sort），是直接插入排序演算法的一種更高效的改進版本。該演算法的基本思想是：把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，排序演算法便終止。
對於希爾排序來說，最關鍵的就是增量該如何選取。這個增量該怎麼確定，這還真是個數學難題，至今沒有解答。但是通過大量的實驗，還是有個經驗值的。我們的例子給出的增量選取公式是：h = 3 * h + 1，下面請看圖示說明。
圖示說明：
源碼實現：
分析：從插入排序中我們知道，插入排在待排序數組基本有序時，插入排序的演算法效率會非常高，所以我們可以這樣認為，希爾排序的最終思想就是：先將整個待排記錄序列分割成為若乾子序列分別進行直接插入排序，待整個序列中的記錄「基本有序」時，在對全體進行一次直接插入排序。
而希爾排序的效率之所以很高，就是因為這個基本思想確實很有用：即當h值大的時候，數據項每一趟排序需要移動元素的個數很少，但數據項移動的距離很長。這是非常有效率的。而當h減小時，每一趟排序需要移動的元素的個數增多，但是此時數據項已經接近於它們排序後最終的位置，這對於插入排序可以更有效率。正是這兩種情況的結合才使希爾排序效率那麼高。
對於增量的選取，可以稱得上是一種魔法。在希爾的原稿中，他建議初始的間距為N/2，簡單地把每一趟排序分成了兩半。但是，這被證明並不是最好的數列。盡管對於大多數的數據來說這個方法還是比插入排序效果好，但是這種方法有時會使運行時間降到O(N2)，這並不比插入排序的效率更高。間隔序列中的數字互質通常被認為很重要：也就是說，除了1之外它們沒有公約數。這個約束條件使每一趟排序更有可能保持前一趟排序已排好的效果。希爾最初以N/2為間隔的低效性就是歸咎於它沒有遵守這個准則。
總結：上面就是四種經典O（n2）級別排序演算法的相關說明。其實在各種場合下選擇排序和冒泡排序基本上是不會使用的，因為使用場景基本沒有。而對於插入排序和希爾排序來說，在待排序數據基本有序的情況下，使用場景還是有的，比如一些日誌文件中存儲的日誌，可能大部分的日誌記錄都是基於時間排序，只是在某些極端情況下導致一些日誌晚存儲了導致時間不一致。
我是徐建航， 這是我寫的第31篇文章，歡迎你加入007社群，七天寫一篇，一起寫七年，七年之後一起去南極。