快排算法與歸并算法時間復(fù)雜度都是O(nlogn)的排序算法亲族。適合大規(guī)模的數(shù)據(jù)排序种呐。
思想利用的是分治思想狠半。
歸并排序
原理
原理：排序一個數(shù)組噩死，把數(shù)組從中間分為兩部分，然后對前后兩部分進(jìn)行分別排序神年。最后把排序好的兩部分都合并在一起已维，在合并的時候也會進(jìn)行排序。就是排序好的數(shù)據(jù)
合并：在合并的過程中會申請一個臨時數(shù)組空間已日，然后把兩個排序號的數(shù)組進(jìn)行取值對比垛耳，哪個小放入到臨時數(shù)組中。
思路：
兩個數(shù)組數(shù)據(jù)在比較大小的時候飘千，可能存在一個數(shù)組中的數(shù)據(jù)有剩余的堂鲜。需要把剩余的數(shù)據(jù)也遷移到臨時數(shù)組中
思考借助哨兵的減少代碼的量級。
性能分析
穩(wěn)定算法护奈？
穩(wěn)定算法：值相同的元素不需要移動缔莲。
在歸并算法中，數(shù)據(jù)相等元素在合并之后的算法中先把前半部分的數(shù)據(jù)放到臨時數(shù)組中逆济，這樣保證了值等同的元素酌予，在合并前后順序不變。所以穩(wěn)定算法奖慌。
時間復(fù)雜度
合并兩個子集合操作時間復(fù)雜度是O(N)
推導(dǎo)公式是用
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2 ) + n = 4*T(n/4)+2*n
= 4*(2*T(n/8) + n/4) +2*n = 8*T(n/8)+3*n
=2^k *T(n/2^k) +k *n
其中n是執(zhí)行合并需要的時間抛虫。
當(dāng)n/2^k ==1 的時候〖蛏可以計算出k的值建椰。T(n)=Cn+n*log2(n)。大O標(biāo)記法就是O(nlogn)
最好岛马，最壞棉姐，平均都是這個時間復(fù)雜度
空間復(fù)雜度
不是原地排序算法。
原地排序算法需要空間復(fù)雜度是O(1),歸并排序在實現(xiàn)的過程中需要申請臨時空間啦逆。內(nèi)存大小最大為數(shù)據(jù)的長度n伞矩，所以空間復(fù)雜度是O(n)
快排
快排思想：排序數(shù)據(jù)下標(biāo)從a-p,那么選擇從a-p之間的任意數(shù)據(jù)作為pivot分區(qū)點(diǎn)。
遍歷數(shù)據(jù)夏志，將小于分區(qū)點(diǎn)的值放到左邊乃坤，大于分區(qū)點(diǎn)的值放到右邊。
等待java代碼的實現(xiàn)
性能分析
也是分區(qū)操作計算公式同歸并算法。時間復(fù)雜度是O(nlogn)湿诊，大會最壞的情況下時間復(fù)雜度會擴(kuò)展到O(n*n)狱杰，
選擇的分區(qū)點(diǎn)最小，導(dǎo)致沒有成功的分區(qū)厅须。
穩(wěn)定算法
數(shù)據(jù)相等的時候不進(jìn)行操作數(shù)據(jù)移動仿畸。所以是穩(wěn)定算法
時間復(fù)雜度
O(nlogn)最壞是O(nlogn)
空間復(fù)雜度
因為是數(shù)據(jù)交換，所以沒有使用到多余的空間朗和。是原地排序算法
