1
快速排序與霍爾的分區霍爾的分區方案golang
// Hoare's partitioning scheme
func PartitionHoare(arr []int, low, high int) int {
length := len(arr)
if length == 0 {
panic("Array size is 0")
}
pivot := arr[low]
i := low - 1
j := high + 1
for {
for {
j--
if arr[j] > pivot {
break
}
}
for {
i++
if arr[i] < pivot {
break
}
}
if i < j {
Swap(&arr, i, j)
} else {
return j
}
}
}
// Sort
func SortHoare(arr []int, low, high int) {
if low < high {
p := PartitionHoare(arr, low, high)
SortHoare(arr, low, p)
SortHoare(arr, p+1, high)
}
}
// Swap i <--> j
func Swap(arr *[]int, i, j int) {
(*arr)[i], (*arr)[j] = (*arr)[j], (*arr)[i]
}
嘗試使用霍爾的分區來實現快速排序,但不能找出我做錯了。它是停留在一個無限循環,始終運行了內存
fatal error: runtime: out of memory
你爲什麼不看看這個實現。 ...也就是爲什麼你的內存不足是因爲你的遞歸函數SortHoare()從來沒有它的轉義邏輯執行'低<高' https://github.com/gersakbogdan/golang-hackerrank/blob/master /quicksort.go SortHoare應該返回'low'和'high',因爲這個值沒有被更新...... primary,因爲low和high沒有被引用傳遞...... SortHoare實際上並沒有做任何有用的事情。 – reticentroot