这是快速排序题,答案有点奇怪

img

img


我有几个问题:
high一直没有变,第二空与seq[high]比较
第三空,pivot也是一直等于seq[low]为什么还要再写

哪里的题目?我也觉得有问题。Exchange方法好像永远不会执行。有后续的话麻烦告知我一下。

答案是错误的。

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 以下回答来自chatgpt:

    问题1: 在快速排序的代码中,变量high在整个代码中没有被修改,为什么要与seq[high]进行比较呢?

    答案:在快速排序算法中,变量high的作用是用来划分左右子数组的边界。它的初始值为数组的最后一个元素的索引,即len(seq)-1。在每次递归调用快速排序函数时,我们会根据pivot值将数组分成两个部分,而变量high的作用就是用来指示右子数组的边界位置。在代码中虽然没有直接修改high的值,但是在每次递归调用时,high的值会被更新为当前pivot位置的前一个索引。所以与seq[high]进行比较的目的是为了判断当前元素是否大于pivot,如果大于则需要将其放在右子数组中。

    以下是一个示例代码,展示了如何实现快速排序算法:

    def quick_sort(seq, low, high):
        if low < high:
            pivot_index = partition(seq, low, high)
            quick_sort(seq, low, pivot_index-1)
            quick_sort(seq, pivot_index+1, high)
    
    def partition(seq, low, high):
        pivot_value = seq[low] # 选择第一个元素作为pivot
        left = low + 1
        right = high
    
        done = False
        while not done:
            while left <= right and seq[left] <= pivot_value:
                left = left + 1
            while seq[right] >= pivot_value and right >=left:
                right = right -1
            if right < left:
                done= True
            else:
                seq[left], seq[right] = seq[right], seq[left]
    
        seq[low], seq[right] = seq[right], seq[low]
        return right
    
    # 测试代码
    seq = [45, 78, 23, 56, 89, 12, 35]
    quick_sort(seq, 0, len(seq)-1)
    print(seq)
    

    问题2: 在代码中,有一个第三空,变量pivot一直等于seq[low],那为什么还要在代码中再次指定pivot的值呢?

    答案:在快速排序算法中,pivot是用来作为比较标准,将数组分成两个部分。在代码中,第一空处的设置是为了将pivot与其他元素进行比较,判断每个元素应该在哪个子数组中。第二空处的设置是为了将最终确定的pivot值与右子数组中的第一个元素交换位置,确保pivot值被正确放置在分界点上。

    代码中第一处的设定是为了在while循环中进行比较,确保左右指针在分界点时停止移动。第二处的设定是为了将分界点的值与右子数组中第一个值交换,即将pivot值正确放置在分界点上。

    当然,如果在代码中我们没有再次指定pivot值,也会得到正确的结果。但是为了代码的清晰和可读性,明确地指定pivot值是更好的实践。

    希望以上回答能够帮助你理解快速排序算法。如果还有其他问题,请随时提问。


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

答案是错误的