? ? 排序思路
? ? 利用分治的思想，將數(shù)組從中間拆分，比較，再合并则果，
? ? 遞推公式 ????merge_sort(left...right)=merge_sort(merge_sort(left...middle),merge_sort(middle+1...right))
? ? 終止條件
? ? left >= right
? ??時間復(fù)雜度分析
?? 對n個元素進(jìn)行排序需要時間為T(n)炕淮，拆分?jǐn)?shù)組后兩個數(shù)組的排序的時間為T(2n)
? ? merge_sort_B中合并數(shù)組的時間復(fù)雜度是O(n)
? ? 歸并排序的時間復(fù)雜度的計算公式為
? ? T(1) = C? -> n=1的時候乖寒，時間復(fù)雜度為常量級的執(zhí)行時間
? ? T(n)? = 2*T(n/2) + n
? ? ? ? = 4*T(n/4) + 2*n
? ? ? ? = 8*T(n/8) + 3*n
? ? ? ? = ...
? ? ? ? = 2^k *T(n/2^k)+ k*n.
? ? 當(dāng) T(n/2^k) = T(1)? ---> n/2^k = 1 ---> k = log以2為底n的對數(shù) ---> k= log(n)/log(2)
? ? 將k代入上面的公式 T(n) = Cn + n * (log(n)/log(2))
? ? 減去常量Cn和log(2)之后
?????O(n*log(n)) = O(nlogn)
? ??--------------------------
? ? 空間復(fù)雜度分析
? ? 在merge_sort_B每次執(zhí)行的時候都會創(chuàng)建一個臨時數(shù)組other
? ? 但是因為每次和并完成之后other會被釋放
? ? 所以只需要一個臨時空間并且大小不會超過n個數(shù)據(jù)的大小
? ? 這樣空間復(fù)雜度就為O(n)
