快速排序和歸并排序的時間復(fù)雜度分析——通俗易懂

今天面試的時候，被問到歸并排序的時間復(fù)雜度，這個大家都知道是O（nlogn），但是面試官又繼續(xù)問，怎么推導(dǎo)出來的。這我就有點懵了，因為之前確實沒有去真正理解這個時間復(fù)雜度是如何得出的，于是就隨便答了一波（理解了之后，發(fā)現(xiàn)面試的時候答錯了......）。

歸并排序和快速排序，是算法中，非常重要的兩個知識點，同時也是在面試中被問的非常頻繁的內(nèi)容，我明知如此，卻沒有徹底理解，真是太不應(yīng)該了。所以，今天這篇博客就來分析一下這兩種排序算法的時間復(fù)雜度是如何得出的。我查了許多篇博客，很多都是通過公式進行分析，十分難理解，下面我就結(jié)合自己的理解，使用通俗易懂的方式進行描述（為了好理解，可能會有些啰嗦）。

歸并排序的時間復(fù)雜度分析

了解歸并排序的應(yīng)該都知道，歸并排序的時間復(fù)雜度是O（nlogn），且這個時間復(fù)雜度是穩(wěn)定的，不隨需要排序的序列不同而產(chǎn)生波動。那這個時間復(fù)雜度是如何得來的呢？我們可以這樣分析，假設(shè)我們需要對一個包含n個數(shù)的序列使用歸并排序，并且使用的是遞歸的實現(xiàn)方式，那么過程如下：

• 遞歸的第一層，將n個數(shù)劃分為2個子區(qū)間，每個子區(qū)間的數(shù)字個數(shù)為n/2；
• 遞歸的第二層，將n個數(shù)劃分為4個子區(qū)間，每個子區(qū)間的數(shù)字個數(shù)為n/4；
• 遞歸的第三層，將n個數(shù)劃分為8個子區(qū)間，每個子區(qū)間的數(shù)字個數(shù)為n/8;

......

• 遞歸的第logn層，將n個數(shù)劃分為n個子區(qū)間，每個子區(qū)間的數(shù)字個數(shù)為1；

我們知道，歸并排序的過程中，需要對當(dāng)前區(qū)間進行對半劃分，直到區(qū)間的長度為1。也就是說，每一層的子區(qū)間，長度都是上一層的1/2。這也就意味著，當(dāng)劃分到第logn層的時候，子區(qū)間的長度就是1了。而歸并排序的merge操作，則是從最底層開始（子區(qū)間為1的層），對相鄰的兩個子區(qū)間進行合并，過程如下：

• 在第logn層（最底層），每個子區(qū)間的長度為1，共n個子區(qū)間，每相鄰兩個子區(qū)間進行合并，總共合并n/2次。n個數(shù)字都會被遍歷一次，所有這一層的總時間復(fù)雜度為O（n）；

......

• 在第二層，每個子區(qū)間長度為n/4，總共有4個子區(qū)間，每相鄰兩個子區(qū)間進行合并，總共合并2次。n個數(shù)字都會被遍歷一次，所以這一層的總時間復(fù)雜度為O（n）；
• 在第一層，每個子區(qū)間長度為n/2，總共有2個子區(qū)間，只需要合并一次。n個數(shù)字都會被遍歷一次，所以這一層的總時間復(fù)雜度為O（n）；

通過上面的過程我們可以發(fā)現(xiàn)，對于每一層來說，在合并所有子區(qū)間的過程中，n個元素都會被 操作一次，所以每一層的時間復(fù)雜度都是O（n）。而之前我們說過，歸并排序劃分子區(qū)間，將子區(qū)間劃分為只剩1個元素，需要劃分logn次。每一層的時間復(fù)雜度為O（n），共有l(wèi)ogn層，所以歸并排序的時間復(fù)雜度就是O（nlogn） 。

上面的描述算是非常詳細了，應(yīng)該不會太難理解。如果上面的過程還是不太理解，那么我們通過另外一種更直觀的方式進行分析。上面描述的是遞歸的過程，下面我們通過非遞歸（迭代）方式實現(xiàn)的歸并排序，再來分析一波，這種方式更加直觀（為什么不直接通過非遞歸的方式描述，而是先通過遞歸的方式分析，是因為上面的過程也可以用來分析快速排序）。下面是通過非遞歸方式實現(xiàn)的歸并排序代碼，其中有兩處分析時間復(fù)雜度的關(guān)鍵點，我標(biāo)注出來了（重點關(guān)注注釋）：

**

/**
 * 此方法用來定義子區(qū)間大小，子區(qū)間大小從1->2->4->8 ... ->n/2
 * 可以近似地認為進行了logn次
 */
