随机打乱数组并使用快速排序算法

Question

我一直在尝试写一个代码来随机打乱数组元素，然后对数组元素使用快速排序算法。这是我写的代码：

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void randomise(int arr[], int s, int e)
{
    int j;
    srand(time(NULL));
    for (int i = e; i >= s; i--)
    {
        int j = rand() % (i + 1);
        swap(&arr[i], &arr[j]);
    }
}
int Partition(int arr[], int s, int e)
{
    int pivot = arr[e];
    int i = s - 1;
    int j;
    for (j = s; j <= e; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[e]);
    return i + 1;
}
void QuickSort(int arr[], int s, int e)
{
    if (s >= e)
        return;
    int x = Partition(arr, s, e);
    QuickSort(arr, s, x - 1);
    QuickSort(arr, x + 1, e);
}
int main()
{
    int b[] = {1, 2, 3, 4, 5};
    randomise(b, 0, 4);
    cout << "Elements of randomised array are:";
    for (int i = 0; i <= 4; i++)
    {
        cout << b[i] << endl;
    }
    QuickSort(b, 0, 4);
    cout << "Elements after quick sort are:";
    for (int i = 0; i <= 4; i++)
    {
        cout << b[i] << endl;
    }
    return 0;
}

然而，在GDB上调试时，我发现这个程序给出了段错误。执行时，该程序的输出为：

Elements of randomised array are:4
5
2
3
1

谁能告诉我这段代码中的错误是什么（我已经尝试在 GDB 上调试它，但我仍然一无所知）。

Answer 1

基本上，当错误是segmentation fault时，你应该寻找一个在找到之后你会想撞墙的错误。在第 26 行，将 <=, 更改为 < 。它在你的分区函数中。 for (j = s; j < e; j++) 关于快速排序的一些解释；每次对分区执行快速排序函数运行s 后，分区的最后一个元素（称为主元）将到达其在数组中的实际位置。分区函数，returns是数组中pivot的真实位置。然后主数组将被分成两个分区，在枢轴位置之前和之后。你的错误是 returning real-pivot-place + 1，作为分区函数的输出。所以你会运行在错误的分区上快速排序；已经排序的分区，但由于分区错误，程序将不断尝试对其进行排序。你可能知道，每次你运行一个函数，它的变量将被保存到计算机的堆栈中。由于您一遍又一遍地调用递归函数（不应该停止），因此该堆栈将变满并溢出。之后，计算机将表现出一些未定义的行为，并可能抛出无法正确描述问题的异常。这就是您出现分段错误的原因。但是为什么你 return real-pivot-place + 1？因为在分区函数的 for 循环中，您也会访问数据透视表，这是您不应该访问的。因为不应该将 pivot 与自身进行比较。所以你会不必要地增加 i 变量。 https://en.wikipedia.org/wiki/Call_stack检查此 link 以获取有关堆栈的更多信息以及函数运行在计算机中的作用。

随机打乱数组并使用快速排序算法

Randomly Shuffle an array and using quick sort algorithm

c++

sorting

debugging

quicksort

segmentation-fault