Golang實現算法：快速排序和歸并排序的比較

在計算機科學中，排序是一種基本的算法問題。排序算法主要有兩類：比較排序和非比較排序。比較排序是通過比較元素的大小來排序的，而非比較排序則不是，常見的非比較排序有計數排序、桶排序和基數排序。而比較排序中，快速排序和歸并排序是兩種比較常見的排序算法。本文將比較這兩種算法的性能和實現。

一、快速排序

快速排序是典型的分治思想的體現，它的基本思想是：通過一次排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按照此方法對兩部分數據分別進行快速排序，整個過程遞歸進行，以此達到整個序列變成有序序列。

1. 算法步驟

快速排序的算法步驟如下：

- 挑選基準值：從數列中挑出一個元素作為基準值，稱為樞軸(pivot)；

- 分割：重新排列序列，使得比樞軸小的元素在左邊，比樞軸大的元素在右邊。在這個分割結束之后，對于每個元素，它左邊的元素都比它小，右邊的元素都比它大；

- 遞歸排序子序列：通過遞歸排序左右兩個子序列，排序完成。

2. 代碼實現

Golang實現快速排序的代碼如下：

`go

func QuickSort(arr int, left, right int) {

if left >= right {

return

}

pivot := partition(arr, left, right)

QuickSort(arr, left, pivot-1)

QuickSort(arr, pivot+1, right)

}

func partition(arr int, left, right int) int {

pivot := arr

for left < right {

for left < right && arr >= pivot {

right--

}

arr = arr

for left < right && arr <= pivot {

left++

}

arr = arr

}

arr = pivot

return left

}

在實現上采用了遞歸的思想，每次選擇最左邊的數作為基準值，遍歷數組，將比基準值小的數放到左邊，比基準值大的數放到右邊，并返回基準值（樞軸）在數組中的位置，以便于對左右兩個子數組進行遞歸排序。如果使用golang內置sort包對數組進行排序，快排的代碼如下：`gofunc QuickSort(data Interface) {n := data.Len()quickSort(data, 0, n, maxDepth(n))}func quickSort(data Interface, a, b, maxDepth int) {for b-a > 12 {if maxDepth == 0 {heapSort(data, a, b)return}maxDepth--i, j := a+1, b-1if data.Less(j, i) {data.Swap(i, j)}if data.Less(j, i+1) {data.Swap(i+1, j)}if data.Less(i, i+1) {data.Swap(i, i+1)}p := ifor {for ; data.Less(i, p); i++ {}for ; j > p && !data.Less(p, j); j-- {}if i >= j {break}data.Swap(i, j)}data.Swap(p, j)if j-p > b-j {quickSort(data, a, j, maxDepth)a = j + 1} else {quickSort(data, j+1, b, maxDepth)b = j}}if b-a > 1 {for i := a + 1; i < b; i++ {for j := i; j > a && data.Less(j, j-1); j-- {data.Swap(j, j-1)}}}}

在Golang內置的sort包中，快排算法的效率極高，它通過減少遞歸的深度，以及處理小數組的方式來提高效率。

二、歸并排序

歸并排序也是一種分治的排序算法，它的基本思想是：將待排序序列分成若干個子序列，每個子序列都是有序的，然后合并子序列，使整個序列的數都有序。

1. 算法步驟

歸并排序的算法步驟如下：

- 拆分：將要排序的序列拆分成兩個子序列，拆分到序列只有一個元素時停止拆分；

- 排序：將每個子序列排序；

- 合并：將已經排好序的子序列合并成一個新的序列。

2. 代碼實現

Golang實現歸并排序的代碼如下：

`go

func MergeSort(arr int) int {

if len(arr) <= 1 {

return arr

}

mid := len(arr) / 2

left := MergeSort(arr)

right := MergeSort(arr)

return merge(left, right)

}

func merge(left, right int) int {

result := int{}

for len(left) > 0 && len(right) > 0 {

if left <= right {

result = append(result, left)

left = left

} else {

result = append(result, right)

right = right

}

}

if len(left) > 0 {

result = append(result, left...)

}

if len(right) > 0 {

result = append(result, right...)

}

return result

}

在實現上采用了遞歸的思想，將數組拆分成左右兩個子數組，然后對每個子數組進行遞歸排序。最后將已經排好序的左右兩個子數組進行合并。如果使用golang內置sort包對數組進行排序，歸并排序的代碼如下：`gofunc MergeSort(data Interface) {n := data.Len()if n < 2 {return}a := make(slice, n/2)b := make(slice, n-n/2)copy(a, data)copy(b, data)MergeSort(a)MergeSort(b)if a.Less(b) {copy(data, a)copy(data, b)return}for i, j, k := 0, 0, 0; k < n; k++ {if j >= len(b) || (i < len(a) && !a.Less(b)) {data = ai++} else {data = bj++}}}

在Golang內置的sort包中，歸并排序的算法效率相對比較低，但它具有穩定性，可以保證相同元素的順序不變。這也是它被廣泛使用的原因之一。

三、算法比較

快速排序和歸并排序都是分治思想的體現，它們的時間復雜度都為O(nlogn)。但是在最壞的情況下，快速排序的時間復雜度會退化到O(n^2)，而歸并排序的時間復雜度則穩定在O(nlogn)。

另外，歸并排序需要額外的空間存儲子數組，而快速排序不需要額外的空間，它是原地排序的，所以在空間復雜度方面，快速排序優于歸并排序。但是這也使得快速排序不穩定，它不能保證相同元素的順序不變。

四、結論

在實際的應用中，快速排序和歸并排序各有優缺點，具體使用哪種算法需要根據實際情況進行選擇。如果需要對大量數據進行排序，且空間比較緊張，可以使用快速排序。如果要求排序穩定，可以使用歸并排序。如果既需要排序穩定，又不希望額外浪費太多空間，可以考慮使用其他算法，比如堆排序。

以上就是IT培訓機構千鋒教育提供的相關內容，如果您有web前端培訓，鴻蒙開發培訓，python培訓，linux培訓，java培訓，UI設計培訓等需求，歡迎隨時聯系千鋒教育。