mergeSort

口訣：

左拆分，左合并鸭巴，右拆分，右合并拦盹，最后合并左右鹃祖。

歸并排序的邏輯

歸并排序的戰(zhàn)略（宏觀）邏輯

先將原數(shù)組拆分為arr.length個(gè)小數(shù)組，每個(gè)數(shù)組長(zhǎng)度為1普舆。
小數(shù)組之間合并恬口，進(jìn)行第一次合并
第一次合并后校读，此時(shí)大數(shù)組分為了arr.length/2個(gè)小數(shù)組，每個(gè)小數(shù)組有兩個(gè)元素祖能，再次合并
每次合并后歉秫，將新的最小數(shù)組合并。

拆分的邏輯是遞歸养铸，需要先推導(dǎo)出遞歸的公式和退出低軌的條件：

忽略常數(shù)項(xiàng) 參數(shù)l,r代表數(shù)組左右索引雁芙，數(shù)組允許左右索引想等
mergeSort(l,r) = merge(mergeSort(l,p),merge_sort(p+1,r))
退出條件為：
l>=r

歸并排序合并的邏輯

本質(zhì)：最小數(shù)組（左右數(shù)組）元素之間的比較，構(gòu)造一個(gè)有序數(shù)組钞螟，完成合并

while循環(huán)却特，左右數(shù)組均從個(gè)字其實(shí)索引位開(kāi)始比較，并將本次比較的小值放到臨時(shí)數(shù)組中筛圆。直到一側(cè)數(shù)組中所有元素都放入了臨時(shí)數(shù)組（即一側(cè)數(shù)組元素清空）
判斷余下了那測(cè)數(shù)組裂明，將該測(cè)數(shù)組遍歷并放入臨時(shí)數(shù)組中（此時(shí)是一測(cè)數(shù)組內(nèi)部循壞，沒(méi)測(cè)數(shù)組都是有序的太援，所以直接遍歷賦值即可）
將新數(shù)組遍歷賦值給原數(shù)組

image.png

代碼實(shí)現(xiàn)

//遞歸拆分闽晦，直到拆分到最小數(shù)組長(zhǎng)度為1
public static void mergeSort(int[] arr,int left,int right,int[] temp){
    int mid = (left+right)/2;
    if (left<right){
        mergeSort(arr,left,mid,temp);
        mergeSort(arr,mid+1,right,temp);
        merge(arr,left,mid,right,temp);
    }
}
//合并
private static void merge(int[] arr, int left,int mid, int right, int[] temp) {
    //左側(cè)數(shù)組的索引，賦予初始值為左側(cè)數(shù)組的起始索引
    int leftIndex = left;
    //右側(cè)數(shù)組的索引提岔，賦予初始值為右側(cè)數(shù)組的起始索引
    int rightIndex = mid+1;
    int tIndex = 0;
    //todo 最小數(shù)組之間的元素比較并給臨時(shí)數(shù)組賦值   eg:數(shù)組中四個(gè)元素仙蛉，左右各兩個(gè)元素，左面數(shù)組和右側(cè)數(shù)組均從起始索引遍歷碱蒙，放入臨時(shí)數(shù)組
    while(leftIndex<=mid && rightIndex<=right){
        //起始判定：左側(cè)數(shù)組最小值荠瘪，和右側(cè)數(shù)組最小值比較， 左右數(shù)組都從各自的起始元素開(kāi)始比較赛惩，放入臨時(shí)數(shù)組哀墓，跳出循環(huán)的條件為，當(dāng)一側(cè)數(shù)組先比較完喷兼，即出現(xiàn)一側(cè)數(shù)組清空的情況篮绰，跳出循環(huán)。
        //注意此處一定要是<=  為了應(yīng)對(duì)值相同的場(chǎng)景季惯，保證其的穩(wěn)定性
        if (arr[leftIndex]<=arr[rightIndex]){
            temp[tIndex] = arr[leftIndex];
            leftIndex++;
            tIndex++;
        }else {
            temp[tIndex] = arr[rightIndex];
            rightIndex++;
            tIndex++;
        }
    }
    //todo 將剩下的值都放到臨時(shí)數(shù)組中
    //判斷哪測(cè)數(shù)組清空了吠各，將未清空的一側(cè)數(shù)組按照其索引位開(kāi)始遍歷，放到臨時(shí)數(shù)組中（沒(méi)測(cè)數(shù)組均是有序的）
    while (leftIndex <= mid){
        temp[tIndex] = arr[leftIndex];
        tIndex++;
        leftIndex++;
    }

    while (rightIndex<=right){
        temp[tIndex] = arr[rightIndex];
        tIndex++;
        rightIndex++;
    }
    //todo 將臨時(shí)數(shù)組復(fù)制給arr  可以直接遍歷賦值勉抓，因?yàn)樵瓟?shù)組的這部分元素都在臨時(shí)數(shù)組中

    int arrIndex = left;
    tIndex = 0;
    while (arrIndex<=right){
        //   System.out.println(tIndex+"-----------"+arrIndex);
        arr[arrIndex] = temp[tIndex];
        arrIndex++;
        tIndex++;
    }
}

