快速排序和歸併排序的時間複雜度分析——通俗易懂
一、前言
今天面試的時候，被問到歸併排序的時間複雜度，這個大家都知道是O（nlogn），但是面試官又繼續問，怎麼推導出來的。這我就有點懵了，因為之前確實沒有去真正理解這個時間複雜度是如何得出的，於是就隨便答了一波（理解了之後，發現面試的時候答錯了……）。
歸併排序和快速排序，是算法中，非常重要的兩個知識點，同時也是在面試中被問的非常頻繁的內容，我明知如此，卻沒有徹底理解，真是太不應該了。所以，今天這篇博客就來分析一下這兩種排序算法的時間複雜度是如何得出的。我查了許多篇博客，很多都是通過公式進行分析，十分難理解，下面我就結合自己的理解，使用通俗易懂的方式進行描述（為了好理解，可能會有些啰嗦）。
二、正文
2.1 歸併排序的時間複雜度分析
了解歸併排序的應該都知道，歸併排序的時間複雜度是O（nlogn），且這個時間複雜度是穩定的，不隨需要排序的序列不同而產生波動。那這個時間複雜度是如何得來的呢？我們可以這樣分析，假設我們需要對一個包含n個數的序列使用歸併排序，並且使用的是遞歸的實現方式，那麼過程如下：
- 遞歸的第一層，將
n個數劃分為2個子區間，每個子區間的數字個數為n/2； - 遞歸的第二層，將
n個數劃分為4個子區間，每個子區間的數字個數為n/4； - 遞歸的第三層，將
n個數劃分為8個子區間，每個子區間的數字個數為n/8;
……
- 遞歸的第
logn層，將n個數劃分為n個子區間，每個子區間的數字個數為1；
我們知道，歸併排序的過程中，需要對當前區間進行對半劃分，直到區間的長度為1。也就是說，每一層的子區間，長度都是上一層的1/2。這也就意味着，當劃分到第logn層的時候，子區間的長度就是1了。而歸併排序的merge操作，則是從最底層開始（子區間為1的層），對相鄰的兩個子區間進行合併，過程如下：
- 在第
logn層（最底層），每個子區間的長度為1，共n個子區間，每相鄰兩個子區間進行合併，總共合併n/2次。n個數字都會被遍歷一次，所有這一層的總時間複雜度為O（n）；
……
- 在第二層，每個子區間長度為
n/4，總共有4個子區間，每相鄰兩個子區間進行合併，總共合併2次。n個數字都會被遍歷一次，所以這一層的總時間複雜度為O（n）； - 在第一層，每個子區間長度為
n/2，總共有2個子區間，只需要合併一次。n個數字都會被遍歷一次，所以這一層的總時間複雜度為O（n）；
通過上面的過程我們可以發現，對於每一層來說，在合併所有子區間的過程中，n個元素都會被操作一次，所以每一層的時間複雜度都是O（n）。而之前我們說過，歸併排序劃分子區間，將子區間劃分為只剩1個元素，需要劃分logn次。每一層的時間複雜度為O（n），共有logn層，所以歸併排序的時間複雜度就是O（nlogn）。
上面的描述算是非常詳細了，應該不會太難理解。如果上面的過程還是不太理解，那麼我們通過另外一種更直觀的方式進行分析。上面描述的是遞歸的過程，下面我們通過非遞歸（迭代）方式實現的歸併排序，再來分析一波，這種方式更加直觀（為什麼不直接通過非遞歸的方式描述，而是先通過遞歸的方式分析，是因為上面的過程也可以用來分析快速排序）。下面是通過非遞歸方式實現的歸併排序代碼，其中有兩處分析時間複雜度的關鍵點，我標註出來了（重點關注注釋）：
/**
* 此方法用來定義子區間大小，子區間大小從1->2->4->8 ... ->n/2
* 可以近似地認為進行了logn次
*/
public static void merge(int[] arr) {
// 關鍵點1：劃分子區間，每一次的子區間長度是上一次的兩倍，所以這個循環需要執行logn次
for(int i = 1;i<arr.length;i *= 2){
// 關鍵點2：此方法每次執行的時間複雜度為O（n），具體看下方
mergeSort(arr,i);
}
}
/**
* 以下方法，每次執行的時間複雜度都是O（n），
* 因為需要將arr數組的每gap個數子，作為一個子區間，
* 然後對相鄰的兩個子區間執行歸併排序的merge操作，
* 所以在這個方法中，arr數組中的每一個數都會在merge操作中，
* 被處理一次，所以下面這個方法的時間複雜度為O（n）
*/
public static void mergeSort(int[] arr, int gap) {
int[] tmp = new int[arr.length];
int index = 0;
int start1 = 0;
int end1 = start1 + gap - 1;
int start2 = end1 + 1;
int end2 = (start2 + gap - 1)>=arr.length?arr.length-1:start2+gap-1;
while(start2<arr.length){
while(start1<=end1&&start2<=end2){
if(arr[start1]<arr[start2]){
tmp[index++] = arr[start1++];
}else{
tmp[index++] = arr[start2++];
}
}
while(start1<=end1){
tmp[index++] = arr[start1++];
}
while(start2<=end2){
tmp[index++] = arr[start2++];
}
start1 = end2+1;
end1 = start1 + gap - 1;
start2 = end1 + 1;
end2 = (start2 + gap - 1)>=arr.length?arr.length-1:start2+gap-1;
}
while(start1<arr.length){
tmp[index++] = arr[start1++];
}
for(int j = 0;j<tmp.length;j++){
arr[j] = tmp[j];
}
}
上面的代碼，merge方法中的循環需要循環logn次，每次循環都調用一次mergeSort方法，mergeSort方法的時間複雜度為O（n），所以很容易得出歸併排序的時間複雜度為O（nlogn）。
2.2 快速排序的時間複雜度
了解快速排序的應該知道，快速排序的時間複雜度在O（nlogn）~ O（n^2）之間，下面我就來分別分析這兩種情況：
（一）快速排序的最好情況O（nlogn）
這種情況下，其實和上面通過遞歸分析的歸併排序很類似，理解了歸併排序的時間複雜度分析，那這裡應該也很好理解。快速排序的實現方式，就是在當前區間中選擇一個軸，區間中所有比軸小的數都需要放到軸的左邊，而比軸大的數則放到軸的右邊。在理想的情況下，我們選取的軸剛好就是這個區間的中位數。也就是說，在操作之後，正好將區間分成了數字個數相等的左右兩個子區間。此時就和歸併排序基本一致了：
- 遞歸的第一層，
n個數被劃分為2個子區間，每個子區間的數字個數為n/2； - 遞歸的第二層，
n個數被劃分為4個子區間，每個子區間的數字個數為n/4； - 遞歸的第三層，
n個數被劃分為8個子區間，每個子區間的數字個數為n/8;
……
- 遞歸的第
logn層，n個數被劃分為n個子區間，每個子區間的數字個數為1；
以上過程與歸併排序基本一致，而區別就是，歸併排序是從最後一層開始進行merge操作，自底向上；而快速排序則是從第一層開始，交換區間中數字的位置，也就是自頂向下。但是，merge操作和快速排序的調換位置操作，時間複雜度是一樣的，對於每一個區間，處理的時候，都需要遍歷一次區間中的每一個元素。這也就意味着，快速排序和歸併排序一樣，每一層的總時間複雜度都是O（n），因為需要對每一個元素遍歷一次。而且在最好的情況下，同樣也是有logn層，所以快速排序最好的時間複雜度為O（nlogn）。
（二）快速排序的最壞情況O（n^2）
下面我們再來說一說快速排序的最壞情況，這種情況就比較好理解了。什麼是快速排序的最壞情況，那就是，對於每一個區間，我們在處理的時候，選取的軸剛好就是這個區間的最大值或者最小值。比如我們需要對n個數排序，而每一次進行處理的時候，選取的軸剛好都是區間的最小值。於是第一次操作，在經過調換元素順序的操作後，最小值被放在了第一個位置，剩餘n-1個數佔據了2到n個位置；第二次操作，處理剩下的n-1個元素，又將這個子區間的最小值放在了當前區間的第1個位置，以此類推……每次操作，都只能將最小值放到第一個位置，而剩下的元素，則沒有任何變化。所以對於n個數來說，需要操作n次，才能為n個數排好序。而每一次操作都需要遍歷一次剩下的所有元素，這個操作的時間複雜度是O（n），所以總時間複雜度為O（n^2）。
其實上面的過程，我們可以換一個角度理解：每次操作，找出最小值放到剩餘區間的第一個位置，這不就是選擇排序的實現方式嗎？而選擇排序的時間複雜度就是O（n^2），所以上面的過程也就O（n^2）。
三、總結
以上內容，就是我基於自己的理解，對快速排序和歸併排序時間複雜度的分析。為了更好理解，我的描述都儘可能的詳細，所以可能會有點啰嗦，但是我認為還是很通俗易懂的。希望這篇博客能夠為之前對這兩種排序算法理解不是特別清晰的人提供幫助，同時，若上面的內容存在錯誤或不足，歡迎指正或補充。
