golang 歸并排序,快速排序,堆排序的實現(xiàn)
更新時間：2022年01月21日 09:57:21 作者：李晨毅
本文主要介紹了golang 歸并排序,快速排序,堆排序的實現(xiàn)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
歸并排序
歸并排序使用經(jīng)典的分治法（Divide and conquer）策略。分治法會將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之。
func sortArray(nums []int) []int {
if len(nums) <= 1 {
return nums
}
partA := sortArray(nums[:len(nums)/2])
partB := sortArray(nums[len(nums)/2:])
temp := make([]int, len(partA) + len(partB))
aPointer := 0
bPointer := 0
i := 0
for aPointer < len(partA) && bPointer < len(partB) {
if partA[aPointer] < partB[bPointer] {
temp[i] = partA[aPointer]
aPointer++
} else {
temp[i] = partB[bPointer]
bPointer++
}
i++
}
for aPointer < len(partA) {
temp[i] = partA[aPointer]
aPointer++
i++
}
for bPointer < len(partB) {
temp[i] = partB[bPointer]
bPointer++
i++
}
return temp
}
快速排序
快速排序算法采用的分治算法，因此對一個子數(shù)組A[p…r]進行快速排序的三個步驟為：
（1）分解：數(shù)組A[p...r]被劃分為兩個（可能為空）子數(shù)組A[p...q-1]和A[q+1...r]，給定一個樞軸，使得A[p...q-1]中的每個元素小于等于A[q]，A[q+1...r]中的每個元素大于等于A[q]，q下標是在劃分過程中計算得出的。
（2）解決：通過遞歸調(diào)用快速排序，對子數(shù)組A[p...q-1]和A[q+1...r]進行排序。
（3）合并：因為兩個子數(shù)組是就地排序，不需要合并操作，整個數(shù)組A[p…r]排序完成。
func sortArray(nums []int) []int {
quickSort(nums)
return nums
}
func quickSort(nums []int) {
left, right := 0, len(nums) - 1
for right > left {
// 右邊部分放大于
if nums[right] > nums[0] {
right--
continue
}
// 左邊部分放小于等于
if nums[left] <= nums[0] {
left++
continue
}
nums[left], nums[right] = nums[right], nums[left]
}
nums[0], nums[right] = nums[right], nums[0]
if len(nums[:right]) > 1 {
sortArray(nums[:right])
}
if len(nums[right + 1:]) > 1 {
sortArray(nums[right + 1:])
}
}
堆排序
func sortArray(nums []int) []int {
// 從n/2 最后一個非葉子結點起開始構建大頂堆
for i := len(nums) / 2; i >= 0; i-- {
heapSort(nums, i)
}
end := len(nums) - 1
// 每次將大頂堆的最大值與末尾進行交換，并再次排序
for end > 0 {
nums[0], nums[end] = nums[end], nums[0]
heapSort(nums[:end], 0)
end--
}
return nums
}
// 對一個非葉子結點進行排序
func heapSort(nums []int, pos int) {
end := len(nums) - 1
left := 2 * pos + 1
if left > end {
return
}
right := 2 * pos + 2
temp := left
// 先左右子結點進行比較，找出較小的那一個
if right <= end && nums[right] > nums[temp] {
temp = right
}
if nums[temp] <= nums[pos] {
return
}
nums[temp], nums[pos] = nums[pos], nums[temp]
// 如果發(fā)生了交換的話 就要繼續(xù)調(diào)查后續(xù)子節(jié)點(只調(diào)查交換了的后續(xù)，不用全調(diào)查，不然會超時)
heapSort(nums, temp)
}
卑鄙排序
func sortArray(nums []int) []int {
sort.Ints(nums)
return nums
}
到此這篇關于golang 歸并排序,快速排序,堆排序的實現(xiàn)的文章就介紹到這了,更多相關golang 歸并排序,快速排序,堆排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
很多朋友想試試用Go語言發(fā)送郵件,所以接下來小編給大家介紹一下如何用Go語言發(fā)送郵件,文中通過代碼實例講解的非常詳細,需要的朋友可以參考下2023-07-07
相信每位編程開發(fā)者們應該都知道,Golang作為一門標榜工程化的語言,提供了非常簡便、實用的編寫單元測試的能力,下面這篇文章主要給大家介紹了關于GoLang基礎學習之go?test測試的相關資料,需要的朋友可以參考下2022-08-08
這篇文章主要介紹了Go語言編程中slice切片結構,其中Append方法的用法介紹較為詳細,需要的朋友可以參考下2015-10-10
這篇文章主要介紹了創(chuàng)建第一個Go語言程序Hello,Go!本文詳細的給出項目創(chuàng)建、代碼編寫的過程,同時講解了GOPATH、Go install等內(nèi)容,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了go語言的sql包原理與用法,較為詳細的分析了Go語言里sql包的結構、相關函數(shù)與使用方法,需要的朋友可以參考下2016-07-07
Golang 的時間處理是 Golang 編程中的一個重要方面，它涉及到了時間類型、時間格式化、時間計算、時區(qū)處理以及定時器和超時機制等多個方面。在本文中，我們將從更深入的角度來探討 Golang 的時間處理2023-04-04
在Go語言中，Goroutine是一種輕量級線程，它的退出機制對于并發(fā)編程至關重要，下午就來介紹幾種Goroutine的退出機制，希望對大家有所幫助2023-06-06
這篇文章主要介紹了使用pprof分析golang內(nèi)存泄露問題及解決,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-04-04
這篇文章主要介紹了Golang截取字符串方法，文中介紹了使用rune函數(shù)和utf包以及range遍歷的方式，熟練掌握這些可以幫助我們更方便地處理字符串，提高編程效率和代碼質(zhì)量，感興趣的同學可以參考下文2023-05-05
這篇文章主要介紹了golang-map的基本操作,由于map是引用類型，所以在操作的時候，必須先初始化，本文通過多種方式給大家講解map的定義方式，需要的朋友可以參考下2022-08-08