快速排序中的三路划分算法

快速排序算法是计算机科学中一种高效的排序算法,它的核心思想是分而治之。通过选取一个基准值(pivot),算法将数据分为三部分:小于基准值的元素、等于基准值的元素和大于基准值的元素。这种划分逻辑是递归进行的,直到整个数据集被排序。

类似于动态规划算法快速排序算法通过解决子问题来解决复杂问题。在快速排序中,每次划分都是一个子问题,通过递归地解决这些子问题,最终实现整个数据集的排序。

在进行三路划分时,算法会将数据分为三组:小于基准值的元素、等于基准值的元素和大于基准值的元素。这种算法通常是原地进行的,这意味着它部分地对数据进行了排序。这种特性可以应用于多种问题,例如:

  • 排序一个只包含0、1和2的数组
  • 荷兰国旗问题
  • 先打印所有负整数,然后打印所有正整数
  • 先打印所有0,然后打印1,或者反过来,对于一个只包含0和1的数组
  • 将所有0移动到数组的末尾,同时保持其他元素的相对顺序

如果算法不是原地进行的(即不改变原始数据),那么它将需要额外的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)
沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485