在编程世界中，大多数问题的答案都可以在存储在各种数据结构中的数据中并借助一些标准算法找到。
今天，我们将讨论快速排序算法以及如何在 Python 中实现它。
在开始确定这些答案之前，您将需要一组数据（在许多情况下是排序数据）来执行进一步的计算。
排序涉及根据某些计算操作来排列数据，最常见的是大于 (>) 或小于 (
它允许以特定方式排列数据，这有助于优化各种以数据为中心的操作，例如搜索。
排序可以用于多种目的，从帮助数据更具可读性到有助于更快和优化的程序。
有多种可用的排序算法可以在 Python 中实现。他们之中有一些是：
这些算法中的每一种都使用不同的方法来执行排序，从而导致不同的时间和空间复杂度。
可以根据程序的要求和资源的可用性来使用其中的每一种。
在列出的算法中，快速排序算法被认为是最fastest因为对于大多数输入，在平均情况下，快速排序被发现是性能最佳的算法。
快速排序算法按照“分而治之”的原理来找到解决方案。
在每个步骤中，我们从数据中选择一个称为“枢轴”的元素，并确定其在排序数组中的正确位置。
迭代结束时，主元左侧的所有元素都小于或等于主元，右侧的所有元素都大于主元。
输入list因此，根据主元值将其划分为左（较小）列表和右（较大）列表。
我们在左右子数组上递归地重复该过程，直到获得排序列表。
不需要额外内存来产生输出，而是“就地”对输入执行操作以产生输出的算法称为“就地算法”。
然而，额外且通常小于线性 (O(n)) 空间的常量空间可用于变量。
在快速排序算法中，由于输入元素被简单地重新排列和就地操作以形成围绕枢轴的“高”和“低”列表，并且使用小的常数空间进行某些计算，因此它是一种就地算法。
让我们将快速排序过程分解为几个步骤。
上述过程可以表示为快速排序的形式化算法。
我们将执行“快速排序”，直到元素出现在列表中。
A=array
start=数组的下界
end = 数组的上限
枢轴=枢轴元素
1. QUICKSORT (array A, start, end)
2. {
3. if (start >= 0 && start >= 0 && start < end)
4. {
5. p = partition(A, start, end)
6. QUICKSORT(A, start, p)
7. QUICKSORT(A, p + 1, end)
8. }
9. }
观察第五步调用了一个名为partition 的函数。
我们将使用这个函数将元素放置在枢轴的两侧。
让我们看一下。
1. PARTITION (array A, start, end)
2. {
3. pivot = A[(start+end)//2]
4. i = start
5. j = end
6. while (True)
7. {
8. do i =i + 1 while A[i]<pivot
9. do j =j - 1 while A[j]>pivot
10. if i>=j then return j
11. swap A[i] with A[j]
12. }
13. }
在分区函数中，我们首先将数组的一个元素（此处为中间元素）分配给主元变量。
变量 i 和 j 用作左指针和右指针，它们迭代数组并用于在需要时交换值。
我们使用 while 循环以及 return 语句来确保整个数组
让我们通过一个例子来理解这个过程。
取数组 A = 3 7 8 5 2 1 9 5 4。
可以选择任何元素作为枢轴，但出于本示例的目的，我采用中间元素。
开始=0，结束=8，i=0，j=8，枢轴=2
由于 a[i]
将 A[i] 与 A[j] 交换，即 3 与 1。
所以 A = 1 7 8 5 2 3 9 5 4，i = 0，j = 5
i=1，j=4，主元=2
由于 a[i]
将 A[i] 与 A[j] 交换，即 7 与 2。
所以 A = 1 2 8 5 7 3 9 5 4，i = 1，j = 4
i=2，j=3，主元=2
由于 a[i]
由于 i=2 > j，退出 while 循环并返回 j=1。
在此步骤中，主元值 2 位于最终排序数组中的正确位置。
现在，我们对两个子数组重复上述步骤，一个子数组的 start=0，end=1，另一个子数组的 start=2，end=8。
让我们首先在 Python 中定义配分函数。
def partition(A, start, end):
i = start-1 #left pointer
pivot = A[(start+end)//2] # pivot
print(f"Pivot = {pivot}")
j = end+1 #right pointer
while True:
i+=1
while (A[i] < pivot):
i+=1 #move left pointer to right
j-=1
while (A[j]> pivot):
j-=1 #move right pointer to left
if i>=j:
return j #stop, pivot moved to its correct position
A[i], A[j] = A[j], A[i]
a = [3,7,8,5,2,4]
print(f"Input array: {a}")
p = partition(a,0,len(a)-1)
print(f"Array after partitioning:{a}")
Output:
请注意枢轴 8 如何从其原始位置 2 移动到最后的正确位置，使得其左侧的所有元素（即 [0:4]）都小于或等于 8。
这种分区技术称为“霍尔分区”，它是更有效的分区方法。
另一种称为“Lomuto 分区”。
现在让我们看一下 Python 中快速排序的完整实现partition功能。
def quickSort(A, start, end):
if start < end:
p = partition(A, start, end) # p is pivot, it is now at its correct position
# sort elements to left and right of pivot separately
quickSort(A, start, p)
quickSort(A, p+1, end)
A = [24, 10, 30, 13, 20, 27]
print(f"Original array A: {A}")
quickSort(A, 0, len(A)-1)
print(f"Array A after quicksort: {A}")
Output:
对于大小为 n 的输入，每一步都会将其分为 k 部分和 n-k 部分。
因此，n 个元素的时间复杂度 = k 个元素的时间复杂度 + n-k 个元素的时间复杂度 + 选择主元的时间复杂度
即 T(n)=T(k)+T(n-k)+M(n)
当选择中间元素作为每个递归循环中的枢轴时，会出现最佳情况的复杂性。
每次迭代时，数组都会被分成大小相等的列表，并且随着重复此过程，排序会以尽可能少的步骤完成。
执行的递归次数将为 log(n)，每一步执行 n 次操作。
因此，可得时间复杂度为O(n(log(n)).
In the worst-case scenario, n number of recursion operations are performed and the time complexity is O(n2).
This can occur under the following conditions:
时间复杂度也可以使用大师定理求出。
平均情况是通过考虑数组的各种排列的时间复杂度的平均值来获得的。复杂度是O(nlog(n)).
上面的实现导致数组按升序排序。
通过交换条件的一些改变，数组也可以按降序排序。
当左侧元素大于枢轴时，不应交换左侧元素，而应在它们小于枢轴时执行交换。
类似地，当右侧元素小于主元时，不应交换它们，而应在它们大于主元时执行交换。
结果，将在其左侧创建大于主元的元素列表，并在其右侧创建小于主元的元素子数组。
最终，数组会按照从左到右从大到小的顺序排列。
def partition_desc(A, start, end):
i = start-1 #left pointer
pivot = A[(start+end)//2] # pivot
j = end+1 #right pointer
while True:
i+=1
while (A[i] > pivot):
i+=1 #move left pointer to right
j-=1
while (A[j]< pivot):
j-=1 #move right pointer to left
if i>=j:
return j #stop, pivot moved to its correct position
A[i], A[j] = A[j], A[i]
a = [3,7,8,5,2,4]
print(f"Input array: {a}")
p = partition_desc(a,0,len(a)-1)
print(f"Array after partitioning:{a}")
Output:
现在，分区步骤可确保将主元移动到最终降序排序数组中的正确位置。
现在让我们看看它的完整快速排序实现。
def quickSort_desc(A, start, end):
if len(A) == 1:
return A
if start < end:
p = partition_desc(A, start, end) # p is pivot, it is now at its correct position
# sort elements to left and right of pivot separately
quickSort_desc(A, start, p-1)
quickSort_desc(A, p+1, end)
A = [24, 10, 30, 13, 20, 27]
print(f"Original array A: {A}")
quickSort_desc(A, 0, len(A)-1)
print(f"Array A after quicksort: {A}")
Output:
在快速排序算法中，分区是就地完成的。
这需要O(1) 空间.
然后对元素进行递归排序，并且对于每个递归调用，使用一个恒定大小的新堆栈帧。
将空间复杂度置于平均情况下为 O(log(n)).
这可以达到最坏情况的 O(n).
到目前为止，我们已经看到了快速排序算法的递归实现。可以通过迭代方法完成相同的操作。
在Python的迭代实现中，执行元素比较和交换的分区函数保持不变。
对快速排序函数中的代码进行了更改，以使用堆栈实现而不是对快速排序函数的递归调用。
这是因为创建了一个临时堆栈并将数组的第一个和最后一个索引放置在其中。
然后，当堆栈不为空时，将元素从堆栈中弹出。
让我们看一下 Python 中的代码实现。
def quickSortIterative(A, start, end):
# Create and initialize the stack, the last filled index represents top of stack
size = end - start + 1
stack = [0] * (size)
top = -1
# push initial values to stack
top = top + 1
stack[top] = start
top = top + 1
stack[top] = end
# Keep popping from stack while it is not empty
while top >= 0:
# Pop start and end
end = stack[top]
top = top - 1
start = stack[top]
top = top - 1
# Call the partition step as before
p = partition( A, start, end )
# If the left of pivot is not empty,
# then push left side indices to stack
if p-1 > start:
top = top + 1
stack[top] = start
top = top + 1
stack[top] = p - 1
# If the right of pivot is not empty,
# then push the right side indices to stack
if p + 1 < end:
top = top + 1
stack[top] = p + 1
top = top + 1
stack[top] = end
A = [9,1,9,2,6,0,8,7,5]
print(f"Input array: {A}")
n = len(A)
quickSortIterative(A, 0, n-1)
print (f"Sorted array:{A}")
Output:
当堆栈不为空时，元素将从堆栈中弹出。
在这个 while 循环中，枢轴元素在分区函数的帮助下移动到正确的位置。
堆栈用于借助第一个和最后一个元素的索引来跟踪低列表和高列表。
从堆栈顶部弹出的两个元素表示子列表的开始索引和结束索引。
对形成的列表迭代执行快速排序，直到堆栈为空并获得排序列表。
当数据集较小时，快速排序算法具有更好的效率。
随着数据集大小的增加，效率会降低，对于较大的数据集，不同的排序算法（例如合并排序）可能会更有效。