2

目前试图弄清楚这种问题是什么。直接从 Wikipedia 的就地 Quicksort 伪代码构建，我将假设它是可靠的。我正在尝试按以空字符结尾的 3 字符“代码”字段对结构数组进行排序。

排序主要是有效的，但总是有一些元素不合适。我只能假设这与枢轴有关，但我花了几个小时盯着它看，却一无所获。谢谢！

void quicksort(Cdir *directory, int left, int right) {

    if (left < right) {
        int pivotIdx = left;
        pivotIdx = partition(directory, left, right, pivotIdx);
        quicksort(directory, left, pivotIdx - 1);
        quicksort(directory, pivotIdx + 1, right);
    }
}

int partition(Cdir *directory, int left, int right, int pivot) {

    char *pivotVal = directory[pivot].code;
    int curIdx = left;
    swap(&directory[pivot], &directory[right]);

    int i;
    for (i = left; i < right; i++) {
        if (strncmp(directory[i].code, pivotVal, 3) < 0) {
            swap(&directory[i], &directory[curIdx]);
            curIdx++;
        }
    }
    swap(&directory[curIdx], &directory[right]);
    return curIdx;
} 

void swap(Cdir *s1, Cdir *s2) {

    Cdir temp = *s1; 
    *s1 = *s2;
    *s2 = temp;
}
4

4 回答 4

3

我只是想说...请不要将此视为您问题的实际答案，因为事实并非如此。

作为一名程序员，你几乎将所有的时间都花在自己解决问题上。这是一个开始学习如何做到这一点的机会。如果你养成了通过实验找出程序为什么会以某种方式运行的习惯，那么你将成为一个比仅仅询问人们哪里出了问题的程序员更好的程序员。

盯着代码可以让你到达一个点，但你不会总是在没有看到实际使用的数据的情况下超过那个点。这就是调试的全部内容：知道你的程序在哪里，它在做什么，以及它的变量包含什么。

调试代码最简单的技术就是printf告诉你发生了什么。

想象一下，如果您的程序输出如下内容：

Quicksorting on range 1 to 6
Partitioning on range 1 to 6
  Sub-array before:
    bob
    nelly
    harold
    yasmine
    fred
    roger
  Sub-array after:
    (you get the idea)
Partition returned pivot index of 5
Quicksorting on range 1 to 4
  (etc etc)

嗯，它可以。插入几个调用很容易printf，突然间你会从程序中得到大量输出，然后将其写入文件然后查看。如果发生了什么愚蠢的事情，很快就会变得很明显，并且只需要一点时间就可以在代码中添加一些跟踪并重新编译。

快乐编码。

于 2013-01-30T14:02:06.840 回答
2

您在 partition(..) 的这一行中有一个错误：

for (i = left; i < right - 1; i++)

维基百科中的代码假定循环中包含 right-1，应该是 <=。

于 2013-01-30T05:56:10.310 回答
2

我终于弄明白了。当我将字符串比较中的“pivotVal”替换为对枢轴值（目录[right]）的直接引用时，排序工作正常。仍在试图确定为什么会这样，但它是固定的！

void quicksort(Cdir directory[], int left, int right) {

    if (left < right) {
        int pivotIdx = left;
        pivotIdx = partition(directory, left, right, pivotIdx);
        quicksort(directory, left, pivotIdx - 1);
        quicksort(directory, pivotIdx + 1, right);
    }
}

int partition(Cdir directory[], int left, int right, int pivot) {

    int curIdx = left;
    swap(&directory[pivot], &directory[right]);

    int i;
    for (i = left; i < right; i++) {
        if (strncmp(directory[i].code, directory[right].code, 3) < 0) {
            swap(&directory[i], &directory[curIdx]);
            curIdx++;
        }
    }
    swap(&directory[curIdx], &directory[right]);

    return curIdx;
} 

void swap(Cdir *s1, Cdir *s2) {

    Cdir temp = *s1; 
    *s1 = *s2;
    *s2 = temp;
}
于 2013-01-30T15:49:26.127 回答
0

我不认为你应该像 glagolig 建议的那样将 for 循环更改为 i <= right 因为 swap(pivot, right) 和 i < right 的目的是从数组中删除枢轴并处理更小的数组 1 元素。该算法对我来说看起来完全正确，也许问题在于您如何调用该函数。
您应该使用正确的参数调用函数作为数组中的最后一个索引而不是数组的大小，即如果您有 Cdir arr[10]; 你应该调用 quicksort(arr, 0 ,9);
如果您发布错误输出的输入示例，您也可以帮助人们更多地帮助您。
我会将此添加为评论，但我没有足够的代表这样做:-)

于 2013-01-30T13:53:26.103 回答