快速排序，中间元素被选为枢轴 [英] Quick sort with middle element selected as the pivot

问题描述

我有此代码，但雇主要求我在中间进行调整 如果有人可以提供帮助，请修改此代码

I have this code but the employer has asked me to pivot in the middle If anyone can help, please edit this code

def quicksort(sequence, low, high):
    if low < high:
        pivot = partition(sequence, low, high)
        quicksort(sequence, low, pivot - 1)
        quicksort(sequence, pivot + 1, high)

def partition(sequence, low, high):
    pivot = sequence[low]
    i = low + 1
    for j in range(low + 1, high + 1):
        if sequence[j] < pivot:
            sequence[j], sequence[i] = sequence[i], sequence[j]
            i += 1
    sequence[i-1], sequence[low] = sequence[low], sequence[i-1]
    return i - 1

推荐答案

patel的答案从问题的Lomuto方案转换为Hoare方案.问题代码的最简单解决方法是将中间元素与低位元素交换为分区的第一行

patel's answer switches from the question's Lomuto scheme to Hoare scheme. The simplest fix to the question's code would be swapping middle element with low element as the first line in partition

def partition(sequence, low, high):
    sequence[low],sequence[(low+high)//2] = sequence[(low+high)//2],sequence[low] #change
    pivot = sequence[low]
      ...

这篇关于快速排序，中间元素被选为枢轴的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！