对此非常困惑,因为我已经验证了足够小的测试用例 (N = 20) 的正确逻辑输出。我尝试做 N = 10,000 个数字,但程序只是挂起,我不明白为什么......我已经尽可能简单地实现了算法。
此外,在我的 N = 10k 列表上调用 sorted(data)
似乎几乎立即起作用。所以我确信我的算法只是卡在了某个地方。
代码如下:
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
所以我很困惑为什么会发生这种情况。感谢您的帮助。
最佳答案
下面这行似乎有错别字:
qsort(arr, 0, newPivotIndex)
我觉得应该是这样的。
qsort(arr, left, newPivotIndex)
否则该函数将仅对某些输入数据集起作用。这就是算法卡住的原因。
关于python - Python 中的 QuickSort - 程序挂起较大的输入大小?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11698947/