我正在尝试用Python实现3路分区快速排序代码。
我的代码有两行:
我的代码适用于以下输入:
但是,当使用以下输入进行测试时: 10, 10 9 8 7 6 5 4 3 2 1
我的代码无法正确对整数数组进行排序?
我可以知道为什么我的代码不适用于最后一种情况吗?
这是我的代码:
def partition3(a, l, r):
#write your code here
pivot = a[r]
i = l
j = l - 1
iterable_length = r
while i <= iterable_length:
if a[i] < pivot:
j += 1
a[i], a[j] = a[j], a[i]
elif a[i] > pivot:
a[i], a[iterable_length] = a[iterable_length], a[i]
iterable_length -= 1
i += 1
return j, iterable_length+1
def randomized_quick_sort(a, l, r):
if l >= r:
return
k = random.randint(l, r)
a[l], a[k] = a[k], a[l]
#use partition3
# m = partition2(a, l, r)
m1, m2 = partition3(a, l, r)
randomized_quick_sort(a, l, m1);
randomized_quick_sort(a, m2, r);
if __name__ == '__main__':
input = sys.stdin.read()
n, *a = list(map(int, input.split()))
randomized_quick_sort(a, 0, n - 1)
for x in a:
print(x, end=' ')
问题似乎出在这里:
k = random.randint(l, r)
a[l], a[k] = a[k], a[l]
您将获得一个随机索引
k
并使用它随机交换两个元素 a[l]
和 a[k]
。 删除这两行 我假设您正在寻找创建一个随机枢轴点,在这种情况下,您应该使用随机索引作为
partition3
函数内的枢轴。
编辑: 问题不是在
a[i]
内部交换后处理/跳过 a[i] > pivot:
处的新元素。应该是:
elif a[i] > pivot:
a[i], a[iterable_length] = a[iterable_length], a[i]
iterable_length -= 1
# don't forget to process new element at a[i]
i -= 1