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

Question

目前，在我将快速排序算法实现为代码之前，我正试图了解它是如何运行的，我有一个未排序的数组：

{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}数组进行排序，并解释您是如何进行排序的，那就太好了，我将自己进行排序

Answer 1

以下动画表示说明了如何在数组中查找轴值

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

实现快速排序算法的步骤：

第一步− 选择最高索引值作为轴（可以是任何索引）

步骤2− 取两个变量指向列表的左侧和右侧（不包括轴）

步骤3− 左指低指数

步骤4− 右指向高点

步骤5− 而左侧的值小于“轴向右移动”

步骤6− 当右侧的值大于枢轴时，向左移动

步骤7− 如果第5步和第6步都不匹配，则交换左侧和右侧

步骤8− 如果留下≥ 对，他们相遇的地方是新支点

上述算法的伪码可以导出为−

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

快速排序算法

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

第一步− 使最右边的索引值成为轴

步骤2− 使用pivot值对数组进行分区

步骤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 2

一旦你得到第一个支点的位置，你需要在两段上做同样的事情。递归地调用左段和右段上的方法

现在在两个子集{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 3

快速回答：

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*logn），但最坏的情况是O（n^2）。根据选择枢轴的方式，该算法在对一些“结束案例”数组进行排序时更可靠，因此，其性能为O（n^2）的案例数更小

Answer 4

快速排序的工作方式是通过一个递归过程，即您描述的过程。在两个结果数组上应用相同的过程，您就可以了

只是澄清一下，该算法的基本情况是当输入数组的大小为1时，生成一个排序数组