为什么我的快速排序挂了？

Question

我正在从一个文件（它只是一个随机整数的小列表（100 个元素））读入一个向量并尝试使用快速排序对其进行排序，但它挂断了。快速排序函数最终在我在代码中注释的地方无限重复 i = 0，j = 30，left = 31 和 right = 30。

#include <iostream>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <vector>

using namespace std;

void quicksort(vector<size_t> &fileV, size_t left, size_t right);
void swap(size_t &a, size_t &b);

int main(int argc, char* argv[]){
    if (argc != 2){
        cout << "error: quicks <file name> "<< endl;
        return 1;
    }

    fstream file;
    file.open(argv[1]);
    if (!file.is_open()){
        cout << "error: failed to open file " << argv[1] << endl;
        return 1;
    }

    vector<size_t> fileV;
    size_t ranNum;
    size_t i = 0;
    while(file >> ranNum)
        fileV.push_back(ranNum);

    quicksort(fileV, 0, fileV.size());

    file.close();

    return 0;
}

void quicksort(vector<size_t> &fileV, size_t left, size_t right){
    size_t i = left, j = right, center = (left + right) / 2;
    size_t pivot = fileV[center];

    while (i <= j){
        while (fileV[i] <= pivot)
            i++;
        while (fileV[j] > pivot)
            j--;
        if (i <= j){
            swap (fileV[i], fileV[j]);
            i++;
            j--;
        }
    }

    //repeats infinitely with i = 0, j = 30, left = 31 and right = 30

    if (left < j) 
        quicksort(fileV, left, j);
    if (i < right) 
        quicksort(fileV, i, right);
}

void swap(size_t &a, size_t &b){
    size_t t = a;
    a = b;
    b = t;
}

Answer 1

你的分区算法步骤错误。例如，假设我们从：

开始

[1, 2, 3, 2, 8, 9]
 ^i    ^center  ^j

我们进入 while 循环，它首先将 i 向上移动第一个大于 3 的元素（8），然后 j 向下到第一个小于等于3的元素（最后一个2）：

[1, 2, 3, 2, 8, 9]
          ^j ^i

此时，没有交换发生，我们认为我们的分区完成了。这是错误的：我们需要交换 2 和 3。不管它为什么最终在某个地方无限循环，这个实现没有希望产生正确的答案。

为什么我的快速排序挂了？

Why is my quick sort hanging up?

c++

sorting

vector

quicksort