我的BubbleSort类没有正确计算迭代次数

本文关键字：计算 迭代 BubbleSort 我的 | 更新日期: 2023-09-27 18:30:03

这是我的程序

static void Main(string[] args)
        {
            int[] arrayToSort = new int[] { 5,4,9};
            BubbleSort bubbleSort = new BubbleSort();
            int [] SortedArray = bubbleSort.SortArray(arrayToSort);
            foreach (int i in SortedArray)
                Console.Write(i.ToString() + "," );
            Console.WriteLine("Number of Iterations {0}",   
                               bubbleSort.IterationsCounter);
            Console.ReadLine();    
        }
 public class BubbleSort
    {
        public int IterationsCounter;
        public int[] SortArray(int[] arrayToSort)
        {
            for(int i = 0;i<arrayToSort.Length-1;i++)
            {
                if(arrayToSort[i]>arrayToSort[i+1])
                {
                    int temp=arrayToSort[i];
                    arrayToSort[i]=arrayToSort[i+1];
                    arrayToSort[i+1]=temp;
                    //IterationsCounter++;  Update:Moved this line out of if condition)
                    SortArray(arrayToSort);
                }
            IterationsCounter++; //Moved counter here:
            }
            return arrayToSort;
    }

输出：

4,5,9 Number of Iterations:1

这怎么可能是对的？我的意思是数组是排序的，但肯定有不止一次迭代。我本以为这会有O（N^2）的运行时间，但这里有些问题。我没有正确计算迭代次数吗？

编辑：

好的，我意识到3项是不够的，根据建议，如果，我将计数器移出，如果现在我将输入更改为

 5,4,9,2,3,1,17

迭代次数更改为78。这更好（从某种意义上说，它应该很高），但它还不够高。那么这意味着算法有O（logn）时间？我以为泡泡糖是O（n^2）？

感谢

我的BubbleSort类没有正确计算迭代次数

您计算的是交换操作的次数，而不是迭代次数。Bubble排序的平均运行时间是O（n^2），这并不意味着每个Bubble分类都必须进行这么多次迭代。例如，如果对已排序的数组进行冒泡排序，并在整个数组遍历后进行交换时设置标志。如果没有进行交换，那么应该清楚的是，阵列已经有序，因为不需要交换两个元素。在这种情况下，泡沫类型应该结束。它似乎比平均时间复杂度为O（n-logn）的快速排序更快，因为在这种情况下，修改后的冒泡排序的性能为O（n）。但你必须考虑到一般情况。

Put IterationsCounter++；在if循环之外计算迭代次数。到目前为止，代码将只计算交换的数量，因为只有当存在交换时，它才会增加。

相关文章：