python - Python - 快速排序递归 - 如何解决堆栈溢出？

Question

我正在做一个作业，需要编写一个快速排序函数来根据某个键对（nx 3）矩阵进行排序。

例如，用户输入键 [2,0,1]。这意味着程序必须首先对第三列进行排序，如果有任何相等的值，它会检查第一列来决定排序。如果值仍然相等，则转到第二列。

例子：

key = [2,0,1]

matrix = [["0","1", "1"], ["0","1", "1"], ["1","1", "2"], ["2","0", "1"], ["2","2", "0"]]

预期结果：

[['2', '2', '0'], ['0', '1', '1'], ['0', '1', '1'], ['2', '0', '1'], ['1', '1', '2']]

我使用递归编写了以下代码。它适用于小于 1000 的矩阵。如果我有一个更大的矩阵，由于 Python 约束，它会给我一个堆栈溢出错误。

我抬头发现我可以使用记忆技术来克服这个问题。有谁知道如何在我的代码上实现这样的事情？

def QuickSort (matrix, key, start = 0, end = None):

    if end is None:
        end = len(matrix)-1
    if start < end:
        p = partition(matrix, start, end, key)
        QuickSort(matrix, key, start, p - 1)
        QuickSort(matrix, key, p + 1, end)

    return matrix


def partition (matrix, start, end, ordekeym):

    pivot = matrix[end]
    i = start

    for j in range (start, end):

        if matrix[j][key[0]] < pivot[key[0]]:
            matrix[j], matrix[i] = matrix[i], matrix[j]
            i = i + 1

        if matrix[j][key[0]] == pivot[key[0]] and len(key) == 2:
            if matrix[j][key[1]] < pivot[key[1]]:
                i = i+1

        if matrix[j][key[0]] == pivot[key[0]] and len(key) == 3:
            if matrix[j][key[1]] < pivot[key[1]]:
                i = i + 1
            if matrix[j][key[1]] == pivot[key[1]]:
                if matrix[j][key[2]] < pivot[key[2]]:
                    i = i + 1
                if matrix[j][key[2]] == pivot[key[2]]:
                    break

    matrix[i], matrix[end], = matrix[end], matrix[i]
    return i

print(QuickSort(matrix, key))

标签： pythonoverflowquicksortmemoization