0

在我的课上，我们的老师希望我们用 C 语言编写一个快速排序算法，该算法适用于 10000 的数组int。我和我的朋友已经编写了伪代码上所见的代码。

对随机值数组进行排序时它可以正常工作，但是在对排序后的数组进行排序时，代码会崩溃。

Unhandled exception at 0x00FF2509 in ConsoleApplication1.exe: 0xC0000005: Access violation writing location 0x00330F58.

现在我搜索了一下，发现链接器为递归函数提供了 1MB 的堆栈（不过我可能弄错了）。因此，对于 4 字节整数变量（再次排序排序数组时将是 4x10k 个）和一个 10k int 引用数组，它应该占用大约 200KB 的堆栈。

所以我不知道为什么会出现这个错误。老师告诉我们，（当然）可以将该代码编写为伪代码。所以要么我在代码上做错了什么，要么我不知道。

任何人都可以请帮助解释什么是错的？

void quicksort_last(int *A,int p,int r){

if(p<r){
    int q=partition(A,p,r);
    quicksort_last(A,p,q-1);
    quicksort_last(A,q+1,r);
}
}

int partition(int *A,int p, int r){
const int x=A[r];
int i=p-1;
int j=p;
int temp;

while(j<r){
    if(A[j]<=x){
        i++;
        temp=A[i];
        A[i]=A[j];
        A[j]=temp;
    }
    j++;
}
temp=A[i+1];
A[i+1]=A[r];
A[r]=temp;
return i+1;
}

编辑：这是调试给出的错误。调试在分区函数开始时停止大约第 4000 次递归。剩下的代码在这里。

ConsoleApplication1.exe 中 0x00BF2509 处的未处理异常：0xC00000FD：堆栈溢出（参数：0x00000001、0x002B2FA8）。

4

3 回答 3

0

如果您的异常状态访问冲突，您为什么会想到堆栈限制？您的代码中肯定存在一个错误，导致您写入不属于您的应用程序的禁止内存。你在调试器中运行过吗？它至少应该告诉您错误发生在哪个迭代中。

于 2013-10-26T14:27:59.083 回答
0

好吧，我做的最后一件事是我应该做的第一件事（像往常一样）

void plusplus(int a){
    printf("%d\n",a);
    plusplus(a+1);
}

int main(){
    plusplus(0);
    return 0;
}

当我运行这段代码时，它会破解大约 4700 次递归。所以我明白了，要么 1 mb 堆栈被填充到第 4700 深度，要么存在限制（我怀疑）。

感谢您的时间和帮助大家;）

于 2013-11-02T11:04:11.597 回答
0

概要

您对算法的转录和实现似乎没问题；它对我有用，没有问题。

您需要仔细检查驱动程序代码，以确保您没有超出任何数组的界限。您可能会在该驱动程序代码中发现问题。

分析

在对您显示的排序和分区代码进行了一些研究之后，我认为它没有什么大问题。我使用了以下测试用例，但在 Mac OS X 10.9 上使用 GCC 4.8.2 进行测试。它使用-std=c11（以及其他选项严格选项）编译，并使用for添加到 C99 的两个特性——“在循环中声明变量”特性和“在需要时声明变量”特性。如果您不使用支持 C99 的编译器，则可以直接修复这些问题。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static void dump_partition(char const *tag, int *array, int lo, int hi)
{
    if (lo < hi)
    {
        int i;
        printf("%s: %d..%d\n", tag, lo, hi);
        for (i = lo; i <= hi; i++)
        {
            printf(" %4d", array[i]);
            if ((i - lo) % 10 == 9)
                putchar('\n');
        }
        if ((i - lo) % 10 != 0)
            putchar('\n');
    }
}

