快速排序抛出堆栈溢出错误

Question

好的，所以我的整个程序如下所示。出于某种原因，当调用分区函数时，它会抛出堆栈溢出错误。我倾注了代码并寻求帮助。你们这些优秀的程序员是我最后的希望。其他一切工作正常，或者至少和它需要的一样好。如果你能帮我看看快速排序和分区函数，看看你能不能找出我搞砸的地方，我将不胜感激。

    #include <iostream>
    #include <string>
    #include <fstream>
    #include <vector>
    #include <time.h>
    #include <stdio.h>
    #include <dos.h>

using namespace std;

vector<int> DataIn(ifstream&);

void quickSort(int, int, vector<int>&, int);

int partition(vector<int>& list, int start, int end)
{
    int pivot = list[start];
    int index = start;

    for (int i = start + 1; i < end; i++)
    {
        if (list[i] <= pivot)
        {
            swap(list[index], list[i]);
        }
    }

    index++;

    if (index != end)
    {
        swap(list[index], list[start]);
    }
    return index;
}

void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

int main()
{
    int repeat = 0;
    int fileCount = 1;

    while (repeat == 0)
    {

        int loadFail = NULL;

        cout << "\nWhat is the file name: ";

        string fileName;
        cin >> fileName;

        ifstream fileIn(fileName);

        do
        {
            if (fileIn.fail())
            {
                loadFail = 1;
                cout << "\nUnable to open file. Please try again:";

                cout << "\nWhat is the file name: ";

                cin >> fileName;
                ifstream fileIn(fileName);

                if (fileIn.good())
                {
                    loadFail = 0;
                }
            }
            else
            {
                loadFail = 0;
            }
        } while (loadFail == 1);

        vector<int> fileData;

        fileData = DataIn(fileIn);

        int fileLength = fileData.size();

        void quickTime = quickSort(0, fileLength - 1, fileData, fileCount);


    return 0;
};

vector<int> DataIn(ifstream& read)
{
    vector<int> data;
    int dataLine;

    while (!read.eof())
    {
        read >> dataLine;
        read.ignore();
        data.push_back(dataLine);
    }

    return data;
}

void quickSort(int begin, int end, vector<int>& list, int fileNum)
{    
    int mid = 0;

    if (end > begin)
    {       
        mid = partition(list, begin, end);
        quickSort(begin, mid, list, fileNum);
        quickSort(mid + 1, end, list, fileNum);
    }

    return elapsed_time;    
}

Answer 1

您发布的代码中存在一些重大问题。

您正在尝试 return void 函数 (quickSort) 中的一个值。我也看不到你在哪里声明了那个变量。
您正在声明类型为 void 的变量，这是错误的。 void 函数 return void，这意味着它没有 return 任何东西。
main() 函数末尾缺少一个括号。
你的while循环永远不会停止，因为repeat总是等于0。
在你的快速排序函数中，在第一次递归调用中应该有 mid-1
你的分区函数逻辑错误

另外，filenum 变量没有在任何地方使用。

这是您的代码的修改版本，确实有效。

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <time.h>
#include <stdio.h>
#include <dos.h>

using namespace std;

vector<int> DataIn(ifstream&);

void quickSort(int, int, vector<int>&);

int partition(vector<int>& arr, int left, int right)
{
    int pivot = arr[left];
    while (left != right)
    {
        if (arr[left] > arr[right])
        {
            swap(arr[left], arr[right]);
        }
        if (pivot == arr[left])
            right--;
        else 
            left++;
    }
    return left;
}

void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

int main()
{
    int repeat = 0;
    int fileCount = 1;

        int loadFail = NULL;

        cout << "\nWhat is the file name: ";

        string fileName;
        cin >> fileName;

        ifstream fileIn(fileName);

        do
        {
            if (fileIn.fail())
            {
                loadFail = 1;
                cout << "\nUnable to open file. Please try again:";

                cout << "\nWhat is the file name: ";

                cin >> fileName;
                ifstream fileIn(fileName);

                if (fileIn.good())
                {
                    loadFail = 0;
                }
            }
            else
            {
                loadFail = 0;
            }
        } while (loadFail == 1);

        vector<int> fileData;

        fileData = DataIn(fileIn);

        int fileLength = fileData.size();

        quickSort(0, fileLength - 1, fileData);


        return 0;
}

    vector<int> DataIn(ifstream& read)
    {
        vector<int> data;
        int dataLine;

        while (!read.eof())
        {
            read >> dataLine;
            read.ignore();
            data.push_back(dataLine);
        }

        return data;
    }

    void quickSort(int begin, int end, vector<int>& list)
    {
        int mid = 0;

        if (end > begin)
        {
            mid = partition(list, begin, end);
            quickSort(begin, mid-1, list);
            quickSort(mid + 1, end, list);
        }
    }

快速排序抛出堆栈溢出错误

Quicksort Throws Stack Overflow error

c++

stack-overflow

vector

quicksort