2

Python で挿入ソートを実装しましたが、アルゴリズムの複雑さを判断する方法を知りたいと思っていました。これは挿入ソートを実装する非効率的な方法ですか? 私には、これが最も読みやすいアルゴリズムのように思えます。

import random as rand
source = [3,1,0,10,20,2,1]
target = []
while len(source)!=0:
 if len(target) ==0:
  target.append(source[0])
  source.pop(0)
 element = source.pop(0)
 if(element <= target[0]):
  target.reverse()
  target.append(element)
  target.reverse()
 elif element > target[len(target)-1]:
  target.append(element) 
 else:
  for i in range(0,len(target)-1):
   if element >= target[i] and element <= target[i+1]:
    target.insert(i+1,element)
    break
print target
4

4 に答える 4

2

それ以外の：

target.reverse()
target.append(element)
target.reverse()

試す：

target.insert(0, element)

また、while ループの代わりに for ループを使用して、source.pop()?:

for value in source:
  ...

最後の else ブロックでは、if テストの最初の部分が冗長です。

else:
   for i in range(0,len(target)-1):
     if element >= target[i] and element <= target[i+1]:
        target.insert(i+1,element)
        break

リストは既にソートされているため、挿入する要素よりも大きな要素が見つかったら、挿入場所を見つけたことになります。

于 2013-03-05T21:26:02.893 に答える
1 
def insertionsort( aList ):
  for i in range( 1, len( aList ) ):
    tmp = aList[i]
    k = i
    while k > 0 and tmp < aList[k - 1]:
        aList[k] = aList[k - 1]
        k -= 1
    aList[k] = tmp

このコードは g eekviewpoint.comから取得したものです。2 つのループを使用していることから、明らかにO(n^2)アルゴリズムです。ただし、入力が既にソートされている場合は、失敗のO(n)ためwhile-loopに常にスキップされるためです。tmp < aList[k - 1]

于 2013-03-06T00:50:51.170 に答える