python 3中值3快速排序实现，在满足递归深度限制后切换到堆排序 [英] python 3 median-of-3 Quicksort implementation which switches to heapsort after a recursion depth limit is met

问题描述

函数调用:(不分类)

def partition( pivot, lst ):
    less, same, more = list(), list(), list()
    for val in lst:
        if val < pivot:
            less.append(val)
        elif val > pivot:
            more.append(val)
        else:
            same.append(val)
    return less, same, more


def medianOf3(lst):
"""
From a lst of unordered data, find and return the the median value from
the first, middle and last values.
"""
    finder=[]
    start=lst[0]
    mid=lst[len(lst)//2]
    end=lst[len(lst)-1]
    finder.append(start)
    finder.append(mid)
    finder.append(end)
    finder.sort()
    pivot_val=finder[1]
    return pivot_val

主要代码

def quicheSortRec(lst,limit):
"""
A non in-place, depth limited quickSort, using median-of-3 pivot.
Once the limit drops to 0, it uses heapSort instead.
"""
    if limit==0:
        return heapSort.heapSort(lst)
    else:
        pivot=qsPivotMedian3.medianOf3(lst)        # here we select the first element as the pivot
        less, same, more = qsPivotMedian3.partition(pivot, lst)
        return quicheSortRec(less,limit-1) + same + quicheSortRec(more,limit-1)


def quicheSort(lst):
"""
The main routine called to do the sort.  It should call the
recursive routine with the correct values in order to perform
the sort
"""
    N=len(lst)
    end= int(math.log(N,2))
    if len(lst)==0:
        return list()
    else:
        return quicheSortRec(lst,end)

所以这段代码应该采用一个列表并使用快速排序的中位数 3 对其进行排序，直到达到深度递归限制，此时函数将改为使用堆排序.这段代码的结果是然后输入另一个程序，用于测试长度为 1,10,100,1000,10000,100000 的列表的算法.

so this code is supposed to take a list and sort it using a median of 3 implementation of quicksort, up until it reaches a depth recursion limit, at which point the the function will instead use heapsort.the results of this code are then fed into another program designed to test the algorithm with lists of length 1,10,100,1000,10000,100000.

然而，当我运行代码时，告诉我长度 1 和 10 工作正常，但在那之后，它给出了一个列表索引越界错误

however, when I run the code, tells me that lengths 1 and 10 work fine, but after that, it gives an list index out of bounds error for

start=lst[0] 3 函数的中位数

start=lst[0] in the median of 3 function

我不知道为什么.

推荐答案

没有看到您的测试数据，我们就在这里盲目飞行.在一般，

Without seeing your test data, we're flying blind here. In general,

less, same, more = qsPivotMedian3.partition(pivot, lst)

本身没问题，但您永远不会检查 less 或 more 以查看它们是否为空.即使它们是空的，它们也会通过以下方式传递:

is fine on its own, but you never check less or more to see whether they're empty. Even if they are empty, they're passed on via:

    return quicheSortRec(less,limit-1) + same + quicheSortRec(more,limit-1)

和 quicheSortRec() 也不检查它们是否为空:它无条件地调用:

and quicheSortRec() doesn't check to see whether they're empty either: it unconditionally calls:

pivot=qsPivotMedian3.medianOf3(lst)  

如果它传递了一个空列表，该函数将引发您看到的错误.请注意，您的 quicheSort() 确实 检查空输入.递归工作函数也应该如此.

and that function will raise the error you're seeing if it's passed an empty list. Note that your quicheSort() does check for an empty input. The recursive worker function should too.

顺便说一句，考虑一下对 medianOf3() 的重写:

BTW, consider this rewrite of medianOf3():

def medianOf3(lst):
    return sorted([lst[0], lst[len(lst)//2], lst[-1]])[1]

这是一种更简洁的情况;-)

This is one case where brevity is clearer ;-)

这篇关于python 3中值3快速排序实现，在满足递归深度限制后切换到堆排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！