// 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]
}
试图使用Hoare的分区实现Quicksort,但无法弄清楚我在做什么错。它陷入无限循环,总是在内存不足的情况下运行
fatal error: runtime: out of memory
最佳答案
在寻找i和j的位置进行交换时,应使用非严格不等式。所以代替
if arr[j] > pivot {
break
}
你应该有
if arr[j] >= pivot {
break
}
和我一样。代替
if arr[i] < pivot {
break
}
使用
if arr[i] <= pivot {
break
}
我也不确定它是否是有意的,但是目前您的算法是以降序排列的。如果要按升序排序,请在i和j之间进行比较。所以:
if arr[j] <= pivot {
break
}
和
if arr[i] >= pivot {
break
}