python - 具有 2 个元素的列表的线性排序

Question

这是我的第一个问题，因此我接受任何/所有提示，以防我的问题措辞不当。

首先，问题是:

假设我们有以下数组 A = [(1,'cat'), (1,'dog'), (0,'giraffe'), (0,'cheetah'),(1,'elephant' )]

我需要使用一种算法，根据每个组件的第一个元素(即数字)对该列表进行排序。特别提到的是，它不一定是一个稳定的算法(我猜意思是我们不需要考虑数字后面单词的排序，只需考虑 0 在所有 1 之前)

我还应该提到，我不希望采用创建侧数组的策略，当算法对它们进行排序时，我将用结果填充这些侧数组。要求算法对同一数组内的数组进行排序。

我设计的代码如下:

def SwapAround(A, start, end):
start_pos = start

for i in range(start,end):
    if A[i] < A[end]:
        A[i], A[start_pos] = A[start_pos], A[i]
        start_pos = start_pos + 1
A[start_pos], A[end] = A[end], A[start_pos]

return start_pos


A=[(1,'cat'),(0,'dog'),(1,'kangaroo'),(0,'mule'),(1,'giraffe'),(1,'dog'), 
(0,'bat')]
SwapAround(A,0,len(A) - 1)
print(A)

我对它有相当特殊的问题，尽管我非常有信心它应该可以工作(至少逐行查看代码，这对我来说很有意义)。

代码对列表进行排序，但不完全...例如，我最近的输出是:

[(0, 'bat'), (0, 'dog'), (1, 'kangaroo'), (0, 'mule'), (1, 'giraffe'), (1, 'dog'), (1, 'cat')]

对于较小的列表，它实际上起作用了，今天早上我醒来向我的列表中添加了更多组件，但它不起作用，我感到很惊讶。

您能否告诉我，您是否可以看到一些我应该考虑的明显“错误”的东西，以及其背后的基本原理，以便我可以完全理解它。

第二个问题:如果我想将包含数字 2 的组件添加到列表中(这意味着我的算法必须在 0,1,2 之间排序，而不仅仅是 0 和 1)，您会使用完全不同的算法吗或者交换仍然有效吗？我最初的想法是交换无法正常工作(并且该算法无法正常工作)，也许 CountingSort 或 RadixSort 会工作得更好，因此我们将非常感谢您的输入。

Answer 1

你的算法在概念上是错误的，尽管它已经接近解决方案。

您的算法的重要问题是只有第一个要交换的元素才会改变。相反，您需要移动最后一个元素和第一个元素的索引。

def sort_binary_key(arr):
    l, u = 0, len(arr) - 1

    while l < u:
        if arr[l] == 1 and arr[u] == 0:
            arr[l], arr[u] = arr[u], arr[l]
        elif arr[l] == 1:
            u -= 1
        elif arr[u] == 0:
            l += 1
        else:
            u -= 1
            l += 1

对于问题的第二部分:
是的，这是可能的。运行上述算法两次。在第一次运行中，将所有带 0 的元素移动到数组的下部，所有其他元素移动到上部。然后对数组的第二部分运行相同的算法，在 1 和 2 作为第一个元组成员的元素之间进行排序。

def sort_binary_key(arr, l, u, key_mapper):
    while l < u:
        al, au = key_mapper(arr[l]), key_mapper(arr[u])

        if al == 1 and au == 0:
            arr[l], arr[u] = arr[u], arr[l]
        elif al == 1:
            u -= 1
        elif au == 0:
            l += 1
        else:
            u -= 1
            l += 1

    return l

def sort_ternary(arr):
    tmp = sort_binary_key(arr, 0, len(arr) - 1, lambda t: 0 if t == 0 else 1)
    sort_binary_key(arr, tmp, len(arr) - 1, lambda t: 0 if t == 1 else 1)

请注意，上述代码仅用于演示。此代码适用于整数列表，而不是 OP 提供的输入。