我正在尝试在Python中实现3路分区快速排序代码。
我的代码有2行:
- 第一个是要排序的整数个数
- 第二个是要排序的整数数组
我的代码适用于以下输入:
- 8、1、3、5、4、2、6、4、4
- 5, 2 3 9 2 2
然而,当使用以下输入进行测试时: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=' ')
欢迎使用StackOverflow。问题似乎在这里:
k = random.randint(l, r)
a[l], a[k] = a[k], a[l]
你得到一个随机索引k
,并使用它来交换两个元素a[l]
和a[k]
随机。删除两行应该给出正确的输出只在某些情况下看起来是正确的。
我假设你正在寻找创建一个随机枢轴点,在这种情况下,您应该使用随机索引作为partition3
函数中的枢轴。
编辑:问题不是在a[i] > pivot:
内部交换后在a[i]
处理/跳过新元素。应该是:
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