static int partition(int *A, int p, int r)
{
    const int x=A[r];
    int i=p-1;
    int j=p;
    int temp;

    while (j < r)
    {
        if (A[j] <= x)
        {
            i++;
            temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
        j++;
    }
    temp=A[i+1];
    A[i+1]=A[r];
    A[r]=temp;
    return i+1;
}

static void quicksort_last(int *A, int p, int r)
{
    if (p < r)
    {
        int q=partition(A, p, r);
        printf("quicksort: %p (%d..%d)\n", (void *)&q, p, r);
        //dump_partition("L-part", A, p, q-1);
        //dump_partition("R-part", A, q+1, r);
        quicksort_last(A, p, q-1);
        quicksort_last(A, q+1, r);
    }
}

int main(void)
{
    int data[] =
    {
        31, 14, 53, 45, 88,  0, 79, 59, 84,  5,
        83, 42, 61, 38, 24, 47, 86, 69,  8, 36,
    };
    enum { N_DATA = sizeof(data) / sizeof(data[0]) };

    dump_partition("Random", data, 0, N_DATA-1);
    quicksort_last(data, 0, N_DATA-1);
    dump_partition("Sorted", data, 0, N_DATA-1);

    enum { BIG_SIZE = 10000 };
    int data2[BIG_SIZE];
    srand(time(0));
    for (int i = 0; i < BIG_SIZE; i++)
        data2[i] = rand() % BIG_SIZE;

    dump_partition("Random", data2, 0, BIG_SIZE-1);
    quicksort_last(data2, 0, BIG_SIZE-1);
    dump_partition("Sorted", data2, 0, BIG_SIZE-1);

    return 0;
}

该dump_partition()功能允许我监控分区中的内容。当注释掉的那些处于quicksort_last()活动状态时，它让我看到分区工作正常。printf()打印地址的给出q堆栈深度的度量。在我的机器上，运行的输出：

qs | grep quicksort: | sort -u -k2,2

曾是：

quicksort: 0x7fff555f66f0 (3962..3963)
quicksort: 0x7fff555f6730 (3961..3963)
quicksort: 0x7fff555f6770 (3961..3965)
quicksort: 0x7fff555f67b0 (1214..1215)
quicksort: 0x7fff555f67f0 (1197..1198)
quicksort: 0x7fff555f6830 (1151..1152)
quicksort: 0x7fff555f6870 (1150..1152)
quicksort: 0x7fff555f68b0 (865..867)
quicksort: 0x7fff555f68f0 (435..436)
quicksort: 0x7fff555f6930 (433..436)
quicksort: 0x7fff555f6970 (20..21)
quicksort: 0x7fff555f69b0 (20..22)
quicksort: 0x7fff555f69f0 (20..23)
quicksort: 0x7fff555f6a30 (20..28)
quicksort: 0x7fff555f6a70 (20..29)
quicksort: 0x7fff555f6ab0 (20..30)
quicksort: 0x7fff555f6af0 (1..2)
quicksort: 0x7fff555f6b30 (1..4)
quicksort: 0x7fff555f6b70 (0..4)
quicksort: 0x7fff555f6bb0 (0..6)
quicksort: 0x7fff555f6bf0 (0..11)
quicksort: 0x7fff555f6c30 (0..18)
quicksort: 0x7fff555f6c70 (0..93)
quicksort: 0x7fff555f6cb0 (0..138)
quicksort: 0x7fff555f6cf0 (8..9)
quicksort: 0x7fff555f6d30 (7..9)
quicksort: 0x7fff555f6d70 (3..4)
quicksort: 0x7fff555f6db0 (0..1)
quicksort: 0x7fff555f6df0 (0..5)
quicksort: 0x7fff555f6e30 (0..19)

最大堆栈深度为：

  0x7fff555f6e30
- 0x7fff555f66f0
  --------------
  0x000000000740

小于 2 KiB。堆栈上有 28 个级别。那是随机数据（显示的代码）。当我修改代码以对已排序的数据进行排序时，使用的堆栈要大得多——正如我在评论中指出的那样，这导致分区中的行为非常糟糕。

如果您的输入数据已经排序，则选择子数组的第一个元素作为枢轴值会导致二次排序和非常深的递归。最好随机选择一个枢轴，或使用三的中位数或相关技术。

堆栈上共有 9999 个级别，堆栈位置的差异为：

  0x7fff5d0bde30
- 0x7fff5d021ab0
  --------------
  0x000000013074

但是，使用的堆栈空间仍然少于 80 KiB（在排序代码中；数组的空间是额外的，但这是一个已知数量，大约 40 KiB）。这些尺寸都不应该对普通机器造成压力。

因此，我必须诊断问题不是您在问题中显示的代码。令人惊讶的是，事实往往如此。

您可以通过获取我的驱动程序代码（main()可能还有dump_partition()函数）并使用您的quicksort_last(). 你应该找到与我得到的结果相似的结果。如果是这种情况，您可以开始编写驱动程序代码。我看了看它并决定我不想仔细检查它——事实上，最初发布的代码对我来说根本无法编译。它似乎也有大量重复的代码，这总是一个不好的迹象。当我做了足够多的工作让它编译无警告（这意味着打印出仔细计算的时间，在很大程度上，但也有其他问题），然后我得到的输出是：

 0.000787
 0.156366
 0.000001
 0.031464
 0.000001
 0.040427
 0.001198
 0.597619
 0.000001
 0.121826
 0.000000
 0.159727
 0.001914
 1.335059
 0.000001
 0.275667
 0.000002
 0.358740
 0.002504
 2.381662
 0.000000
 0.487816
 0.000000
 0.645867

%13.6f这是使用格式字符串打印时间。同样，它没有在 Mac OS X 10.9 上崩溃。我没有在这段代码中测量堆栈使用情况。

于 2013-10-26T19:32:32.340 回答