快速排序算法是计算机科学中一种高效的排序算法,它的核心思想是分而治之。通过选取一个基准值(pivot),算法将数据分为三部分:小于基准值的元素、等于基准值的元素和大于基准值的元素。这种划分逻辑是递归进行的,直到整个数据集被排序。
类似于动态规划算法,快速排序算法通过解决子问题来解决复杂问题。在快速排序中,每次划分都是一个子问题,通过递归地解决这些子问题,最终实现整个数据集的排序。
在进行三路划分时,算法会将数据分为三组:小于基准值的元素、等于基准值的元素和大于基准值的元素。这种算法通常是原地进行的,这意味着它部分地对数据进行了排序。这种特性可以应用于多种问题,例如:
如果算法不是原地进行的(即不改变原始数据),那么它将需要额外的O(n)空间。
以排序一个只包含0、1和2的数组为例,首先想到的解决方案是计算0、1和2的数量,然后根据这些数量重置数组。虽然这种方法的时间复杂度是O(n),但它需要两次遍历数组或者使用一个额外的数组。
下面是一个使用线性时间划分算法来避免额外遍历/空间的尝试:
def threeWayPartition(A):
start = mid = 0
end = len(A) - 1
pivot = 1
while mid <= end:
if A[mid] < pivot:
swap(A, start, mid)
start = start + 1
mid = mid + 1
elif A[mid] > pivot:
swap(A, mid, end)
end = end - 1
else:
mid = mid + 1
def swap(A, i, j):
A[i], A[j] = A[j], A[i]
inputArray = [0, 1, 2, 2, 1, 0, 0, 2]
threeWayPartition(inputArray)
print(inputArray)
输出结果为:[0, 0, 0, 1, 1, 2, 2, 2]。通过定义一个基准值,将数据分隔在基准值的两侧,从而得到了期望的输出。荷兰国旗问题或打印所有负数然后正数,或打印所有0然后1,都遵循相同的代码逻辑。
def threeWayPartition(A):
current = 0
nonzero = 0
end = len(A) - 1
pivot = 0
while current <= end:
if A[current] != pivot:
swap(A, current, nonzero)
nonzero = nonzero + 1
current = current + 1
inputArray = [7, 0, 5, 1, 2, 0, 2, 0, 6]
threeWayPartition(inputArray)
print(inputArray)