歸并思想：

將一組數(shù)據(jù)拆分至最小單元贾漏，在將最小單元合并，合并的過(guò)程中進(jìn)行排序藕筋，合并直到最小單元長(zhǎng)度等于元數(shù)據(jù)長(zhǎng)度纵散。

性能分析

內(nèi)存消耗

O(n)
實(shí)際上，盡管每次合并操作都需要申請(qǐng)額外的內(nèi)存空間，但在合并完成之后困食，臨時(shí)開(kāi)辟的內(nèi)存空間就被釋放掉了边翁。在任意時(shí)刻，CPU 只會(huì)有一個(gè)函數(shù)在執(zhí)行硕盹，也就只會(huì)有一個(gè)臨時(shí)的內(nèi)存空間在使用符匾。臨時(shí)內(nèi)存空間最大也不會(huì)超過(guò) n 個(gè)數(shù)據(jù)的大小，所以空間復(fù)雜度是 O(n)瘩例。

穩(wěn)定性

是否穩(wěn)定決定于代碼21行
if (arr[leftIndex]<=arr[rightIndex])
如果判斷條件是<=那就是穩(wěn)定的啊胶，如果判斷條件是<而不是<=就是不穩(wěn)定的。

執(zhí)行效率

最好垛贤，最壞焰坪，平均都是O(nlogn)

這里分析時(shí)間復(fù)雜度，和之前有點(diǎn)不同聘惦，因?yàn)橥ㄟ^(guò)遞歸實(shí)現(xiàn)的某饰，所以這里的時(shí)間復(fù)雜度即分析遞歸的時(shí)間復(fù)雜度。

遞歸代碼時(shí)間復(fù)雜度推導(dǎo)過(guò)程

首先先看一下遞歸的使用場(chǎng)景
一個(gè)問(wèn)題 a 可以分解為多個(gè)子問(wèn)題 b善绎、c黔漂，那求解問(wèn)題 a 就可以分解為求解問(wèn)題 b、c禀酱。問(wèn)題 b炬守、c 解決之后，我們?cè)侔?b剂跟、c 的結(jié)果合并成 a 的結(jié)果减途。

遞歸代碼的時(shí)間復(fù)雜度：

如果我們定義求解問(wèn)題 a 的時(shí)間是 T(a)，求解問(wèn)題 b曹洽、c 的時(shí)間分別是 T(b) 和 T( c)鳍置，那我們就可以得到這樣的遞推關(guān)系式：
T(a) = T(b) + T(c) + K
其中 K 等于將兩個(gè)子問(wèn)題 b、c 的結(jié)果合并成問(wèn)題 a 的結(jié)果所消耗的時(shí)間衣洁。

mergeSort的時(shí)間復(fù)雜度：

我們假設(shè)對(duì) n 個(gè)元素進(jìn)行歸并排序需要的時(shí)間是 T(n)墓捻，那分解成兩個(gè)子數(shù)組排序的時(shí)間都是 T(n/2)。我們知道坊夫，merge() 函數(shù)合并兩個(gè)有序子數(shù)組的時(shí)間復(fù)雜度是 O(n)。所以撤卢，套用前面的公式环凿，歸并排序的時(shí)間復(fù)雜度的計(jì)算公式就是：

T(1) = C；   n=1時(shí)放吩，只需要常量級(jí)的執(zhí)行時(shí)間智听，所以表示為C。
T(n) = 2*T(n/2) + n； n>1

2*T(n/2)為每個(gè)子數(shù)組排序的時(shí)間
n為合并兩個(gè)子數(shù)組的時(shí)間到推，merge() 函數(shù)合并兩個(gè)有序子數(shù)組的時(shí)間復(fù)雜度是 O(n)
以上只是一次merge的時(shí)間函數(shù)考赛，如果在以上的基礎(chǔ)上再次拆分：

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n       //進(jìn)行兩次合并
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

