为什么我的快速排序效率如此低下

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()，所以它对所有仍然。 这肯定是你看到的症状的原因。

Answer 2

这一行是错误的：

sortShit(left, intVec.size() - 1);

递归的其他一些分支负责在rightValue+1和intVec.size()-1之间进行排序。 您只需要使用

sortShit(left, rightValue);

它恢复了递归调用始终在连续较小的集合上并因此终止的不变性。

您的呼叫允许右侧集的大小增长，因此不能保证终止。