试图实现以下视频中显示的快速排序技术
试图实现以下视频中显示的快速排序技术
提问于 2022-10-06 15:30:21
这是我指的视频： https://youtu.be/ywWBy6J5gz8
--这是我在python中尝试过的代码：
def partition(arr, low, high):
pivot = arr[low]
i = low + 1
j = high
switch = True
while (True):
while switch == True:
while arr[j] >= pivot and i < j:
j -= 1
pos = arr.index(pivot)
arr[j] , arr[pos] = arr[pos], arr[j]
switch = False
while switch == False:
while arr[i] <= pivot and i < j:
i += 1
pos2 = arr.index(pivot)
arr[i] , arr[pos2] = arr[pos2], arr[i]
switch = True
if i >= j:
return j
def quickSort(arr, low, high):
if high - low >= 1:
pivot = partition(arr, low, high)
quickSort(arr, low, pivot - 1)
quickSort(arr, pivot + 1, high)
arr = [3, 1, 5, 7, 6, 2, 4]
quickSort(arr, 0, len(arr) - 1)
print("Sorted array:")
print(arr)输出：排序数组: 1、2、3、6、4、5、7
我做错什么了？？
回答 1
Stack Overflow用户
回答已采纳
发布于 2022-10-06 16:23:13
您的代码中有几个问题：
- 在视频中，枢轴是两个人中的一员，其中一人走上前，一人戴着黑色的帽子(没有灯光装饰)。在这个过程中没有第三个人，但是您可以将
i和j定义为独立于支点所在的索引的索引。为了协调您的代码与视频，您应该初始化i到low。向前走的两个人在代码中代表i和j。
- 分区实际上应该在
i >= j时结束，但是如果这个条件发生在第一个块中，那么第二个块仍然执行，并在那里执行一个不想要的交换。您应该在i >= j时立即退出该函数。如果你这样编码，你也不再需要这个switch了。
-
arr.index(pivot)的调用是不需要的，也不是高效的，也不是视频所建议的。你已经知道枢轴在哪里了，因为它是两个人中的一个向前走(黑帽)，比如i或i。
以下是修正后的代码：
def partition(arr, low, high):
pivot = arr[low]
i = low
j = high
while True:
while arr[j] >= pivot:
j -= 1
if i >= j:
return i
arr[j], arr[i] = pivot, arr[j]
while arr[i] <= pivot:
i += 1
if i >= j:
return j
arr[i], arr[j] = pivot, arr[i]这现在实现了在视频中显示的内容。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/73976444
复制相关文章
相似问题
腾讯云开发者
