英文:
Hoare's partitioning scheme golang
问题
使用Hoare的划分方案实现快速排序，但是我无法弄清楚我做错了什么。它陷入了一个无限循环，总是内存不足。
// Hoare的划分方案
func PartitionHoare(arr []int, low, high int) int {
length := len(arr)
if length == 0 {
panic("数组大小为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
}
}
}
// 排序
func SortHoare(arr []int, low, high int) {
if low < high {
p := PartitionHoare(arr, low, high)
SortHoare(arr, low, p)
SortHoare(arr, p+1, high)
}
}
// 交换 i <--> j
func Swap(arr *[]int, i, j int) {
(*arr)[i], (*arr)[j] = (*arr)[j], (*arr)[i]
}
尝试使用Hoare的划分方案实现快速排序，但是无法解决问题。它陷入了一个无限循环，并且总是内存不足。
英文:
> Quicksort with Hoare's partitioning
// 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]
}
Trying to implement Quicksort using Hoare's partitioning but can't figure out what am I doing wrong. It is stuck in an infinite loop, always runs out of memory
fatal error: runtime: out of memory
答案1
得分: 2
在查找i和j的位置进行交换时，应该使用非严格不等式。所以，不要使用：
if arr[j] > pivot {
break
}
而应该使用：
if arr[j] >= pivot {
break
}
对于i也是一样。不要使用：
if arr[i] < pivot {
break
}
而应该使用：
if arr[i] <= pivot {
break
}
此外，我不确定这是否是有意为之，但是目前你的算法是按降序排序的。如果你想按升序排序，请交换i和j之间的比较。所以：
if arr[j] <= pivot {
break
}
和
if arr[i] >= pivot {
break
}
英文:
You should use non strict inequalities while looking for position of i and j to do the swap. So instead of
if arr[j] > pivot {
break
}
you should have
if arr[j] >= pivot {
break
}
And the same for i. Instead of
if arr[i] < pivot {
break
}
use
if arr[i] <= pivot {
break
}
Also I'm not sure if it's intentional or not, but currently your algorithm sorts in descending order. If you want to sort in ascending order swap the comparitions between i and j. So:
if arr[j] <= pivot {
break
}
and
if arr[i] >= pivot {
break
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论