c++ - C++随机快速排序SegFault

我正在使用C ++开发“随机快速排序”程序，但是由于某些原因，按程序进行段错误处理，而我对为什么这样做有些迷惑。

我很确定它与我的hoarePartition函数有关，陷入了while循环中，但是我不太确定问题出在哪里。

解决此问题的任何帮助将非常有帮助！

#import <iostream>
#import <cstdlib>
#import <random>
#import <time.h>
#include <ctime>
#include <boost/timer.hpp>

void swap(int& first, int& second)
{
    int temp = first;
    first = second;
    second = temp;
}

int hoarePartition(int* array, int leftIndex, int rightIndex)
{
    int partition = array[leftIndex];
    int i = leftIndex;
    int j = rightIndex + 1;

    while (i < j)
    {
        while (array[i] < partition && i <= j)
        {
            i = i + 1;
        }
        while (array[j] > partition && j > i)
        {
            j = j - 1;
            cout << j << endl;
        }
        swap(array[i], array[j]);
    }

    swap(array[i], array[j]);
    swap(array[leftIndex], array[j]);

    return j;
}

void randomQuickSort(int* array, int leftIndex, int rightIndex)
{
    if (leftIndex < rightIndex)
    {
        int q = rand() % (rightIndex - leftIndex) + leftIndex;
        swap(array[leftIndex], array[q]);
        int s = hoarePartition(array, leftIndex, rightIndex);
        randomQuickSort(array, leftIndex, s-1);
        randomQuickSort(array, s+1, rightIndex);
    }
}

int main(int argc, char** argv)
{
    srand(time(NULL));
    int size = atoi(argv[1]);
    int* array = new int[size];

    for (int i = 0; i < size; ++i)
    {
        array[i] = (100.0 * rand()) / RAND_MAX;
    }

    boost::timer t;
    randomQuickSort(array, 0, size);
    std::cout << t.elapsed() << endl;

    delete[] array;

    return 0;
}

最佳答案

用randomQuickSort = rightIndex调用size，它比数组中最后一个元素的索引大一。然后，将其传递给hoarePartition，将j初始化为rightIndex+1，然后（在第二个内部while循环中）访问array[j]。