0

整数を最小値から最大値にソートし、次に低値に戻す2つの関数を作成しました。このタイプのソートは存在しますか？とにかく、私が作成した次の2つの並べ替え関数があり、同じ出力を生成します。2つのうちどちらが最も効率的か疑問に思いましたか？どちらかを改善することはできますか？

  1. sortMiddleMax1
    • 元の新しい逆ソートリストを作成します
    • インデックス1から開始してリストの長さを2ずつ増やします
  2. sortMiddleMax2
    • リストをインプレースで並べ替えます
    • 最後のインデックスから2ずつ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

リストスライスを使用して、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

現在の2つのバージョンはまったく同じように動作していると思います。ただし、値を削除して挿入するのではなく、スライスを使用してリスト内の値を取得することで、両方を改善できます。

それぞれがdelあり、あなたはそれぞれをやっているので、ソートはになります。スライスも同様ですが、2回だけ行う必要があります。ソートにかかる時間は、漸近的に支配的になります。insertO(N)N/2O(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 に答える
1

Pythonの拡張スライスを使用できます。[::2]毎秒要素を取ることを意味します。[::-2]つまり、最後から1つおきの要素を取り、逆方向に作業します。ここで、最初のスライスは、偶数の長さのリストの場合は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 に答える