c++ - 快速排序错误，可能是关闭 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);

withleft=0和right=1第一个if-statement 将评估为

    if(0 >= 1-1)
        return;

并且该函数将在不交换两个元素的情况下返回，即使列表显然未排序。