0

我正在为整数编写一个快速排序算法，但在 srand 函数中出现了一个奇怪的段错误。以下是 sort.h 中的代码：

int distributePivot (int *a, int left, int pivot, int right) {
    int i, j;
    if (pivot != right)
        swapInt(&pivot, &right);
    i = left;
    j = right - 1;
    while (i < j) {
        while (i < j && a[i] <= a[right])
            i++;
        while (j > i && a[j] >= a[right])
            j--;
        if (i < j)
            swapInt(&a[i], &a[j]);
    }
    if (i < right)
        swapInt(&a[i], &a[right]);
    return i;
}

void intArrayQuickSort (int *a, int left, int right) {
    int pivot;
    if (left < right) {
            pivot = rand() % (right - left +1) + left;
        pivot = distributePivot(a, left, pivot, right);
        intArrayQuickSort (a, left, pivot -1);
        intArrayQuickSort (a, pivot, right);
    }
}

这是来自 sort-test.c 的调用：

    srand(time(NULL));
    intArrayQuickSort(temp, 0, n - 1);

wheretemp是指向整数的指针。

这是我在 gdb 中执行它时遇到的错误：

    Program received signal SIGSEGV, Segmentation fault.
    0x00007ffff77e9884 in rand () from /lib64/libc.so.6

你能帮我么？

非常感谢。

编辑：这是 swapInt 函数：

void swapInt (int *a, int *b) {
    int aux = *a;
    *a = *b;
    *b = aux;
}
4

4 回答 4

1

程序逻辑有错误。
eg
in main
array = [1,2]
call intArrayQuickSort(array, 0, 1);// a:array, left:0, right:1
in intArrayQuickSort
pivot = 1 //rand() % (right - left +1) + left;
调用distributePivot(a, 0, 1, 1)
indistributePivot
not swap (pivot, right) because pivot == right
i = 0 //left
j = 0 //right - 1
not execute while block because i == j
execute swap (a[i],a [right]) 因为 i < right // 0 < 1
//a = [2, 1] //!!NG
return 0
//已经非法状态
intArrayQuickSort
pivot = 0 ;//从返回值: 0
call intArrayQuickSort ( a, 0, -1);//left:0, pivot -1 :-1
no operation return
call intArrayQuickSort (a, 1, 1);//pivot + 1:1, right : 1
no operation return in main
result:a = [2, 1] //NG！

于 2012-06-09T17:50:16.463 回答
0

实际上我已经找到了解决方案，但我不知道它为什么会起作用。第二个递归调用应该是：

intArrayQuickSort (a, pivot + 1, right);

这对算法有意义，但我不明白为什么 rand() 会出现错误。有什么解释吗？

于 2012-06-09T14:07:10.273 回答
0

我认为修改版 

int distributePivot (int *a, int left, int pivot, int right) {
    int i, j;
    if (pivot != right)
        swapInt(&a[pivot], &a[right]);
    i = left;
    j = right - 1;
    while (1) {
        while (i < right && a[i] < a[right])
            i++;
        while (left <= j && a[j] >= a[right])
            j--;
        if (i < j)
            swapInt(&a[i], &a[j]);
        else
            break;
    }
    if(i < right)
        swapInt(&a[i], &a[right]);
    return i;
}
void intArrayQuickSort (int *a, int left, int right) {
    int pivot;
    if (left < right) {
        pivot = rand() % (right - left +1) + left ;
        pivot = distributePivot(a, left, pivot, right);
        intArrayQuickSort (a, left, pivot - 1);
        intArrayQuickSort (a, pivot + 1, right);
    }
}
于 2012-06-10T07:37:05.467 回答
-1 
pivot = rand() % (right - left +1) + left;

应该：

pivot = left + rand() % (right - left +1);

甚至可能：

pivot = left +1 + rand() % (right - left);
于 2012-06-09T13:13:22.330 回答