Python 霍尔分区算法(Hoare‘s Partition Algorithm)

目录【方法】——霍尔数组划分算法——时间复杂度为 O(n)空间复杂度为 O(1)一些有趣的事实如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定一个数组arr[]任务是以第一个元素为枢轴元素对数组进行分区。数组的划分必须满足以下两个条件小于枢轴元素的元素必须出现在小于或等于分区索引的索引处。大于或等于枢轴元素的元素必须出现在大于分区索引的索引处。分区索引等于元素个数严格小于枢轴元素个数减一。注意可能存在多个分区数组。例如输入arr[] [5, 3, 8, 4, 2, 7, 1, 10]输出[1, 3, 2, 4 , 8, 7, 5, 10]说明分区索引为 3枢轴元素为 5所有小于枢轴元素的元素 [1, 3, 2, 4] 排列在分区索引之前大于或等于枢轴元素的元素 [8, 7, 5, 10] 排列在分区索引之后。输入arr[] [12, 10, 9, 16, 19, 9]输出[9, 10, 9 , 16, 19, 12]说明分区索引为 2枢轴元素为 12所有小于枢轴元素 [9, 10, 9] 的元素都排列在分区索引之前或处大于或等于枢轴元素 [16, 19, 12] 的元素都排列在分区索引之后。【方法】——霍尔数组划分算法——时间复杂度为 O(n)空间复杂度为 O(1)霍尔分区算法是一种围绕枢轴元素对数组进行高效分区的方法。它基于两个指针这两个指针分别从数组的两端出发并向彼此移动直到找到需要交换的元素。算法步骤详解将第一个元素作为枢轴并初始化两个指针分别指向数组的开头和结尾。ij向右移动直到找到大于或等于枢轴的元素向左移动直到找到小于或等于枢轴的元素。ij如果指针指向的元素大于或等于枢轴元素并且指针指向的元素小于或等于枢轴元素则交换这两个元素。ij重复此过程彼此移动并靠近直到相遇或交叉。ij当指针交叉时分区完成小于或等于枢轴的元素在左侧大于或等于枢轴的元素在右侧。示例代码# Function to partition the array according to pivot index elementdef partition(arr):n len(arr)pivot arr[0]i -1j nwhile True:# find next element larger than pivot from the leftwhile True:i 1if arr[i] pivot:break# find next element smaller than pivot from the rightwhile True:j - 1if arr[j] pivot:break# if left and right crosses each other no swapping requiredif i j:break# swap larger and smaller elementsarr[i], arr[j] arr[j], arr[i]if __name__ __main__:arr [5, 3, 8, 4, 2, 7, 1, 10]partition(arr)for num in arr:print(num, end )输出1 3 2 4 8 7 5 10一些有趣的事实霍尔分区算法通常比洛穆托分区算法更快因为它执行的交换次数更少并且只对数组进行一次遍历从而在实践中实现了更好的时间复杂度。它直接在原地工作不需要额外的空间这与使用临时数组的简单分区方法不同。经过适当的调整它可以用来实现快速排序的稳定版本尽管它本身并不稳定。我们可以通过交换第一个元素和最后一个元素然后使用相同的代码轻松地修改算法将第一个元素或任何其他元素视为枢轴。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。