dongzhong2018 2017-09-03 16:52
浏览 166
已采纳

Hoare的分区方案golang

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条回答 默认 最新

  • duandang6352 2017-09-03 17:41
    关注

    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
        }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 数学的三元一次方程求解
  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题