快速排序
在解釋之前，先上一張快排的圖，我發現直接看圖理解演算法更簡單
首先需要了解的是，快速排序的程序是遞回呼叫的，
步驟：
- 先選出一個參考值，用來進行比較，這個參考值可以從待排序的陣列里任選一個，一般選擇第一個或者最后一個，
- 在選出一個參考值之后，開始遍歷陣列，把比參考值小的放到它的左邊，大于等于它的放到右邊；在實作的時候就是交換位置，在實作的時候，需要維護兩個指標，頭指標和尾指標，如果遍歷的數比參考值小，就讓這個數和頭指標指向的數交換位置，并且頭指標向右移動一步，類似的，尾指標則是向左移動一步，
代碼實作
package main
func quickSort(nums []int) {
if len(nums) < 2 {
return
}
head, tail := 0, len(nums)-1
Reference := nums[0]
i := 1
for head < tail {
if nums[i] < Reference {
nums[i], nums[head] = nums[head], nums[i]
head++
i++
} else {
nums[i], nums[tail] = nums[tail], nums[i]
tail--
}
}
quickSort(nums[:head])
quickSort(nums[head+1:])
}
可以看到，最后對參考值左邊和右邊的數進行遞回排序，一直到只剩下兩個數的時候，得到了正確的順序之后回傳之前的呼叫，最終就得到了排序后的結果，
空間復雜度： O(1), 在執行程序中只申請了一個 reference，因此空間復雜度是 O(1)
時間復雜度： O(nlogn), 這里貼個計算公式，
T(1) = C； n=1時，只需要常量級的執行時間，所以表示為C，
T(n) = 2*T(n/2) + n； n>1
解釋一下：陣列的時間復雜度為 T(n)，那么當分為兩部分之后，每一個部分的時間復雜度應為 T(n/2)，而合并兩個陣列的時間復雜度是 n，因此總的時間復雜度是 2*T(n/2) + n，這個公式是計算遞回演算法時間復雜度的一個公式，快排可以用，歸并排序也可以同樣的計算，
求解 T(n) 的程序:
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
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......
= 2^k * T(n/2^k) + k * n
......
上面的求解程序其實并不是很符合快速排序，因為把陣列一分為二的前提是選取的參考值正好是整個能讓整個陣列一分為二，瞎蒙一個都有這種效果，顯然概率是比較小的，但是在估算的時候就先這么算吧，，，非要去推導公式我也不會，，，
當 T(n/2^k) = T(1) 時，即 n/2^k = 1，所以 k = logn,代入上面的公式得 T(n)=Cn+nlog2n，即 O(nlogn)，
但是快速排序的性能與它的磁區點選取是有關系的，如果一個有序的陣列，我們每次都選取了最后一個來作為參考，這樣就需要進行 n-1 次磁區，使得快排的時間復雜度退化到 O(n^2)
歸并排序
還是先上一張歸并排序的動圖
與快速排序不同的是，歸并排序不需要選參考值，直接從中間分開，一直分到最后一個一組，再合并起來，最重要的也是這個 merge 操作，創建一個臨時陣列，因為待合并的兩個陣列都是有序的，因此可以把兩個待合并的陣列按從小到大的順序插入臨時陣列中，最終合并到只剩下一個陣列的時候就是結果了，
代碼實作
package main
func mergeSort(nums []int, left int, right int) {
if left >= right {
return 0
}
tmp := []int{}
mid := left + (right-left)/2
mergeSort(nums, left, mid)
mergeSort(nums, mid+1, right)
i, j := left, mid+1
for i <= mid && j <= right { // merge 操作
if nums[i] <= nums[j] {
tmp = append(tmp, nums[i])
count += j - (mid + 1)
i++
} else {
tmp = append(tmp, nums[j])
j++
}
}
for ; i <= mid; i++ { //右邊沒有資料了，左邊還有
tmp = append(tmp, nums[i])
}
for ; j <= right; j++ {
tmp = append(tmp, nums[j]) //右邊都是有序的了
}
for i := left; i <= right; i++ {
nums[i] = tmp[i-left] //拷貝回原陣列
}
}
時間復雜度: O(nlogn)，可以看上面的遞推公式，原理都是一樣的
空間復雜度：O(n)，如果按照上面的公式遞推，其實空間復雜度應該是 O(nlogn) 才對，但是每次合并完成后，占用的記憶體空間都被系統釋放了，因此同一時刻只有一個臨時陣列占用了空間，因此時間復雜度是 O(n)，
公眾號：沒有夢想的阿巧 后臺回復 "群聊"，一起學習，一起進步
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/165084.html
標籤：其他