GeeksForGeeks问题的快速排序算法

Question

我在GeeksForGeeks网站上有一个关于快速排序算法的问题:https://www.geeksforgeeks.org/python-program-for-quicksort/

快速排序由GeeksForGeeks上的划分函数组成，如下所示:

def partition(arr, low, high):
i = (low-1)         # index of smaller element
pivot = arr[high]     # pivot

for j in range(low, high):

# If current element is smaller than or
# equal to pivot
if arr[j] <= pivot:

# increment index of smaller element
i = i+1
arr[i], arr[j] = arr[j], arr[i]

arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)

我想知道为什么i被设置为i = low - 1。

为什么不能这样重写函数(注意所有的i):

def partition(arr, low, high):
i = low
pivot = arr[high]

for j in range(low, high):

if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[high] = arr[high], arr[i]
return i

Answer 1

您的快速排序实现工作。有多个正确的快速排序实现。我猜是GeeksForGeeks选择了这个实现，但是他们为什么选择它呢?

你得问这篇文章的作者。

我认为你的问题提出了一个很好的观点，即算法可以以不同但相似的方式实现。

我很快写了一个脚本来测试你的快速排序实现版本。

def partition(arr, low, high):
i = low        # index of smaller element
pivot = arr[high]     # pivot

for j in range(low, high):

# If current element is smaller than or
# equal to pivot
if arr[j] <= pivot:

# increment index of smaller element
arr[i], arr[j] = arr[j], arr[i]
i = i+1

arr[i], arr[high] = arr[high], arr[i]
return i


def quickSort(arr, low, high):
if len(arr) == 1:
return arr
if low < high:

# pi is partitioning index, arr[p] is now
# at right place
pi = partition(arr, low, high)

# Separately sort elements before
# partition and after partition
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)


# Driver code to test above
arr = []
for i in range(0, 10000):
import random
r = random.randint(-100000,100000)
arr.append(r)
n = len(arr)
quickSort(arr, 0, n-1)
# using naive method to 
# check sorted list 
flag = 0
i = 1
while i < len(arr):
if(arr[i] < arr[i - 1]):
flag = 1
i += 1

# printing result
if (not flag) :
print ("Sorted")
else :
print ("Not sorted")
print(arr)

Answer 2

这都是关于效率的，通过在low处启动i，在low处启动j，您在循环的第一次运行中针对自身测试值，这在数组排序的范围内绝对没有做任何事情。

要改变这种情况并保持效率，您必须更改quickSort方法的实现(如调用partition的方法)，但这样做最终会在两次递归调用之间多次接触相同的索引，这再次降低了效率。

快速排序是关于速度的(因此得名)。你所做的改变，绝对不会破坏算法，但是当你扩大输入时，它确实会降低它的速度。