您的函数partition_median（）不使用第一个中间和最后一个元素的中位数，而仅使用中间元素

发布于 2025-01-27 13:57:01 字数 1014 浏览 2 评论 0原文

需要纠正此问题，我想使用快速排序中值枢轴emelent 我的教授问我这个语句

您的函数partition_median（）不使用第一个中间和最后一个元素的中位数，而仅使用中间元素。

但是我不知道

def partition_median(req_list,start_index,end_index):
    """Function get Pivot at meadian."""
    pivot = req_list[(end_index+start_index)//2]
    i, j = start_index - 1, end_index + 1
    while True:
        i += 1
        j -= 1
        while req_list[i] < pivot:
            i += 1
        while req_list[j] > pivot:
            j -= 1

        if i >= j:
            return j

        req_list[i], req_list[j] = req_list[j], req_list[i]
def qsort_median(req_list, start_index, end_index):
    """Function to sort by median."""
    if start_index < end_index:
        pivot = partition_median(req_list, start_index, end_index)
        qsort_median(req_list, start_index, pivot)
        qsort_median(req_list, pivot + 1, end_index)


def quicksort_pivot_median(list_re):
    """Function sorting by median."""
    qsort_median(list_re, 0, len(list_re) - 1)

原文

need to correct this i want to use quick sort median pivot emelent
my professor is asking me this statement

Your function partition_median () does not use the median of the first middle and last element, but only takes the middle element.

but i do no know

def partition_median(req_list,start_index,end_index):
    """Function get Pivot at meadian."""
    pivot = req_list[(end_index+start_index)//2]
    i, j = start_index - 1, end_index + 1
    while True:
        i += 1
        j -= 1
        while req_list[i] < pivot:
            i += 1
        while req_list[j] > pivot:
            j -= 1

        if i >= j:
            return j

        req_list[i], req_list[j] = req_list[j], req_list[i]
def qsort_median(req_list, start_index, end_index):
    """Function to sort by median."""
    if start_index < end_index:
        pivot = partition_median(req_list, start_index, end_index)
        qsort_median(req_list, start_index, pivot)
        qsort_median(req_list, pivot + 1, end_index)


def quicksort_pivot_median(list_re):
    """Function sorting by median."""
    qsort_median(list_re, 0, len(list_re) - 1)

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

肥爪爪 2025-02-03 13:57:01

的确，正如您的老师所说的那样，您将中间元素作为枢纽：

pivot = req_list[(end_index+start_index)//2]

显然您被要求“使用第一个，中间和最后一个元素的中位数” 。因此，至少您需要检查这三个值：

a = req_list[start_index]
b = req_list[(end_index+start_index)//2]
c = req_list[end_index]
# The median of 3 values can be got by taking them all, 
#    but then subtracting the two extremes from it:
pivot = a + b + c - max(a, b, c) - min(a, b, c)

另请参见中位数< /a>。

Indeed, as your teacher is saying, you are taking the middle element as pivot:

pivot = req_list[(end_index+start_index)//2]

Apparently you were asked to "use the median of the first, middle and last element". So at least you need to inspect those three values:

a = req_list[start_index]
b = req_list[(end_index+start_index)//2]
c = req_list[end_index]
# The median of 3 values can be got by taking them all, 
#    but then subtracting the two extremes from it:
pivot = a + b + c - max(a, b, c) - min(a, b, c)