Python 中的霍尔分区方案

Question

我将 Hoare 分区方案从 Wikipedia article 翻译成 Python:

这是我的代码：

def partition(nums, low, high):
  pivot = nums[(high + low) // 2]
  i = low - 1
  j = high + 1

  while True:
    i += 1
    j -= 1

    while nums[i] < pivot:
      i += 1
    while nums[j] > pivot:
      j -= 1

    if i >= j:
      return j

    nums[i], nums[j] = nums[j], nums[i]    


nums = [14801, 338, 6389, 3209, 4825, 10818, 1768, 7669, 4545, 10930, 11810]
pivot_1 = partition(nums, 0, len(nums) - 1)
print(pivot_1)  # 6 ---> this should be 7, no?
print(nums)  # [4545, 338, 6389, 3209, 4825, 7669, 1768, 10818, 14801, 10930, 11810]

pivot_2 = partition(nums, 0, 6)
print(pivot_2)  # 2 ---> this looks ok
print(nums)  # [1768, 338, 3209, 6389, 4825, 7669, 4545, 10818, 14801, 10930, 11810]

我做错了什么？为什么我的代码没有返回正确的枢轴位置？

Answer 1

我不熟悉 python 语法，但在 java 中我按如下方式实现

private static int partition(int[] arr, int low, int high) {
        int pivot = arr[(low+high)/2];
        int i = low-1, j = high+1;
        while(true) {
          do { i++; } while(arr[i] < pivot);
          do { j--; } while(arr[j] > pivot);
          if (i < j) swap(arr, i, j);
          else return j;
        }

它可能会帮助您在 python 中实现相同的逻辑。

Answer 2

this should be 7, no?

没有

正如维基百科代码上方的段落所说：

the pivot's final location is not necessarily at the index that is returned

您误解了返回索引的含义。它只是分区边界，您可以将其用于递归快速排序。

Python 中的霍尔分区方案

Hoare partition scheme in Python

python

sorting

algorithm

quicksort