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

Question

这是我的程序

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 项是不够的，并且根据建议我将计数器从 if 中移出，如果现在我将输入更改为

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

迭代次数更改为 78 。那更好(在它应该高的意义上)但它还不够高。那么这意味着算法有 O(logn) 时间？我以为冒泡排序是 O(n^2)？

谢谢

Answer 1

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