快速排序错误，可能是1个c++错误

Question

尝试编写一个快速排序，并花了一段时间调试。问题似乎是在第二次递归调用，但我不知道我在哪里。任何指针都很棒。谢谢。

void quickSort(vector<int> &list, int left, int right){
    int pivot = left;
    int temp = right;
    if(left >= right - 1)
        return;
    while (left != right) {
        if (pivot == left){
            if (list[pivot] > list[right]) {
                //-------------------------
                int tempList = list[right];
                list[right] = list[pivot];   // Swap for now
                list[pivot] = tempList;
                //-------------------------
                pivot = right;
                left++;
            }else{
                right--;
            }
        }else{
            if (list[pivot] < list[left]) {
                //-------------------------
                int tempList = list[left];
                list[left] = list[pivot];   // Swap for now
                list[pivot] = tempList;
                //-------------------------
                pivot = left;
                right--;
            }else{
                left++;
            }
        }
    }
    quickSort(list, 0, right-1);
    quickSort(list, right + 1, temp);
}

这是我现在创建数据集的方式:

srand(time(0));
vector<int> list;
vector<int> sortedList;
int i;
for (i=0;i<10;i++) list.push_back(rand() %100);

我得到了38 65 26 22 86 64 13 28 57 18的数据集

得到的输出为13 18 22 26 28 38 57 64 86 65

通常是后半部分的元素，但也不是每次都是。

Answer 1

由于您正在访问位置right和left的元素，我假设初始调用如下:

quickSort(list, 0, list.size()-1);

如果列表初始化为vector<int>{ 2, 1 }，第一次调用将计算为

quickSort(list, 0, 1);

对于left=0和right=1，第一个if语句的求值为

    if(0 >= 1-1)
        return;

和函数将不交换两个元素返回，即使列表明显未排序。