1

这是我的我的程序

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) 时间吗？我认为bubblesort是O（n ^ 2）？

谢谢

4

2 回答 2

0

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

于 2013-09-04T06:32:00.893 回答
0

把 IterationsCounter++; 在 if 循环之外计算迭代次数。到目前为止，代码只会计算交换次数，因为它仅在有交换时才会增加。

于 2013-09-04T06:26:59.657 回答