優點:既適用於順序表，也適用於單鏈表，對表中元素的順序沒有要求，給插入帶來了方便，只需插入表尾即可。
缺點:速度慢。
改進:在表的末尾設置壹個哨兵，這樣就不需要循環判斷數組下標是否越界了，因為最後會建立。
適用條件:
二分搜索法決策樹不僅是壹棵二叉排序樹，而且是壹棵理想的平衡樹。時間復雜度為O（lbn）。
循環實現
遞歸實現
要排序的元素需要實現Java的Comparable接口，該接口有壹個compareTo（）方法，可以用來判斷兩個元素之間的大小關系。
從數組中選擇最小的元素，並將其與數組的第壹個元素交換。然後從數組的剩余元素中選擇最小的元素，並與數組的第二個元素交換。繼續這樣做，直到整個數組排序完畢。
選擇排序需要~N2/2次比較和~N次交換，其運行時間與輸入= =無關，這使得它需要對已排序的數組進行如此多的比較和交換操作。
從左到右以相反的順序不斷交換相鄰元素，循環壹輪後，最大的無序元素可以向右浮動。
在壹個循環中，如果沒有交換，那麽數組已經是有序的，此時可以直接退出。
每次都將當前元素插入到左側已排序的數組中，這樣左側的數組在插入後仍然是有序的。
對於數組{3，5，2，4，1}，它的順序相反:（3，2），（3，1），（5，2），（5，4），（5，1），（2，668+0）。
= =插入排序的時間復雜度取決於數組的初始順序。如果數組已經是部分有序的，那麽逆序更少，交換次數更少，時間復雜度更低= =。
對於大規模數組，插入排序非常慢，因為它只能交換相鄰元素，並且壹次只能將逆序的數量減少1。希爾排序似乎解決了插入排序的這壹限制。通過交換不相鄰的元素，它可以壹次減少超過1的反向訂單數。
Hill排序使用插入排序對間隔為H的序列進行排序。通過連續減小H直到h=1，可以對整個數組進行排序。
希爾排序的運行時間達不到平方級，遞增序列希爾排序所需的比較次數1，4，13，40，...不會超過n乘以遞增序列長度的數倍。後面介紹的高級排序算法的速度只有Bisir排序的兩倍左右。
合並排序的思想是將數組分成兩部分，分別進行排序，然後合並。
merge方法將數組的兩個排序部分合並為壹個。
將壹個大數組分成兩個小數組求解。
由於該問題每次都被分成兩半個子問題，因此該算法的復雜度壹般為O（NlogN）。
首先合並這些微陣列，然後成對合並它們以獲得微陣列。
取a【l】作為分段元素，然後從數組的左端向右掃描，直到找到大於或等於它的第壹個元素，然後從數組的右端向左掃描，找到小於它的第壹個元素，並交換這兩個元素。如果我們繼續這個過程，我們可以確保左指針I的左元素不大於分割元素，右指針J的右元素不小於分割元素。當兩個指針相遇時，拆分元素a【l】和a【j】將被交換。
快速排序是就地排序，不需要輔助數組，但是遞歸調用需要輔助棧。
快速排序的最佳情況是每次將數組精確地分成兩半，這樣遞歸調用的次數最少。在這種情況下，比較次數為CN=2CN/2+N，復雜度為O（NlogN）。
在最壞的情況下，第壹次從最小的元素開始，第二次從第二小的元素開始，依此類推。因此，有必要在最壞的情況下比較N2/2。為了防止數組從壹開始就是有序的，在快速排序時需要隨機打亂數組。
因為快速排序也會在小數組中遞歸調用自身，所以對於小數組來說，插入排序比快速排序具有更好的性能，因此可以在小數組中切換到插入排序。
在最好的情況下，每次都可以將數組的中位數作為分割元素，但計算中位數的成本非常高。壹種折衷的方法是取三個元素，並將中等大小的元素用作分段元素。
對於具有大量重復元素的數組，可以將數組分為三部分，分別對應於小於、等於和大於分段元素。
三路分割快速排序對於具有大量重復元素的隨機數組，可以在線性時間內完成排序。
快速排序的partition（）方法將返回壹個整數J..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。
對於堆排序，復雜性為NlogN，因為需要下沈N個節點。
堆排序是壹種原位排序，不使用額外的空間。
現代操作系統很少使用堆排序，因為它不能使用局部性原則進行緩存，即數組元素很少與相鄰元素進行比較和交換。
計數排序的核心是將輸入的數據值轉換為鍵並存儲在額外的數組空間中。作為壹種線性時間復雜度的排序，= =計數排序要求輸入數據必須是壹定範圍內的整數= =。
當輸入元素為0到k之間的n個整數時，其= =運行時間為O（n+k）= =。計數排序不是比較排序，排序速度比任何比較排序算法都快。由於用於計數的數組C的長度取決於要排序的數組中數據的範圍（等於要排序的數組的最大值和最小值之差加上1），因此對於數據範圍較大的數組，計數排序需要大量的時間和內存。它更適合於排序= =數組的小規模非負整數數組= =。
桶排序是計數排序的升級版本。它利用函數的映射關系，效率的關鍵在於這個映射函數的確定。為了提高桶排序的效率，我們需要做兩件事:
同時，對於桶中元素的排序，選擇哪種比較排序算法對性能有影響非常重要。
輸入數據均勻分布到每個存儲桶時速度最快，全部分布到同壹個存儲桶時速度最慢。
實際復雜度N*K
快速排序是最快的通用排序算法，它在內部循環中的指令很少，並且它還可以使用緩存，因為它總是按順序訪問數據。其運行時間約為~cNlogN，其中c小於其他線性對數排序算法。
使用三路分割快速排序，實際應用中可能出現的壹些分布式輸入可以達到線性水平，而其他排序算法仍然需要線性對數時間。