冒泡函数在 C 中对整数数组进行排序

Question

我编写了一个冒泡函数，它应该对用户输入的整数数组进行冒泡排序，但出于某种原因，我的数组只适用于大小为 6 的数组...否则数组输出零最大的数字。请运行此代码并帮助我找出问题所在。

        #include <stdio.h>
        //prototype
        void bubble(int array[], int size);



        int main(void) 
        {
            int n,i,j,size,temp,counter = 0;
            //FOR SOME REASON, ONLY INPUT SIZE 6 WORKS PERFECTLY.
            int k;
            printf("How many numbers to sort?\n");
            scanf("%d",&size);
            int array[size];
            for(i=0;i<size;i++)
            {
                printf("Enter number %d\n",i+1);
                scanf("%d",&k);
                array[i] = k;
            }
            printf("Array before sorting:\n");

            for(i=0;i<size;i++)
            {
                printf("%d  ",array[i]);
            }

            bubble(array,size);

        return 0;
        }

        // use this if you want to test print an array
        // for(i=0;i<size;i++)
            // {
            //     printf("%d",array[i]);
            // }
        void bubble(int array[], int size)
        {
            int i, j, temp;
            for(j=0;j<size;j++)
            {  
                printf("\nIteration# %d\n",j+1);
                for(i=0;i<size;i++)
                {
                    if(array[i] > array[i+1])
                    {
                        temp = array[i];
                        array[i] = array[i+1];
                        array[i+1] = temp;
                    }
                    printf("%4d",array[i]);

                }

            }
        }

        // void select(int array[], int size)
        // {
        //     int i, j, temp;
        //     min = array[0];
        //     for(j=0;j<size;j++)
        //     {
        //         if(array[j] < min)
        //         {
        //             array[j] = temp;
        //             min = array[j];



        //         }


        //     }

        // }

Answer 1

i<size 与 i+1 的组合将越过数组的边界。

你应该替换这个：

for(i=0;i<size;i++)

有了这个：

for(i=0;i<size-1;i++)

Answer 2

您的内部循环顶端条件中断是 size，但在循环中您引用 array[i+1]，这意味着您指的是 array[size]。由于 C 数组是从零开始索引的，因此唯一允许的索引是从 0...(size-1)。您的代码反复违反了一项。

将内部循环的顶端更改为 size-1 将适用于您的情况。但可以说有一个更好的选择可以让你从一开始就记住负 1。它涉及在排序时修改 size 以直接控制内部循环的顶端。它还消除了一个您不再需要的局部变量。

    void bubble(int array[], int size)
    {
        while (size-- > 0)
        {  
            for(int i=0; i<size; ++i)
            {
                if(array[i] > array[i+1])
                {
                    int temp = array[i];
                    array[i] = array[i+1];
                    array[i+1] = temp;
                }
            }
        }
    }

通常称为"goes-down-to"表达式（因为它看起来像一个指向极限值的长箭头），外层循环已更改为while (size-- > 0)。这会将 size 的当前值变为临时值，递减大小，并将临时值与 > 0（或多或少）进行比较。结果是 size 现在反映了你想要的内循环的上限。外循环的每个枚举都会将下一个内循环传递缩小一次。冒泡排序的要点是，一旦一个元素 "bubbled up" 到了它的正确位置，你就不需要再访问那个元素，你的代码 而不是 利用的东西.

奖金优化

最后，您可以进一步优化它，并为您的冒泡排序提供该算法可以提供的唯一可取之处：在序列已经排序的最佳情况下为 O(n)。你可以通过 "swap-detection" 来做到这一点。如果你在没有进行一次交换的情况下跳过了内循环，那么再执行排序就没有意义了。序列已排序，您就完成了。这是对上述原始算法的近乎免费的补充，看起来像这样：

void bubble(int array[], int size)
{
    int swapped = 1;
    while (swapped && size-- > 0)
    {  
        swapped = 0;
        for(int i=0; i<size; ++i)
        {
            if(array[i] > array[i+1])
            {
                int temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
                swapped = 1;
            }
        }
    }
}

给定一个已经排序的十、一百或十万个元素的序列，这将在一次通过后完成。值得注意的是：即使一个元素在一端位置不正确也会使这种优化变得无关紧要。 IE。如果任何属于开头附近的元素最初都靠近结尾，则最多需要 size 次迭代才能将其带回家，因此优化变得没有实际意义。简而言之，这个序列

1 3 4 5... 9998 9999 2

将完全破坏上面的优化。也有一些技术可以解决这个问题，包括两次传递的内部循环枚举，您可以在其中上升以冒出更大的值，然后反向到 descend，冒出更小的值。但此时你最好使用更精细的算法，如快速排序或堆排序。对此的讨论，实际上 post 的后半部分超出了您的问题范围。

冒泡函数在 C 中对整数数组进行排序

Bubble Function sorting in C on an array of integers

c

arrays

bubble-sort