如何定义一个返回升序元组的 sort_tuple

Question

我需要定义一个叫做'sort_tuple'的函数，这个函数接收一个元组，并返回一个按升序排列的元组。（我不能在代码中使用内置的sorted函数或.sort方法）

注意：代码应该使用insert_tuple函数：

def insert_tup(x, tup):
    b = search(x, tup)
    left = tup[:b]
    right = tup[ b:]
    new_tup = left + (x,) + right
    return new_tup

def search(x, seq):
    for i in seq:
        if x<i:
            return seq.index(i)
        elif x == i:
            return seq.index(i)
        elif x>seq[-1]:
            return (seq.index(seq[-1]))+1

测试结果：

>>> sort_tuple((5, 0, -1, 4, -2))
(-2, -1, 0, 4, 5)

这是我的答案：

def sort_tuple(tup):
    for i in range(len(tup)):
       if tup[i-1] > tup[i]:
            removed_tup = tup[0:i-1] + tup[i: len(tup)]
            new_tup = insert_tup(tup[i-1], removed_tup)
    return new_tup

但是这个代码出错了，因为当我输入这个表达式时：

sort_tuple((5, 0, -1, 4, -2))

输出应该是升序的：(-2, -1, 0, 4, 5)，但我的输出却是(4, 5, 0, -1, -2)。

Answer 1

你可能应该做一种插入排序：

def sort_tuple(t):
    result = () # start with an empty result
    for val in t:
        result = insert_tup(val, result) # insert each value into its place
    return result

这个方法效率不是特别高，但用你手头的函数来实现非常简单。

虽然上面的代码看起来很简单，但在这个情况下，它只是碰巧能工作，因为当传入一个空元组时，search函数表现得很糟糕（返回None）。幸运的是，tup[:None]是一个合法的切片。在它出现的特定情况下，甚至是正确的！

一个更好的search实现应该总是返回一个整数。这里有个简单的尝试：

def search(x, seq):
    for i, v in enumerate(seq):
        if x < v:
            return i
    return len(seq)

或者更好的是，使用bisect模块来进行搜索，这样可以在O(log n)的时间内完成，而不是O(n)。