谁能解释这个伪代码（分区）

Question

1.can 有人请解释并阅读这段代码吗？这是Searching K-th key Pseudo code，看起来不难，但是我很难理解那几行代码。特别是，我希望你分享你在 partition() 中的处理方式，我知道 reclusive 函数有效，所以你不必解释选择函数，但如果你愿意，你可以这样做..（这是我的第一个问题如果我的问题不明确，请告诉我。)

 keytype selection(index low, index high, index k) {
     index pivotpoint;
     if(low == high)
       return s[low];
     else {
         partition(low, high, pivotpoint);
         if (k == pivotpoint)
           return s[pivotpoint];
         else if (k < pivotpoint)
           return selection(low, pivotpoint-1, k);
         else 
           return selection(pivotpoint+1, high, k-pivotpoint);
         }
   }    

 void partition(index low, index high, index& pivotpoint) { 
     index i,j;
     keytype pivotitem;
     pivotitem = s[low];
     j=low;
     for (i = low+1; i <= high; i++)
      if(s[i] < pivotitem) {
       j++;
       exchange s[i] and s[j];
      }
     pivotpoint = j;
     exchange s[low] and s[pivotpoint];
    }

Answer 1

这是Quickselect算法。

partition的思路是将数组s中的元素在low和high之间划分如下：

它首先选择 pivotitem，在本例中是 s[low]。
循环遍历s（从i=low+1开始），将所有小于pivotitem的元素移动到数组的左边（也是从[=19=开始） ]).
循环结束时，s[low+1,...,j]全部小于pivotitem，s[j+1,...,high]全部大于等于pivotitem。
最后两行将pivotpoint指向j，并将pivotitem移动到那个位置。

总结一下，当函数终止时，变量pivotpoint指向low和high之间的位置，和所有元素low 和 pivotpoint-1 之间的元素小于 s[pivotpoint] 并且 pivotpoint+1 和 high 之间的所有元素都大于或等于 s[pivotpoint].

Answer 2

首先，您正在 select 创建一个枢轴元素。分区后，所有小于枢轴元素的元素都在枢轴左侧，所有大于枢轴的元素都在右侧。您可以 select 任何元素作为枢轴元素。一旦选择了枢轴元素，首先要为枢轴元素分配一个初始位置，在您的情况下该位置较低。然后我们遍历所有元素，看看它们是小于还是大于 pivot 元素。现在出现两种情况：

当a[i] > pivot: 由于(i > j) 始终成立，数组元素已经在pivot元素的右侧
当a[i] < pivot:In 这种情况下，数组元素位于枢轴的右侧并且小于枢轴。所以，我们应该将它移到枢轴的左侧。因此，我们将枢轴元素的位置增加 1，并将较小的元素移至枢轴位置，将较大的元素移至右侧。最后在迭代之后，我们将 pivot 元素的值推到它的位置。

如需进一步参考，请参阅 quick sort。

谁能解释这个伪代码（分区）

can anyone explain this peudo code (partition)

sorting

algorithm

pseudocode