迭代就地快速排序

Question

我已经在Python中实现了一个迭代的就地快速排序算法，默认情况下，它选择pivot作为最后一个元素：

def quicksort(array):
    """
    Sorts an array of integers using the quick-sort algorithm.

    :param array: the array to be sorted
    :type array: list<int>
    :return: the sorted array
    :rtype: list<int>
    """
    indexes_stack = list()
    idx = (0, len(array) - 1)
    indexes_stack.append(idx)
    for idx in indexes_stack:
        elem_idx = idx[0]
        pivot_idx = idx[1]
        while pivot_idx > elem_idx:
            pivot = array[pivot_idx]
            elem = array[elem_idx]
            if elem > pivot:
                array[pivot_idx] = elem
                array[elem_idx] = array[pivot_idx - 1]
                array[pivot_idx - 1] = pivot
                pivot_idx -= 1
            else:
                elem_idx += 1

        boundar_low = idx[0]
        boundar_high = idx[1]
        if pivot_idx > 1 and boundar_low < pivot_idx - 1:
            indexes_stack.append((boundar_low, pivot_idx - 1))
        if pivot_idx < len(array) -1 and pivot_idx + 1 < boundar_high:
            indexes_stack.append((pivot_idx + 1, boundar_high))

    return array

# Test the sorting function
counter = 0
while counter < 1000:
    test = [int(100 * random.random()) for i in xrange(15)]
    assert (quicksort(list(test)) == sorted(test)), test
    counter += 1

我用各种输入测试过它，它似乎是正确的，但我不知道它是否可以变得更高效或更干净。

Answer 1

即使没有(Y)明确的问题，隐含的发布的代码的任何方面都是反馈和批评的公平游戏。也有理由在CR上提问。我不想猜测任何代码是用来做什么的:为什么会有另一个python快速排序呢？在代码中没有得到回答。

虽然docstring看起来是迷人，但quicksort()的参数被过度指定了:获取和设置item_s和_comparable项所需的所有内容都是“订阅”。(数字项目可以被视为方便地选择几个的平均值作为枢轴。)

代码既没有提到iterative，也没有提到in-place：

应该指定quicksort()来返回其(ordered)参数。

clean，和美一样，都存在于旁观者的眼睛里--对我来说，两者在代码上都很接近。我喜欢蟒蛇，因为它能用最少的时间来表达事情。

(我不太喜欢elem_idx&pivot_idx --有时使用up&down。)

在演示代码中，似乎已经习惯于从_partition_ing中筛选出当前的quicksort()序列。

是真的？代码不使用indexes_stack作为堆栈。至于in-place意味着o(n)空间 (除了输出是过去的输入)，呈现的实现是不到位的。

更有效率？当然-

• 空间:首先处理最小的分区(由于内存不足，这是一个正确性问题)。
• 时间：
  • 选择pivot是关键，使用分区两端的一个值对预先排序的输入是灾难性的。
  • Hoare分区方案而不是Lom分析法 -如果需要大量的重复值，可以使用三种方法
  • 最好不要使用少于两个项:对小分区使用不同的算法
  • 不要将优先级最高的分区立即弹出。

代替进一步的咆哮(保留elem，elem_idx和pivot_idx作为识别值)：

# non-recursive quicksort - re-inventing the wheel finger exercise 

# docs.python.org tutorial:
# To add an item to the top of the stack, use append()
class stack(list):
    ''' push() to add an item to the top of the stack '''
    push = list.append


# non-recursive quicksort
def quicksort(items):
    """
    Sort a sequence using the quick-sort algorithm.

    :param items: the sequence to be sorted
    :return: items, sorted
    """
    nItems = len(items)
    if nItems < 2:
        return items
    todo = stack([(0, nItems - 1)])
    while todo:
        elem_idx, pivot_idx = low, high = todo.pop()
        elem = items[elem_idx]
        pivot = items[pivot_idx]
        while pivot_idx > elem_idx:
            if elem > pivot:
                items[pivot_idx] = elem
                pivot_idx -= 1
                items[elem_idx] = elem = items[pivot_idx]
            else:
                elem_idx += 1
                elem = items[elem_idx]
        items[pivot_idx] = pivot

        lsize = pivot_idx - low
        hsize = high - pivot_idx
        if lsize <= hsize:
            if 1 < lsize:
                todo.push((pivot_idx + 1, high))
                todo.push((low, pivot_idx - 1))
        else:
            todo.push((low, pivot_idx - 1))
        if 1 < hsize:
            todo.push((pivot_idx + 1, high))
    return items


if __name__ == '__main__':
# run the sorting function
    from random import randint
    for _ in range(99):
        test = [str(randint(0, 100)) for _ in range(randint(15, 99))]
        assert (quicksort(test[:]) == sorted(test)), test