回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>对此我感到很困惑,因为我已经为足够小的测试用例(N=20)验证了正确的逻辑输出。我试着做N=10000个数字,程序就挂了,我不明白为什么。。。我已经尽可能简单地实现了这个算法。在</p>
<p>另外,在我的N=10k列表上调用<code>sorted(data)</code>似乎可以立即工作。所以我确信我的算法在某个地方卡住了。在</p>
<p>代码如下:</p>
<pre><code>def QuickSort(array):
qsort(array, 0, len(array))
def qsort(arr, left, right):
if ((right - left) < 2):
return
pivotIndex = choosePivot0(arr, left, right)
newPivotIndex = partition(arr, pivotIndex, left, right)
qsort(arr, 0, newPivotIndex)
qsort(arr, newPivotIndex + 1, right)
def partition(arr, pivotIndex, left, right):
swap(arr, pivotIndex, left)
pivot = arr[left]
i = left + 1
for j in range(left+1, right):
if (arr[j] < pivot):
swap(arr, i, j)
i = i + 1
swap(arr, left, i-1) #put pivot back where it belongs
#cobj.count = cobj.count + (right - left - 1) #add m-1 the #of comparisons
return (i-1) #give back where the pivot resides
def swap(array, i, j):
temp = array[i]
array[i] = array[j]
array[j] = temp
def choosePivot0(array, left, right):
return randint(left, right-1) #random
</code></pre>
<p>所以我很困惑为什么会发生这种事。谢谢你的帮助。在</p>