當(dāng) T(n/2^k)=T(1) 時(shí)，也就是 n/2^k=1莉测，我們得到 k=log2n 颜骤。我們將 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 捣卤。
大O分析忍抽，則得出時(shí)間復(fù)雜度為：

O(nlogn)

歸并排序的執(zhí)行效率與要排序的原始數(shù)組的有序程度無(wú)關(guān)，所以其時(shí)間復(fù)雜度是非常穩(wěn)定的董朝，不管是最好情況鸠项、最壞情況，還是平均情況子姜，時(shí)間復(fù)雜度都是 O(nlogn)祟绊，這種排序算法，和原數(shù)組是否有序無(wú)關(guān)哥捕。

快速排序

排序邏輯

通過(guò)不斷遞歸二分久免，不斷將數(shù)組分成兩組，左側(cè)組所有元素都比右側(cè)組所有元素小扭弧，在和中間值比較的過(guò)程中阎姥，先到達(dá)中間位置的一側(cè)負(fù)責(zé)控制另一側(cè)的索引，讓另一組合中間值比較與交換中間值鸽捻，也就是另一組和中間值排序抡爹。

• 從數(shù)列中挑出一個(gè)元素兔魂，稱為 “基準(zhǔn)”（pivot）；
• 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面沟堡，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后夺谁，該基準(zhǔn)就處于數(shù)列的中間位置托猩。這個(gè)稱為分區(qū)（partition）操作；
• 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序碘箍。

遞歸公式

quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

終止條件：
p >= r

code

public static void quickSort(int[] arr,int left,int right){
        //todo 首次分組通過(guò)中間值遵馆，制造兩組，左面小于中間值丰榴，右面大于中間值货邓，后面每次都在各自組中再次分組，直到中間值等于最小值或者等于最大值四濒。
        int leftIndex = left;
        int rightIndex = right;
        int middleValue = arr[(leftIndex + rightIndex)/2];
        //左少 -1,1,2,0,3,4,6  l1 r3  l2 r2  l3 r1  -1,0,2,1,3,4,6    右少  -1,-2,-3,0,-4,-5,6    -1,1,2,0,-3,4,5  -1,-3,2,0,1,4,5   -1,-3,0,2,1,4,5
        while (leftIndex < rightIndex){
            int temp = 0;
            while (arr[leftIndex] < middleValue){
                leftIndex++;
            }
            while (arr[rightIndex] > middleValue){
                rightIndex--;
            }
            if (leftIndex == rightIndex){
                break;
            }
            temp = arr[leftIndex];
            arr[leftIndex] = arr[rightIndex];
            arr[rightIndex] = temp;
            //每次中軸兩側(cè)比較换况，左右互補(bǔ)越過(guò)中軸职辨，左先到，等右戈二，右先到舒裤，等左
            if (arr[rightIndex] == middleValue){
                leftIndex++;
            }
            if (arr[leftIndex] == middleValue){
                rightIndex--;
            }
        }
        //每次出循環(huán)，必然leftIndex = rightIndex
        if (leftIndex == rightIndex){
            leftIndex++;
            rightIndex--;
        }

        if (leftIndex<right ){
            quickSort(arr,leftIndex,right);
        }

        if (rightIndex>left){
            quickSort(arr,left,rightIndex);
        }
    }

性能分析

內(nèi)存消耗

O(1)

穩(wěn)定性

不穩(wěn)定

執(zhí)行效率

最佳情況：T(n) = O(nlogn) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(nlogn)

總結(jié)

歸并排序算法是一種在任何情況下時(shí)間復(fù)雜度都比較穩(wěn)定的排序算法觉吭，這也使它存在致命的缺點(diǎn)腾供，即歸并排序不是原地排序算法，空間復(fù)雜度比較高亏栈，是 O(n)台腥。正因?yàn)榇耍矝](méi)有快排應(yīng)用廣泛绒北。
快速排序算法雖然最壞情況下的時(shí)間復(fù)雜度是 O(n2)黎侈，但是平均情況下時(shí)間復(fù)雜度都是 O(nlogn)。不僅如此闷游，快速排序算法時(shí)間復(fù)雜度退化到 O(n2) 的概率非常小峻汉，我們可以通過(guò)合理地選擇 pivot 來(lái)避免這種情況。