0

所以我想为了个人练习，我会在 Python 3.6 中编写一个快速排序算法。算法并不难，而且相当容易理解。为了让事情变得更有趣，我想在原地对其进行排序（不分配与输入一样多的空间）。我意识到这不是真的，因为我仍然分配 log(n) 内存，但这只是因为在调用递归之前变量没有被释放。无论如何，我遇到了一个特殊的问题，我的算法对最多 36 个元素的数组进行排序，不会失败而且速度很快。但是，当我尝试对长度为 37 及以上的数组进行排序时，它突然陷入无限递归循环并在 1000 次递归后崩溃。

有人可以指出我的问题吗？我似乎找不到它。

randomnumbers = [160,51,77,32,53,44,83,116,128,170,190,192,192,117,28,32,9,17,136,146,47,67,20,196,41,122,17,13,11,176,198,79,166,71,114,44]#,116]#,167,200,159,50,76,71,198,157,116,124,83,149,37]
 #is the array one element shorter is suddenly works WTH?!

def quicksort (array, begin, final, o):
  pivotposition = 0

  if(final-begin==1):
    if(array[begin]>array[final]):
        #print("bla")
        temp = array[begin]
        array[begin] = array[final]
        array[final] = temp
    return
  elif(final-begin<1):
    return
  else:
    import random
    pivotposition = begin#random.randint(begin, final)

  pivot = array[pivotposition]
  start = begin
  end = final
  endfirst = 0
  print(o) #debugging print statement to check for the recursion depth
            #can be taken out without consequence
  while(start!=end):

    if(array[start]>pivot):
        if(pivotposition==end):
            pivotposition = start
        temp = array[start]
        array[start] = array[end]
        array[end] = temp
        end = end -1
    else:
        start = start + 1

  if(array[start]>pivot):
    endfirst=start-1
  else:
    endfirst=start

  lur = array[endfirst]
  array[endfirst] = array[pivotposition]
  array[pivotposition]= lur

  quicksort(array,begin,endfirst,o+1)
  quicksort(array,endfirst+1, final,o+1)

#-------------------------------------------------------
print(randomnumbers)
quicksort(randomnumbers, 0, len(randomnumbers)-1,0)
print(randomnumbers)

input("press Enter")
4

0 回答 0