Golang實(shí)現(xiàn)算法：快速排序和歸并排序的比較
在計(jì)算機(jī)科學(xué)中，排序是一種基本的算法問題。排序算法主要有兩類：比較排序和非比較排序。比較排序是通過比較元素的大小來(lái)排序的，而非比較排序則不是，常見的非比較排序有計(jì)數(shù)排序、桶排序和基數(shù)排序。而比較排序中，快速排序和歸并排序是兩種比較常見的排序算法。本文將比較這兩種算法的性能和實(shí)現(xiàn)。
一、快速排序
快速排序是典型的分治思想的體現(xiàn)，它的基本思想是：通過一次排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按照此方法對(duì)兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)過程遞歸進(jìn)行，以此達(dá)到整個(gè)序列變成有序序列。
1. 算法步驟
快速排序的算法步驟如下：
- 挑選基準(zhǔn)值：從數(shù)列中挑出一個(gè)元素作為基準(zhǔn)值，稱為樞軸(pivot)；
- 分割：重新排列序列，使得比樞軸小的元素在左邊，比樞軸大的元素在右邊。在這個(gè)分割結(jié)束之后，對(duì)于每個(gè)元素，它左邊的元素都比它小，右邊的元素都比它大；
- 遞歸排序子序列：通過遞歸排序左右兩個(gè)子序列，排序完成。
2. 代碼實(shí)現(xiàn)
Golang實(shí)現(xiàn)快速排序的代碼如下：
`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
}
在實(shí)現(xiàn)上采用了遞歸的思想，每次選擇最左邊的數(shù)作為基準(zhǔn)值，遍歷數(shù)組，將比基準(zhǔn)值小的數(shù)放到左邊，比基準(zhǔn)值大的數(shù)放到右邊，并返回基準(zhǔn)值（樞軸）在數(shù)組中的位置，以便于對(duì)左右兩個(gè)子數(shù)組進(jìn)行遞歸排序。如果使用golang內(nèi)置sort包對(duì)數(shù)組進(jìn)行排序，快排的代碼如下：`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內(nèi)置的sort包中，快排算法的效率極高，它通過減少遞歸的深度，以及處理小數(shù)組的方式來(lái)提高效率。
二、歸并排序
歸并排序也是一種分治的排序算法，它的基本思想是：將待排序序列分成若干個(gè)子序列，每個(gè)子序列都是有序的，然后合并子序列，使整個(gè)序列的數(shù)都有序。
1. 算法步驟
歸并排序的算法步驟如下：
- 拆分：將要排序的序列拆分成兩個(gè)子序列，拆分到序列只有一個(gè)元素時(shí)停止拆分；
- 排序：將每個(gè)子序列排序；
- 合并：將已經(jīng)排好序的子序列合并成一個(gè)新的序列。
2. 代碼實(shí)現(xiàn)
Golang實(shí)現(xiàn)歸并排序的代碼如下：
`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
}
在實(shí)現(xiàn)上采用了遞歸的思想，將數(shù)組拆分成左右兩個(gè)子數(shù)組，然后對(duì)每個(gè)子數(shù)組進(jìn)行遞歸排序。最后將已經(jīng)排好序的左右兩個(gè)子數(shù)組進(jìn)行合并。如果使用golang內(nèi)置sort包對(duì)數(shù)組進(jìn)行排序，歸并排序的代碼如下：`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內(nèi)置的sort包中，歸并排序的算法效率相對(duì)比較低，但它具有穩(wěn)定性，可以保證相同元素的順序不變。這也是它被廣泛使用的原因之一。
三、算法比較
快速排序和歸并排序都是分治思想的體現(xiàn)，它們的時(shí)間復(fù)雜度都為O(nlogn)。但是在最壞的情況下，快速排序的時(shí)間復(fù)雜度會(huì)退化到O(n^2)，而歸并排序的時(shí)間復(fù)雜度則穩(wěn)定在O(nlogn)。
另外，歸并排序需要額外的空間存儲(chǔ)子數(shù)組，而快速排序不需要額外的空間，它是原地排序的，所以在空間復(fù)雜度方面，快速排序優(yōu)于歸并排序。但是這也使得快速排序不穩(wěn)定，它不能保證相同元素的順序不變。
四、結(jié)論
在實(shí)際的應(yīng)用中，快速排序和歸并排序各有優(yōu)缺點(diǎn)，具體使用哪種算法需要根據(jù)實(shí)際情況進(jìn)行選擇。如果需要對(duì)大量數(shù)據(jù)進(jìn)行排序，且空間比較緊張，可以使用快速排序。如果要求排序穩(wěn)定，可以使用歸并排序。如果既需要排序穩(wěn)定，又不希望額外浪費(fèi)太多空間，可以考慮使用其他算法，比如堆排序。
以上就是IT培訓(xùn)機(jī)構(gòu)千鋒教育提供的相關(guān)內(nèi)容，如果您有web前端培訓(xùn)，鴻蒙開發(fā)培訓(xùn)，python培訓(xùn)，linux培訓(xùn)，java培訓(xùn)，UI設(shè)計(jì)培訓(xùn)等需求，歡迎隨時(shí)聯(lián)系千鋒教育。
京公網(wǎng)安備 11010802030320號(hào)