以下冒泡排序在 C 中不起作用

Question

我正在编写一个排序函数来在 C 中实现冒泡排序，但它没有对给定的数组进行排序。这是以下代码。我正在使用 void 函数，所以我不能 return 数组并且必须对现有数组进行更改。代码可以很好地编译并运行，但它不会对数组进行排序。

void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm
    for(int i = 0; i < n; i++)
    {
        int sp = 0;
        for(int j = 0; j < n; j++)
        {
            if (values[i] > values[i + 1])
            {
                int first_val = values[i];
                int second_val = values[i + 1];

                values[i] = second_val;
                values[i + 1] = first_val;
                sp = 1;
            }
        }
        if (sp == 0)
        {
            break;
        }
    }
}

Answer 1

您可以通过说 values[i] > values[i + 1] 访问 values[i + 1]。所以 i 的自然极限应该是 n-1

for(int i = 0; i < n - 1; i++)

Answer 2

代码现在似乎可以使用以下代码：

void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm
    for(int i = 0; i < n-1; i++)
    {
        int sp = 0;
        for(int j = 0; j < n-1; j++)
        {
            if (values[j] > values[j + 1])
            {
                int first_val = values[j];
                int second_val = values[j + 1];

                values[j] = second_val;
                values[j + 1] = first_val;
                sp = 1;
            }
        }
        if (sp == 0)
        {
            break;
        }
    }

}

Answer 3

在冒泡排序中，第一遍进行n-1次比较，第二遍进行n-2次比较，第三遍进行n-3次比较，依此类推。所以比较的总数将是

(n-1)+(n-2)+(n-3)+.....+3+2+1
Sum = n(n-1)/2
i.e O(n2)

所以您需要在代码中更改两件事：-

内循环中的条件将为 (j=0;j< n-i-1;j++).
不需要取两个变量来交换数据。 Space 冒泡排序的复杂度为 O(1)，因为临时变量只需要一个额外的内存 space。

以下冒泡排序在 C 中不起作用

Following Bubble sort not working in C

c

arrays

sorting

bubble-sort

cs50