C++ 随机快速排序段错误

Question

我正在用 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;
}

Answer 1

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

Answer 2

您正在 hoarePartition 函数中访问 size+1。这是数组超出范围的 2 个元素，导致索引超出范围异常。

C++ 随机快速排序段错误

C++ Random Quick Sort SegFault

c++

sorting

random

quicksort