C 排序算法没有输出正确的值？

Question

这里是 C 的新手。我正在制作一个程序，该程序将出于学习目的对随机整数列表进行排序和搜索，并尝试实施冒泡排序，但在调试期间我的控制台中出现奇怪的结果。

我有一个这样的数组：

arr[0] = 3
arr[1] = 2
arr[2] = 1

因此，如果我要将此列表从最小到最大排序，则应该是相反的顺序。相反，我的排序函数似乎在逻辑上有缺陷，并输出以下内容。

arr[0] = 0
arr[1] = 1
arr[2] = 2

显然我是新手，因为了解更多的人可能会很快发现我的错误。

find.c

/**
 * Prompts user for as many as MAX values until EOF is reached, 
 * then proceeds to search that "haystack" of values for given needle.
 *
 * Usage: ./find needle
 *
 * where needle is the value to find in a haystack of values
 */

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

#include "helpers.h"

// maximum amount of hay
const int MAX = 65536;

int main(int argc, string argv[])
{
    // ensure proper usage
    if (argc != 2)
    {
        printf("Usage: ./find needle\n");
        return -1;
    }

    // remember needle
    int needle = atoi(argv[1]);

    // fill haystack
    int size;
    int haystack[MAX];
    for (size = 0; size < MAX; size++)
    {
        // wait for hay until EOF
        printf("\nhaystack[%i] = ", size);
        int straw = get_int();
        if (straw == INT_MAX)
        {
            break;
        }

        // add hay to stack
        haystack[size] = straw;
    }
    printf("\n");

    // sort the haystack
    sort(haystack, size);

    // try to find needle in haystack
    if (search(needle, haystack, size))
    {
        printf("\nFound needle in haystack!\n\n");
        return 0;
    }
    else
    {
        printf("\nDidn't find needle in haystack.\n\n");
        return 1;
    }
}

helpers.c

#include <cs50.h>

#include "helpers.h"
#include <stdio.h>
/**
 * Returns true if value is in array of n values, else false.
 */
bool search(int value, int values[], int n)
{
    // TODO: implement a searching algorithm
    return false;
}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm
    int tmp = 0;
    int i = 0;
    bool swapped = false;
    bool sorted = false;

    for (int i = 0; i < n; i++)
    {
        printf("%i\n", values[i]);
    }

    while (!sorted)
    {
        //check if number on left is greater than number on right in sequential order of the array.
        if (values[i] > values[i+1])
        {
            tmp = values[i];
            values[i] = values[i+1];
            values[i+1] = tmp;
            swapped = true;
        }
        if (i >= n - 1)
        {
            if (!swapped)
            {
                //No swaps occured, meaning I can assume the list is sorted.
                for (int i = 0; i < n; i++)
                {
                    printf("%i\n", values[i]);
                }
                sorted = true;
                break;
            } else {
                //A swap occured on this pass through of the array.  Set the flag back to false for the next pass through, repeating until no swaps are detected.  (Meaning every number is in its proper place.)
                i = 0;
                swapped = false;
            }
        } else {
            i++;
        }
    }
}

Answer 1

您可以在数组 0..n-1 中交换的最高条目是 n-2 和 n-1。所以 i 可能不会大于 n-2 所以 i+1 访问 n-1.

因此您的支票必须是：

if (i > n - 2)

Answer 2

问题是您在进行测试 if (i >= n - 1) 之前 进行了比较和交换 。这意味着它将在 i == n-1 时比较 values[i] > values[i+1]，因此它将访问数组边界之外，这是未定义的行为。在你的例子中，数组后面的内存中恰好有 0，所以它被交换到数组中，然后它被排序到数组的开头。

改变

    if (values[i] > values[i+1])

至

    if (i < n-1 && values[i] > values[i+1])

C 排序算法没有输出正确的值？

C Sort Algorithm Not Outputting Correct Values?

c

arrays

sorting

algorithm

cs50