public static void merge(int[] arr) {
    // 關(guān)鍵點1：劃分子區(qū)間，每一次的子區(qū)間長度是上一次的兩倍，所以這個循環(huán)需要執(zhí)行l(wèi)ogn次
    for(int i = 1;i<arr.length;i *= 2){
        // 關(guān)鍵點2：此方法每次執(zhí)行的時間復(fù)雜度為O（n），具體看下方
        mergeSort(arr,i);
    }
}
/**
 * 以下方法，每次執(zhí)行的時間復(fù)雜度都是O（n），
 * 因為需要將arr數(shù)組的每gap個數(shù)子，作為一個子區(qū)間，
 * 然后對相鄰的兩個子區(qū)間執(zhí)行歸并排序的merge操作，
 * 所以在這個方法中，arr數(shù)組中的每一個數(shù)都會在merge操作中，
 * 被處理一次，所以下面這個方法的時間復(fù)雜度為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方法中的循環(huán)需要循環(huán)logn次，每次循環(huán)都調(diào)用一次mergeSort方法，mergeSort方法的時間復(fù)雜度為O（n），所以很容易得出歸并排序的時間復(fù)雜度為O（nlogn）。

快速排序的時間復(fù)雜度

了解快速排序的應(yīng)該知道，快速排序的時間復(fù)雜度在O（nlogn）~ O（n^2）之間，下面我就來分別分析這兩種情況：

（一）快速排序的最好情況O（nlogn）

這種情況下，其實和上面通過遞歸分析的歸并排序很類似，理解了歸并排序的時間復(fù)雜度分析，那這里應(yīng)該也很好理解?？焖倥判虻膶崿F(xiàn)方式，就是在當(dāng)前區(qū)間中選擇一個軸，區(qū)間中所有比軸小的數(shù)都需要放到軸的左邊，而比軸大的數(shù)則放到軸的右邊。在理想的情況下，我們選取的軸剛好就是這個區(qū)間的中位數(shù)。也就是說，在操作之后，正好將區(qū)間分成了數(shù)字個數(shù)相等的左右兩個子區(qū)間。此時就和歸并排序基本一致了：

• 遞歸的第一層，n個數(shù)被劃分為2個子區(qū)間，每個子區(qū)間的數(shù)字個數(shù)為n/2；
• 遞歸的第二層，n個數(shù)被劃分為4個子區(qū)間，每個子區(qū)間的數(shù)字個數(shù)為n/4；
• 遞歸的第三層，n個數(shù)被劃分為8個子區(qū)間，每個子區(qū)間的數(shù)字個數(shù)為n/8;

......

• 遞歸的第logn層，n個數(shù)被劃分為n個子區(qū)間，每個子區(qū)間的數(shù)字個數(shù)為1；

以上過程與歸并排序基本一致，而區(qū)別就是，歸并排序是從最后一層開始進行merge操作，自底向上；而快速排序則是從第一層開始，交換區(qū)間中數(shù)字的位置，也就是自頂向下。但是，merge操作和快速排序的調(diào)換位置操作，時間復(fù)雜度是一樣的，對于每一個區(qū)間，處理的時候，都需要遍歷一次區(qū)間中的每一個元素。這也就意味著，快速排序和歸并排序一樣，每一層的總時間復(fù)雜度都是O（n），因為需要對每一個元素遍歷一次。而且在最好的情況下，同樣也是有logn層，所以快速排序最好的時間復(fù)雜度為O（nlogn）。

快速排序的最壞情況O（n^2）

下面我們再來說一說快速排序的最壞情況，這種情況就比較好理解了。什么是快速排序的最壞情況，那就是，對于每一個區(qū)間，我們在處理的時候，選取的軸剛好就是這個區(qū)間的最大值或者最小值。比如我們需要對n個數(shù)排序，而每一次進行處理的時候，選取的軸剛好都是區(qū)間的最小值。于是第一次操作，在經(jīng)過調(diào)換元素順序的操作后，最小值被放在了第一個位置，剩余n-1個數(shù)占據(jù)了2到n個位置；第二次操作，處理剩下的n-1個元素，又將這個子區(qū)間的最小值放在了當(dāng)前區(qū)間的第1個位置，以此類推......每次操作，都只能將最小值放到第一個位置，而剩下的元素，則沒有任何變化。所以對于n個數(shù)來說，需要操作n次，才能為n個數(shù)排好序。而每一次操作都需要遍歷一次剩下的所有元素，這個操作的時間復(fù)雜度是O（n），所以總時間復(fù)雜度為O（n^2）。

其實上面的過程，我們可以換一個角度理解：每次操作，找出最小值放到剩余區(qū)間的第一個位置，這不就是選擇排序的實現(xiàn)方式嗎？而選擇排序的時間復(fù)雜度就是O（n^2），所以上面的過程也就O（n^2）。

總結(jié)

以上內(nèi)容，就是我基于自己的理解，對快速排序和歸并排序時間復(fù)雜度的分析。為了更好理解，我的描述都盡可能的詳細，所以可能會有點啰嗦，但是我認為還是很通俗易懂的。希望這篇博客能夠為之前對這兩種排序算法理解不是特別清晰的人提供幫助，同時，若上面的內(nèi)容存在錯誤或不足，歡迎指正或補充。