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

今天面試的時(shí)候，被問(wèn)到歸并排序的時(shí)間復(fù)雜度，這個(gè)大家都知道是O（nlogn），但是面試官又繼續(xù)問(wèn)，怎么推導(dǎo)出來(lái)的。這我就有點(diǎn)懵了，因?yàn)橹按_實(shí)沒(méi)有去真正理解這個(gè)時(shí)間復(fù)雜度是如何得出的，于是就隨便答了一波（理解了之后，發(fā)現(xiàn)面試的時(shí)候答錯(cuò)了......）。

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

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

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

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

......

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

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

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

......

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

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

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

**

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

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

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

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

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

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

......

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

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

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

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

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

總結(jié)

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