将数组严格分为两部分，其中左半部分元素小于右半部分元素

Question

我需要根据中间值midval将数组A [n]分为两个子数组A1，A2，使得A1（或表示为left）的所有元素都小于midval，并且A1的所有元素都小于midval A2（或表示为右侧）大于（midval）。

我正在实施的第一个分区阶段的参考：https://thescipub.com/pdf/jcssp.2008.897.902.pdf

我编写了这段代码，它可以工作，但它没有严格地将其分开，左半部分小于右半部分。

        int pivot = data.Length / 2;

        // Find the max and min values for left and right parts
        int Lmax = int.MinValue, Lmin = int.MaxValue, Rmax = int.MinValue, Rmin = int.MaxValue;
        for (int i = 0; i < pivot; i++)
        {
            if (data[i] > Lmax)
                Lmax = data[i];
            if (data[i] < Lmin)
                Lmin = data[i];
        }
        for (int i = pivot; i < data.Length; i++)
        {
            if (data[i] > Rmax)
                Rmax = data[i];
            if (data[i] < Rmin)
                Rmin = data[i];
        }

        // Calculate midval
        int midval = (Lmax + Lmin + Rmax + Rmin) / 4;

        // Perform swaps
        for (int i = 0, j = data.Length - 1; i < pivot && j >= pivot;)
        {

            if (data[i] >= midval && data[j] < midval)
            {
                int temp = data[i];
                data[i] = data[j];
                data[j] = temp;
                i++;
                j--;
            }
            else if(data[i] < midval)
            {
                i++;
            }
            else if(data[j] >= midval)
            {
                j--;
            }
        }

我正在计算 midval 值，该值必须始终大于或等于左半部分中的所有值，并且小于右半部分中的所有数组元素。在我交换左半部和右半部的元素之后：如果左半部的元素大于 midval，则右半部的元素如果小于 midval。

通过这种方式，它以正确的方式交换元素，但它不会将数组分成两半，即 0 到 n/2 个元素总是小于 n/2 到 n 个元素。
它停止从两侧接近 n/2 的交换，但停止是因为其中一个指针达到 n/2 的范围，并且一些接近中间的值没有交换。

例如左指针达到n/2并且所有元素都小于midval，但是右指针位于位置n/2+10并且中间我们有10个元素未被检查，并且在这10个元素中我们有那个元素，小于中值。

我认为问题在于中值计算不正确，应该用不同的公式代替，对吗？

Answer 1

使用快速选择来找到线性时间的中点。