快速排序算法一旦第一个枢轴位于数组中的最终位置，下一步是什么？

Question

目前正在尝试了解 QuickSort 算法是如何运行的，然后再将它实现到代码中，我有未排序的数组：

{7,8,2,5,1,9,3,6}

在这道题的例子中，数组中最右边的元素被选为基准，6。我已经遍历了数组，将每个元素与 6(pivot) 进行了比较，并根据数组元素是小于还是大于 6，执行了适当的操作。结果，现在所有小于 6 的值都在左边，所有大于 6 的值都在右边数组现在看起来像这样

{2,5,1,3,6,7,9,8}.

正如许多教程所述，我们现在基本上有两个较小的数组

{2,5,1,3} and {7,9,8}

我被困在下一步该做什么上，因为每个不同的教程都会选择不同的支点，因此很难理解。我会在我的两个较小的阵列中再次做同样的事情吗？

如果有人能告诉我如何对 {2,5,3,1} 数组进行排序并解释你是如何做到的，那就太好了，我会自己做 {7,9,8}。

Answer 1

获得第一个枢轴的位置后，您需要在两个线段上执行相同的操作。递归调用左右段的方法。

现在对您的两个子集 {2,5,1,3} 和 {7,9,8} 进行分区。您将在 {2,5,1,3} 上选择 3 作为支点，并为第一段获得 {2,1} 和 {5}，并对另一段执行类似操作。

{2,5,1,3} 
       ^
{2,1,3,5}
     ^
pivot (3) at proper position. do the same on left and right segments.

{2,1} and {5}
   ^

{1,2,3,5}

Answer 2

QuickSort 的工作方式是通过递归过程，这就是您描述的过程。对两个结果数组应用相同的过程，你会没事的。

澄清一下，此算法的基本情况是输入数组的大小为 1，从而生成排序数组。

Answer 3

以下动画演示解释了如何在数组中查找枢轴值。

枢轴值将列表分为两部分。递归地，我们找到每个子列表的枢轴，直到所有列表只包含一个元素。

实现QuickSort算法的步骤：

第 1 步 - 选择最高的索引值作为主元（可以是任何索引）

第 2 步 - 取两个变量指向列表的左侧和右侧，不包括 pivot

第 3 步 - 左指向低索引

第 4 步 - 右指向高点

第 5 步 - 当左边的值小于枢轴向右移动时

第 6 步 - 当右侧的值大于枢轴向左移动时

第 7 步 - 如果第 5 步和第 6 步都不匹配左右交换

步骤 8 − 如果 left ≥ right，他们相遇的点是新的 pivot

上述算法的伪代码可以推导为-

function partitionFunc(left, right, pivot)
   leftPointer = left -1
   rightPointer = right

   while True do
      while A[++leftPointer] < pivot do
         //do-nothing            
      end while

      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing         
      end while

      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if

   end while 

   swap leftPointer,right
   return leftPointer

end function

快速排序算法

递归地使用枢轴算法，我们最终得到更小的可能分区。然后处理每个分区以进行快速排序。我们定义快速排序的递归算法如下 -

第 1 步 - 使最右边的索引值成为主元

第 2 步 - 使用枢轴值对数组进行分区

第 3 步 - 快速排序左分区递归

第 4 步 - 递归快速排序右分区

快速排序伪代码

为了更深入地了解它，让我们看看快速排序算法的伪代码 -

procedure quickSort(left, right)

   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   end if       

end procedure

Answer 4

快速回答：

I am stuck here on what to do next, as every different tutorial picks a different pivot point making it hard to follow.

可以通过多种不同方式选择枢轴，甚至可以随机选择。快速排序的平均性能为 O(n*log n)，但最坏情况为 O(n^2)。根据选择基准的方式，该算法在对某些 "end-case" 数组进行排序时更可靠，因此其性能为 O(n^2) 的情况的数量较少。

快速排序算法一旦第一个枢轴位于数组中的最终位置，下一步是什么？

QuickSort Algorithm what is next step once first pivot is located its final position in the array?

java

arrays

algorithm

quicksort