时间戳

首页 > 解决方案 > 随机打乱数组并使用快速排序算法

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

问题描述

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

#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 上调试它，但我仍然一无所知）。

标签： c++sortingdebuggingsegmentation-faultquicksort

解决方案

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

推荐阅读