快速排序是一种遵循分而治之策略的排序算法。它的工作原理是选择一个枢轴元素，然后通过执行交换来围绕枢轴排列元素。它递归地重复这个过程，直到数组排序完毕。
在本教程中，我们将学习 QuickSort 的工作原理以及如何为其实现编写 Python 代码。
了解快速排序算法
对数组执行快速排序的第一步是选择主元。选择枢轴元素的方法有多种。
您可以选择随机元素，也可以选择数组的中值。为简单起见，我们将选择数组的第一个元素作为主元元素。
1. 选择透视元素
如上所述，第一个元素被选为枢轴元素。
pivot = array[start] |
选择一个枢轴元素后，我们需要重新排列它周围的元素。我们重新排列元素，使所有小于主元的元素都在左侧，所有大于主元的元素都在右侧。
我们如何做到这一点？
我们接下来讨论一下。
2.围绕Pivot重新排列元素
为了重新排列枢轴周围的元素，我们初始化两个变量。
我们将这些变量称为低变量和高变量。
我们用数组的第二个元素（主元之后的一个）初始化 low，用最后一个元素初始化 high。
low = start + 1high = end |
为了重新排列元素，我们将低值向右移动，将高值向左移动。这样做的目的是确保所有大于主元的值都应向右移动，所有小于主元的值应向左移动。
当我们以这种方式排列值时，我们可以找到枢轴元素在排序数组中的最终位置，因为所有小于枢轴的元素都在其左侧，而右侧的所有元素都较大。
枢轴右侧和左侧的元素可以按排序方式排列，也可以不按排序方式排列。
3、如何低走高走？
我们向左移动高点，直到高点指向小于枢轴的值或直到高点小于低点。
while low <= high and array[high] >= pivot: high = high - 1 |
类似地，我们向右移动低点，直到它指向高于枢轴的值或直到高点小于低点。
while low <= high and array[low] <= pivot: low = low + 1 |
退出循环后，我们检查 low 是否小于或等于 high。如果是这种情况，那么我们需要交换高值和低值。
if low <= high: array[low], array[high] = array[high], array[low] |
如果 low 大于 high，我们将跳出循环并返回 high 作为枢轴元素的位置。这意味着我们已经成功地将值排列在枢轴周围。
4. 到目前为止已实现的代码
下面给出了负责选择枢轴元素然后重新排列元素的函数的完整代码：
def pivot(array, start, end):#initializing pivot = array[start] low = start + 1 high = end while True: #moving high towards left while low <= high and array[high] >= pivot: high = high - 1#moving low towards right while low <= high and array[low] <= pivot: low = low + 1#checking if low and high have crossed if low <= high:#swapping values to rearrange array[low], array[high] = array[high], array[low] else:#breaking out of the loop if low > high break#swapping pivot with high so that pivot is at its right # #position array[start], array[high] = array[high], array[start]#returning pivot position return high |
5. 对数组的两半进行递归调用
在围绕枢轴重新排列元素后，我们需要对数组的两半进行递归调用。
这些调用将重复进行，直到我们拥有大小为 1 的数组。进行递归调用的函数代码如下：
def quick_sort(array, start, end): if start >= end: return#call pivot p = pivot(array, start, end)#recursive call on left half quick_sort(array, start, p-1)#recursive call on right half quick_sort(array, p+1, end) |
最后两条语句分别在左半部分和右半部分进行递归调用。
对于左半部和右半部重复选择枢轴并围绕其重新排列元素的相同过程。
当我们重复执行此操作时，我们确保每个元素都放置在正确的位置。
这里，“正确位置”意味着所有较小的元素都在左侧，所有较大的元素都在右侧。当所有元素都放置在正确的位置时，我们得到一个排序数组。
快速排序数组的示例
让我们举一个例子来测试我们的代码。
[5,1,3,9,8,2,7] |
让我们添加一些代码来打印每个递归调用的枢轴元素、数组的左半部分和右半部分。
def quick_sort(array, start, end): if start >= end: return p = pivot(array, start, end) print("Pivot",array[p]) print("left :", array[start:p]) print("right :",array[p+1:end+1]) print("\n") quick_sort(array, start, p-1) quick_sort(array, p+1, end) |
让我们使用上面的示例数组运行代码。
array = [5,1,3,9,8,2,7]quick_sort(array, 0, len(array) - 1)print(array) |
输出如下：
Pivot 5left : [2, 1, 3]right : [8, 9, 7]Pivot 2left : [1]right : [3]Pivot 8left : [7]right : [9][1, 2, 3, 5, 7, 8, 9] |
我们可以看到，对于每个主元元素，左侧数组包含小于主元的元素，右侧数组包含大于主元的元素。
从视觉上看，我们可以将递归调用表示如下：
完成实施
快速排序的完整实现如下：
def pivot(array, start, end):#initializing pivot = array[start] low = start + 1 high = end while True: #moving high towards left while low <= high and array[high] >= pivot: high = high - 1#moving low towards right while low <= high and array[low] <= pivot: low = low + 1#checking if low and high have crossed if low <= high:#swapping values to rearrange array[low], array[high] = array[high], array[low] else:#breaking out of the loop if low > high break#swapping pivot with high so that pivot is at its right # #position array[start], array[high] = array[high], array[start]#returning pivot position return highdef quick_sort(array, start, end): if start >= end: return#call pivot p = pivot(array, start, end)#recursive call on left half quick_sort(array, start, p-1)#recursive call on right half quick_sort(array, p+1, end)array = [5,1,3,9,8,2,7]quick_sort(array, 0, len(array) - 1)print(array) |
结论
本教程是关于在 Python 中实现快速排序。快速排序的最坏情况时间复杂度为 O(n 2 )，平均情况时间复杂度为 O(n logn)。