0

我创建了两个函数，它们将整数从最低值排序到最高值，然后再回到最低值。这种类型的排序存在吗？无论如何，我创建了以下两个排序函数，它们产生相同的输出。我想知道两者中哪个效率最高？有什么我可以做的改进吗？

  1. sortMiddleMax1
    • 创建一个新的反向排序的原始列表
    • 从索引 1 开始到列表长度逐步增加 2
  2. sortMiddleMax2
    • 就地对列表进行排序
    • 从最后一个索引开始到 0 逐步 2

我试图让第二个比第一个更有效率。我没有在内存中创建新列表，而是将其附加到末尾，而不是向右推动整个列表。我在这个假设中正确吗？

功能

def sortMiddleMax1(aList=None, verbose=False):
  if aList == None or len(aList) < 2:
    return aList
  else:
    sList = sorted(x, key=None, reverse=True)
    if verbose: print sList
    index = 1
    while index < len(sList):
      tmp = sList[index]
      del sList[index]
      sList.insert(0, tmp)
      index+=2
      if verbose: print sList
    return sList

def sortMiddleMax2(aList=None, verbose=False):
  if aList == None or len(aList) < 2:
    return aList
  else:
    aList.sort()
    if verbose: print aList
    index = len(aList)-1
    while index > 0:
      tmp = aList[index]
      del aList[index]
      aList.append(tmp)
      index-=2
      if verbose: print aList
    return aList

主要的

x = [1,4,6,8,3,5,7,1,5,8,3,9,2,8]
print '############# sortMiddleMax1 #############'
x1 = sortMiddleMax1(x, True)
print '############# sortMiddleMax2 #############'
x2 = sortMiddleMax2(x, True)

输出

############# sortMiddleMax1 #############
[9, 8, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1]
[8, 9, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1]
[8, 8, 9, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1]
[6, 8, 8, 9, 8, 7, 5, 5, 4, 3, 3, 2, 1, 1]
[5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 3, 2, 1, 1]
[3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 2, 1, 1]
[2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1, 1]
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]
############# sortMiddleMax2 #############
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9]
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9]
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, 8]
[1, 1, 2, 3, 3, 4, 5, 5, 6, 8, 8, 9, 8, 7]
[1, 1, 2, 3, 3, 4, 5, 6, 8, 8, 9, 8, 7, 5]
[1, 1, 2, 3, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4]
[1, 1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3]
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]
4

3 回答 3

1

您可以使用 Python 的扩展切片。[::2]意味着每隔一个元素。[::-2]意味着从最后取出第二个元素并向后工作。这里第一个切片从 0 开始表示偶数长度列表，从 1 开始表示奇数长度列表

>>> x = [1, 4, 6, 8, 3, 5, 7, 1, 5, 8, 3, 9, 2, 8]
>>> x = sorted(x)
>>> x[len(x)%2::2] + x[::-2]
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]
于 2013-02-28T02:54:24.397 回答
1

您可以使用列表切片来获得结果，而无需 for 循环：

x = sorted([1,4,6,8,3,5,7,1,5,8,3,9,2,8])
x2 = x[::2] + x[1::2][::-1]
于 2013-02-28T02:48:39.877 回答
1

我怀疑您的两个当前版本的性能完全相同。但是，它们都可以通过使用切片来获取列表中的值来改进，而不是通过删除和插入值。

每del一个insert都是O(N)，你正在做N/2每一个，所以排序将是O(N^2). 切片也是O(N)如此，但只需要进行两次。排序所花费的时间O(N log N)将逐渐占主导地位。

def sortMiddle3(aList):
    s = sorted(aList) # sort the provided list

    # now take the even indexed items, followed by the odd indexes in reverse
    if len(s) % 2 == 0: # is the number of items even?
        return s[::2] + s[-1::-2] # if so, the last item has an odd index
    else:
        return s[::2] + s[-2::-2]

示例输出：

>>> x = [1,4,6,8,3,5,7,1,5,8,3,9,2,8]
>>> sortMiddle3(x)
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]
于 2013-02-28T02:48:49.237 回答