快速排序的哪个干运行是正确的？使困惑

Question

我正在准备考试，目前正在重新学习快速排序。

假设我应该对数组进行快速排序运行

8,6,2,7,1,4,3,5

我朋友说我做错了，因为在快速排序中它会同时移动索引和交换。所以基本上在我下面做的步骤中，我可以跳过我只移动i, j的步骤。所以他说我需要同时移动和交换。你能说他是对的吗？我觉得还好..请告诉我，因为我现在不确定考试...

我有索引 i 它将遍历数组，直到找到比枢轴元素更大的元素。 j 是低于枢轴元素的索引。 P是枢轴元素。 || 表示元素位于正确的位置，也就是已排序。

8,6,2,7,1,4,3,5
i           j P

3,6,2,7,1,4,8,5
  i       j   P

3,4,2,7,1,6,8,5
  i       j   P

3,4,2,7,1,6,8,5
      i j     P

3,4,2,1,7,6,8,5
      j i     P

3,4,2,1,|5|,6,8,7
      j  P      i

3,4,2,1,|5|,6,8,7
i   j P

3,4,2, 1, |5|,6,8,7
i      Pj

1,4,2, 3, |5|,6,8,7
i      Pj

1,4,2,3,|5|,6,8,7
  i j P

1,2,4,3,|5|,6,8,7
  j i P

1,2,|3|,|4|,|5|,6,8,7
  j  P   i

1, 2, |3|,|4|,|5|,6,8,7
i  Pj

1, 2, |3|,|4|,|5|,6,8,7
j  Pi

|1|, |2|,|3|,|4|,|5|,6,8,7
 j   Pi

|1|,|2|,|3|,|4|,|5|,6,8,7
                    i j P

|1|,|2|,|3|,|4|,|5|,6,8,7
                    j i P

|1|,|2|,|3|,|4|,|5|,|6|,|7|,|8|
                     j   P   i

这是他的版本。比我矮很多，因为他不像我那样多走一步。所以他的步数是我的两倍。你认为正确的是什么？

Answer 1

嗯，从考试的角度来看，我觉得你的版本似乎更合适，因为你在考试中最好每一步都详细说明。

在你朋友的版本中，考官不会对答案很满意，因为没有指示 left(i) 和 right(j) 迭代器以及 pivot 元素。

从实现的角度来看，你们基本上都在做同样的事情，只是你们分别展示了迭代器的移动和值的交换，但是不会改变算法的语义。

仔细一看，其实是一样的：

你

swap(array[i] , array[j])
i = i + 1
j = j - 1

朋友

swap(array[i++] , array[j--])

快速排序的哪个干运行是正确的？使困惑

Which dry run for quicksort is the correct one? Confused

sorting

algorithm

quicksort

快速排序的哪个干 运行 是正确的？使困惑

Which dry run for quicksort is the correct one? Confused

sorting

algorithm

quicksort

快速排序的哪个干运行是正确的？使困惑