c++ - 为什么我的快速排序如此低效？

Question

我从各种在线资源中进行了快速排序，并使用将枢轴置于中心而不是像其他人那样使用第一个或最后一个索引的技术来制作我的。

但是，排序最终会破坏我的程序超过 80 个元素，因为它只是卡住，我假设这是因为它的内存效率低下。

它试图排序的数据绝不是已经排序的并且是完全随机的。

void swapVecPos(int posOne, int posTwo)
{
    int temp = intVec[posOne];
    intVec[posOne] = intVec[posTwo];
    intVec[posTwo] = temp;
}

void sortShit(int leftValue, int rightValue)
{
    int left = leftValue;
    int right = rightValue;
    int pivot = intVec[(leftValue + rightValue) / 2];

    while(left <= right)
    {
        while(intVec[left] < pivot)
        {
            left++;
        }

        while(intVec[right] > pivot)
        {
            right--;
        }

        if(left <= right)
        {
            swapVecPos(left, right);
            left++;
            right--;
        }
    }

    if(leftValue < right)
        sortShit(leftValue, right);

    if(left < rightValue)
        sortShit(left, intVec.size() - 1);
}

谢谢

Answer 1

您的代码中有两个明显的错误。首先，如果有的话时间轴是最小值或最大值(并且如果值是随机的，将在某个时间发生)，你离开您正在处理的分区。如果分区是第一个或最后，这可能会导致未定义的行为，但在任何情况下情况下，它不会给出正确的结果。

第二:当你递归时，第二个递归使用intVect.size()，所以它会调用函数遗迹。这肯定是您所看到的症状的原因。