最經(jīng)典最常用的排序算法有：冒泡排序、插入排序、選擇排序、歸并排序、快速排序、計數(shù)排序、基數(shù)排序和桶排序。這些排序算法可以按照時間復雜度分為三類：
- O(n^2)——冒泡、插入、選擇
- O(nlogn)——快速、歸并
- O(n)——計數(shù)、基數(shù)、桶
一、衡量排序算法的指標
1.1 算法的執(zhí)行效率
- 最好、最壞和平均情況下的時間復雜度；
- 原始數(shù)據(jù)的雜亂程度會導致同一種算法在不同情況下的時間復雜度呈現(xiàn)不同量級的差異，所以在選擇排序算法的時候，需要給出這三個指標，結(jié)合實際業(yè)務情況的原始數(shù)據(jù)，來選擇算法。
- 時間復雜度的系數(shù)、常數(shù)和低階；
- 不同的排序算法可能會出現(xiàn)算法復雜度處在同一量級的情況，此時就需要根據(jù)時間復雜度的系數(shù)、常數(shù)和低階來決定使用哪一種算法。
- 算法的比較次數(shù)和移動次數(shù)；
- 比較次數(shù)和移動次數(shù)會分別導致CPU和IO操作，所以也需要納入到選擇排序算法的指標中來。
1.2 算法的內(nèi)存消耗
- 原地排序，是指空間復雜度為O(1)的排序算法，不需要借助很多外部存儲空間就能完成排序；
- 非原地排序，需要借助外部存儲空間才能完成排序；
1.3 算法的排序穩(wěn)定性
- 穩(wěn)定，原始數(shù)據(jù)中相等的元素在排序后它們之間的順序不發(fā)生改變；
- 非穩(wěn)定，原始數(shù)據(jù)中相等的元素在排序后它們之間的順序有可能發(fā)生改變；
二、O(n^2)的排序算法
2.1 冒泡排序
冒泡排序每次只會比較相鄰的兩個元素，只有在不滿足要求的大小關(guān)系情況下，才會發(fā)生交換行為。一次冒泡迭代會讓至少一個元素移動到它最終應該在的位置上，最多n次冒泡迭代，當某次冒泡迭代沒有發(fā)生元素的交換行為，就可以判定數(shù)列已經(jīng)完成了排序。
比如我們需要對如下數(shù)列進行從小到大的排列：
冒泡排序過程示意圖
對應的實現(xiàn)代碼如下：
public static void main(String[] args) {
int[] data = {4,5,6,3,2,1};
int size = 6;
log.info("原始數(shù)列為：{}",data);
bubbleSort(data,size);
log.info("冒泡排序后的結(jié)果為：{}",data);
}
public static void bubbleSort(int[] data, int n){
if(n <= 1){
log.info("數(shù)組中元素少于2個，無需進行排序！");
return;
}
// 最多需要迭代n次冒泡
for(int i=0;i<n;i++){
// 表示當前迭代冒泡中是否發(fā)生了元素交換
boolean switchFlag = false;
for(int j=0;j<n-i-1;j++){
if(data[j] > data[j+1]){
// 不滿足從小到大的關(guān)系，需要交換
int temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
switchFlag = true;
}
}
// 當前冒泡迭代中沒有發(fā)生元素交換，說明數(shù)列已經(jīng)有序，完成了排序，可以提前結(jié)束
if(!switchFlag){
break;
}
}
}
冒泡排序沒有借助很多額外的存儲空間，因此是原地排序；
冒泡排序只有在前后兩個元素不滿足大小關(guān)系時才發(fā)生交換，因此是穩(wěn)定的排序算法；
最好情況下原始數(shù)列就是滿足要求的大小關(guān)系的，那么只需要迭代一個冒泡就完成了排序，時間復雜度為O(n)；最壞情況下原始數(shù)列正好和要求的大小關(guān)系完全相反，那么需要迭代n此冒泡，因此時間復雜度為O(n^2)。
2.2 插入排序
插入排序?qū)⒄麄€數(shù)列劃分為已排序和未排序兩個區(qū)間，初始情況下，已排序區(qū)間只有一個元素，那就是數(shù)列的第一個元素，然后重復取未排序區(qū)間中的元素逐個插入到已排序區(qū)間中，直至未排序區(qū)間元素數(shù)量為0，需要注意的是，將元素插入已排序區(qū)間會引起插入位置后方所有元素的移動。
比如，我們對如下數(shù)列進行插入排序的過程為：
插入排序過程示意圖
對應的實現(xiàn)代碼如下：
public static void main(String[] args) {
int[] data = {4,5,6,3,2,1};
int size = 6;
log.info("原始數(shù)列為：{}",data);
insertionSort(data,size);
log.info("插入排序后的結(jié)果為：{}",data);
}
public static void insertionSort(int data[], int n){
if(n <= 1){
log.info("數(shù)組中元素少于2個，無需進行排序！");
return;
}
// 從未排序區(qū)間開始遍歷
for(int i=1;i<n;i++){
// 放到臨時空間保存，因為后續(xù)已排序區(qū)間元素的向后移動會覆蓋掉data[i]的值
int value = data[i];
int j=i-1;
for(;j>=0;j--){
// 已排序區(qū)間從后往前遍歷和當前需要插入的元素進行比較
if(data[j] > value){
// 當前已排序區(qū)間的元素往后移動一位
data[j+1] = data[j];
} else {
break;
}
}
// 插入到已排序區(qū)間中小于等于自己元素的后面，保證排序算法的穩(wěn)定性
data[j+1] = value;
}
}
插入排序沒有借助很多額外的存儲空間，因此是原地排序；
插入排序可以在算法中約定，將未排序區(qū)間的元素插入到排序區(qū)間相同元素的后方，因此也是穩(wěn)定的排序算法；
最好情況下原始數(shù)列就是滿足要求的大小關(guān)系的，那么只需要迭代一遍數(shù)列就完成了排序，時間復雜度為O(n)；最壞情況下，每將一個元素插入已排序區(qū)間，都會引起所有已排序區(qū)間元素的向后移動，那么時間復雜度就是O(n^2)。
2.3 選擇排序
選擇排序也是將整個數(shù)列分為已排序區(qū)間和未排序區(qū)間，和插入排序的區(qū)別是，每次迭代都是從未排序區(qū)間中尋找到最小值，然后將其和未排序區(qū)間中的第一個元素進行交換，直至未排序區(qū)間元素為空。
選擇排序過程示意圖
選擇排序也是原地排序；
選擇排序是不穩(wěn)定的，在交換元素的時候，極有可能改變相同元素的前后順序，比如：
1，2，| 5，4，5，3
此時未排序區(qū)間最小元素為3，會和未排序區(qū)間第一個元素5進行交換：
1，2，3，| 4，5，5
此時，未排序區(qū)間的兩個5實際上已經(jīng)發(fā)生了順序上的變化，在排序完成后，它們也極有可能是維持現(xiàn)在變化了的順序的。
最好情況和最壞情況下的時間復雜度都是O(n2)，無論最好還是最壞，每次迭代都要從未排序區(qū)間中找到最小值，每次找最小值的時間復雜度為O(n)，所以無論哪種情況，選擇排序的時間復雜度都是O(n2)。
2.4 小結(jié)
冒泡排序和插入排序雖然時間復雜度在同一量級，并且都是穩(wěn)定的、原地排序算法，但是通常來說，插入排序的性能要優(yōu)于冒泡排序。因為插入排序的交換次數(shù)和賦值次數(shù)更少，在大數(shù)據(jù)量數(shù)列排序時，效果尤為明顯。
插入排序還存在優(yōu)化的空間，在大數(shù)據(jù)量和比較無序的情況下使用希爾排序能很好地提升排序性能，希爾排序的核心思想是對數(shù)列按照增量序列進行邏輯分組，對分組的數(shù)列使用插入排序，保證基本有序，然后逐步減小增量序列，迭代進行插入排序。
希爾排序的時間復雜度視增量序列值的不同而不同，最壞情況是O(n^2)，并且不是穩(wěn)定的排序算法。
總之，這三種排序算法的時間復雜度都是O(n^2)，比較適合小數(shù)據(jù)量的排序場景。
三、O(nlogn)的排序算法
3.1 快速排序
快速排序是由冒泡排序進化而來，能夠迭代更少的次數(shù)，更加快速地完成排序，因此得名。其使用了分治思想和遞歸的實現(xiàn)方式，其大致的思路如下：
- 選取最前面或者最后面的一個元素作為基準元素（我們以最前面一個元素作為基準元素為例），并在數(shù)列的頭部left和尾部right上各設置一個指針；
- 從right開始將元素和基準元素比較，如果大于等于基準元素，則right-1，如果小于基準元素，那么將right的值賦值到left所在的位置，然后切換到left，left+=1，將此時的left元素和基準元素比較，如果小于等于基準元素，則left+1，如果大于基準元素，那么將left的值賦值到right所在的位置；
- 對如上過程遞歸迭代，直至left=right，然后將它們指向的元素賦值為基準元素，此時就完成了排序；
排序過程示意圖可以參考：什么是快速排序
快速排序在排序的過程中并不會借助很多的額外存儲空間，因此屬于原地排序；
快速排序可能會改變相同元素的順序，因此是不穩(wěn)定的排序算法；
快速排序的時間復雜度是O(nlogn)，前提是每次遞歸選取的基準元素正好可以將數(shù)列分成兩個差不多的子數(shù)列，在最壞情況下，每次選取的基準元素不是最大值就是最小值的話，那么時間復雜度就會退化為O(n^2)。
3.2 歸并排序
歸并排序也是使用了分治思想和遞歸的實現(xiàn)方式，其大致的思路如下：
- 找到待排序數(shù)列的中間位置，將數(shù)列分解成前后兩個子數(shù)列；
- 使用同樣的方法迭代分解子數(shù)列，直至所有子數(shù)列都只有一個元素為止；
- 使用額外的存儲空間從下往上，開始合并相鄰子數(shù)列，直至合并為一個數(shù)列為止，即完成了排序；
分解和合并的大致示意圖如下：
歸并排序的分解合并過程
需要注意的是，在合并的過程中，算法需要借助額外的存儲空間來合并相鄰的兩個子數(shù)列，合并的過程如下：
歸并排序合并過程示意圖
遞歸的代碼示例如下：
public static void MergeSort(int[] data, int begin, int end){
if(begin >= end){
log.info("當前子數(shù)列僅有一個元素，無需再分解");
return;
}
int middle = (begin + end) / 2;
MergeSort(data,begin,middle);
MergeSort(data,middle+1,end);
Merge(data,begin,middle,end);
}
歸并排序在合并的時候需要借助很多額外的存儲空間，空間復雜度為O(n)，因此它不是原地排序算法；
歸并排序在合并的時候，我們可以通過代碼控制相同的元素保持原始數(shù)列的順序，因此是穩(wěn)定的；
歸并排序在任何情況下的時間復雜度都是O(nlogn)；
3.3 小結(jié)
快速排序和歸并排序都是比較復雜的排序算法，它們都是采用了分治思想和遞歸的實現(xiàn)方法，區(qū)別在于：
- 快速排序是自上而下地進行排序，歸并排序是先分解然后再自下而上地完成排序；
- 快速排序平均時間復雜度是O(nlogn)，但是最壞情況會退化為O(n^2)，雖然概率很小，但是歸并排序在任何情況下時間復雜度都是O(nlogn)；
- 快速排序是不穩(wěn)定的，屬于原地排序算法，歸并排序是穩(wěn)定的，屬于非原地排序算法；
- 因為歸并排序的空間復雜度是O(n)，所以相對來說，快速排序更加受歡迎，并被使用地最多；
四、O(n)的排序算法
4.1 桶排序
- 首先得出待排序數(shù)列的區(qū)間范圍，按照范圍平均分為若干個有序的桶；
- 遍歷待排序數(shù)列，將這些數(shù)據(jù)分別放到各個桶里面；
- 單個桶里面的數(shù)據(jù)可以使用快速排序進行排序；
- 將所有桶中的數(shù)據(jù)按照桶的次序合并起來就得到了最終有序的數(shù)列；
桶排序示意圖
桶排序需要借助額外的存儲空間“桶”，因此，不是原地排序算法；
桶排序是否穩(wěn)定取決于單個桶內(nèi)排序使用的算法，如果使用的快速排序，因為快排本身就不是穩(wěn)定的，因此桶排序就不是穩(wěn)定的；
桶排序的空間復雜度為O(n)，因為它需要將全部元素都放到桶中；時間復雜度也是O(n)，這個是由公式推到而來，假設n個元素被平均放到m個桶里面，那么每個桶中的元素個數(shù)為k=n/m，每個桶中排序的時間復雜度就是快速排序的時間復雜度，為O(klogk)，因為有m個桶，因此總的時間復雜度就是O(mklogk)，我們把k替換為n/m，那么時間復雜度就可以表示為O(nlog(n/m)，當桶的個數(shù)m接近元素個數(shù)n時，log(n/m)就是很小的常數(shù)可以忽略，因此時間復雜度就接近O(n)；
桶排序?qū)Υ判驍?shù)列的要求比較高，即待排序數(shù)列必須是容易被劃分為m個桶的，并且每個桶中的元素要能均勻，否則，有的桶中元素很多，有的很少，那么就會退化為O(nlogn)的時間復雜度；
桶排序比較適用于大數(shù)據(jù)量的外部排序場景中（非內(nèi)存排序），比如對10GB的訂單數(shù)據(jù)按照金額進行排序，內(nèi)存一次性加載不了這么大的數(shù)據(jù)，可以使用桶排序劃分若干個有次序的相同大小的文件，一次只把一個文件中的數(shù)據(jù)加載到內(nèi)存進行快速排序；但是訂單金額分布不一定是均勻的，有的桶中的數(shù)據(jù)比較多，會導致該桶文件也無法被一次性加載到內(nèi)存中進行排序，此時可以對該文件迭代進行桶排序，直至所有桶文件都可以被加載到內(nèi)存中為止。
4.2 計數(shù)排序
計數(shù)排序是桶排序的一種特殊情形，當待排序數(shù)列的范圍區(qū)間不是很大的時候，我們?yōu)槊恳粋€數(shù)值劃分一個桶，桶之間要有順序，然后遍歷數(shù)列，將元素放到它對應的桶中，最后再將桶按照順序合并起來就得到了有序的數(shù)列；每個桶中的元素都是相同的，因此我們省掉了桶內(nèi)快速排序的時間；
計數(shù)排序需要借助額外的存儲空間“桶”，因此，不是原地排序算法；
計數(shù)排序再將相同的元素放到同一個桶中的時候，可以設置保持它們在原始數(shù)列中順序來保證算法的穩(wěn)定性；
計數(shù)排序的空間復雜度是O(n)，時間復雜度為O(n+k)，k表示數(shù)據(jù)范圍即有多少各個桶，當數(shù)據(jù)范圍不大，可以考慮為常數(shù)，那么時間復雜度就是O(n)；
計數(shù)排序只能適用在數(shù)列范圍區(qū)間不大的場景中，比如給50萬考生的分數(shù)進行排名，分數(shù)范圍k為0~600，數(shù)據(jù)元素m為50萬，k遠遠小于m，所以適合適用計數(shù)排序；計數(shù)排序只能給非負整數(shù)進行排序，如果待排序數(shù)列不是非負整數(shù)，需要先想辦法把數(shù)列轉(zhuǎn)換為非負整數(shù)后才能使用計數(shù)排序進行排序；
4.3 基數(shù)排序
有時候待排序數(shù)列的范圍區(qū)間非常大，分布也不一定是均勻的，且數(shù)列本身位數(shù)比較多，可以考慮基數(shù)排序；基數(shù)排序是從最低位開始排序，逐步遍歷到最高位，等到最高位完成排序后，整個數(shù)列就是有序的。
有一個要求，對每一位的排序算法一定要使用穩(wěn)定的排序算法，不然高位的排序會弄亂低位已經(jīng)排好的順序，排序算法就不對了。
基數(shù)排序在每一位上會使用到線性排序算法，比如計數(shù)排序，需要使用額外的存儲空間，因此不是原地排序算法；
基數(shù)排序每一位的排序算法都是采用的穩(wěn)定的算法，因此整體上也是穩(wěn)定的；
基數(shù)排序的空間復雜度為O(1)，時間復雜度為O(kn)，當k（元素的位數(shù)）不大的時候，并且每一位的排序采用的是線性排序算法（比如計數(shù)排序，這就要求每一位上的范圍區(qū)間不是很大），那時間復雜度就是O(n)；如果每一位排序采用的不是線性排序算法，那么時間復雜度就很難保證是O(n)了。
基數(shù)排序的適用場景有給手機號、身份證號、銀行卡號排序，這些場景下，數(shù)列的范圍區(qū)間非常大，并且分布不一定均勻，不適合使用桶排序和計數(shù)排序，但是卻非常適合基數(shù)排序。
有的待排序數(shù)列不是等長的，比如單詞表序列的排序，可以把每一個單詞元素通過補0的方式補充到一樣長，再通過基數(shù)排序進行排序。
4.4 小結(jié)
這三種排序算法的時間復雜度是線性的，因此也被成為線性排序算法，雖然它們在時間復雜度上面很占優(yōu)勢，但是對待排序數(shù)列的要求比較高，只有待排序數(shù)列符合它們各自的特點時，使用它們進行排序才能得到O(n)的效率，因此，實際使用中也不是太多。
五、排序算法總結(jié)
如下是八種基本排序算法的總結(jié)：
八大排序算法總結(jié)
以上是比較基本的排序算法，還有其它的排序算法會在以后總結(jié)。
當你拿到一個數(shù)列考慮使用哪一種排序算法的時候：
- 優(yōu)先考慮是否可以使用線性排序算法；
- 如果數(shù)據(jù)不符合線性排序算法的特征，再看下數(shù)據(jù)量是否比較大，不大的話就選用O(n^2)的算法即可，比較簡單；
- 如果數(shù)據(jù)量比較大，還是優(yōu)先考慮使用O(nlogn)的排序算法；
- 其中因為歸并算法空間復雜度較高，因此快速排序會被更多地被考慮使用。
- 快速排序的缺點在于最壞情況下時間復雜度會到O(n^2)，這個取決于你每次迭代選取基準元素的方式和數(shù)列的特點決定的，通常可以對選取基準元素的方式進行優(yōu)化來盡量避免這個問題。
- 比如原先是選取第一個或者最后一個元素，可以改進為隨機選取或者別的方式，目標是使得基準元素左右兩邊的數(shù)據(jù)元素個數(shù)都差不多，這樣才能維持O(nlogn)的時間復雜度。
