霍尔的分区方案golang

Question

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]
}

尝试使用 Hoare 分区实现快速排序，但无法弄清楚我做错了什么。它陷入无限循环，运行时总是 内存不足

fatal error: runtime: out of memory

Answer 1

在寻找 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
    }

霍尔的分区方案golang

Hoare's partitioning scheme golang

algorithm

quicksort

go