时间戳

首页 > 解决方案 > 快速排序的 C 实现在 arr[0] 处产生垃圾值

c - 快速排序的 C 实现在 arr[0] 处产生垃圾值

问题描述

考虑以下算法：

void qsort(int arr[], int left, int right) {
        if (left < right) {
        int index = partition(arr, left, right);
        qsort(arr, left, index - 1);
        qsort(arr, index + 1, right);
    }
}

int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            ++i;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[right]);
    return i + 1;
}

inline void swap(int* i, int* j) {
    int temp = *i;
    *i = *j;
    *j = temp;
}

修复段错误后，我注意到该算法总是在arr[0]. 因此，如果输入数组是：5 5 1 3 7 0 0 0 3，则输出是-858993460 0 0 0 1 3 3 5 5。我已经通过调试器多次运行它，但我仍然不知道垃圾值来自哪里。更有趣的是，在 Java 中几乎相同的算法可以完美运行。

编辑 初始函数是这样调用的：qsort(arr, 0, 9);其中 9 是数组的长度 - 1。

标签： cquicksort

解决方案

我怀疑您在初始化arr或调用qsort(). 可能在数组的开头或结尾使用垃圾（未初始化）元素调用它。7这也可能解释了为什么输出中缺少最大值。

如果我进一步推测，我猜想在 Java 中，数组被初始化为零，所以你在输出中得到一个额外的零（也许你在其他零中忽略了？）

编辑：初始函数是这样调用的：qsort(arr, 0, 9);其中 9 是数组的长度 - 1。

对于您的示例，这9显然不正确，因此这是一个错误。它将解释垃圾元素，但不考虑丢失的元素。

我的下一个假设是，对一个十元素数组（9 个实数 + 1 个垃圾）进行排序后，您只打印出前九个元素。这将解释7您的输出中的缺失（它是最大的，因此被放置在最终位置，即没有被打印出来的位置）。

PS 如果我可以为未来的问题提供一些不请自来的建议，发布一个最小的、完整的和可验证的示例将使所有这些猜测调试完全没有必要，因为我们可以立即看到你的代码到底发生了什么. :)

推荐阅读