递归分区排序效率低下

Question

我已经为分区排序编写了递归方法来对数组进行排序，但是当我使用超过 10-20 个元素的数组时，程序需要很长时间才能完成（在我的计算机上，冒泡排序100,000 个 int 数组大约需要 15-20 秒，但是只有 30 个 int 的数组，我的分区排序需要大约 45 秒才能完成排序。

这是代码。

public static int[] partitionSortRecursive(int[] array, int beginning, int end)
{
    if (end < beginning)
        return array;

    int pivot = (array[beginning] + array[end]) / 2;
    int firstUnknown = beginning;
    int lastS1 = beginning - 1;
    int firstS3 = end + 1;


    while (firstUnknown < firstS3)
    {
        if (array[firstUnknown] == pivot)
        {
            firstUnknown++;
        }
        else if (array[firstUnknown] > pivot)
        {
            firstS3--;
            int temp = array[firstUnknown];
            array[firstUnknown] = array[firstS3];
            array[firstS3] = temp;
        }
        else
        {
            lastS1++;
            int temp = array[firstUnknown];
            array[firstUnknown] = array[lastS1];
            array[lastS1] = temp;
            firstUnknown++;
        }

    }

    partitionSortRecursive(array, 0, lastS1);
    partitionSortRecursive(array, firstS3, end);

    return array;
}

Answer 1

而不是像这样直接递归调用

partitionSortRecursive(array, 0, lastS1);
partitionSortRecursive(array, firstS3, end);

组织可以保存索引对的内部堆栈。当堆栈不为空时，从堆栈中获取下一对。在函数的最后不要调用同一个函数，而是在堆栈中放入 2 对 (0, lastS1) 和 (firstS3, end)

Answer 2

您没有使用正确的枢轴元素。您计算左右值的平均值，但您必须从子数组中取一个样本值来进行分区。

您可以选择最右边、中间或任何其他元素。所以你的第一行代码应该是这样的

int pivot = array[(beginning + end) / 2];
// or
int pivot = array[end];

您也可以采用任何其他元素（例如随机）

编辑：这不能解决性能问题。

据我了解，快速排序会将数组分为两个子数组A和B，其中A中的所有元素都小于B中的任何元素，然后对两个子数组执行相同的操作。

所以基本的调用结构应该是这样的

void DoSort (array, i, j)
{
  pivot = Partition (array, i, j)
  DoSort (array, i,pivot)
  DoSort (array, pivot + 1, j)
}

把你的实现基本上是

void DoSort (array, i, j)
{
  pivot = Partition (array, i, j)
  DoSort (array, 0, pivot)     // <<<<<< notice the '0' instead of 'i'
  DoSort (array, pivot + 1, j)
}

所以你总是从原始数组的开头开始，这很可能需要一段时间

递归分区排序效率低下

Recursive Partition Sort is Acting Ineffecient

java

sorting

quicksort