c - 在 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

您的内循环顶端条件中断是 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现在反射(reflect)了您想要的内部循环的上限。外循环的每次枚举都会将下一个内循环缩小一个。冒泡排序的要点是，一旦一个元素被“冒泡”到其适当的位置，您就不需要再次访问该元素，您的代码没有利用这一点。

奖金优化

最后，您可以进一步优化这一点，并为您的冒泡排序提供算法可以提供的唯一的救赎质量:O(n) 在序列已经排序的最佳情况下。您可以通过“交换检测”来做到这一点。如果您在没有进行单个交换的情况下跳过内部循环，则执行更多排序是没有意义的。序列已排序，您就完成了。这是对上述原始算法的近乎免费的补充，看起来像这样:

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

将完全挫败上述优化。还有一些技术可以解决这个问题，包括两遍内循环枚举，在那里你上升以冒泡较大的值，然后反向下降，冒泡较小的值。但此时你最好使用更精细的算法，如快速排序或堆排序。对此的讨论以及本文的后半部分超出了您的问题范围。