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) の実行時間がかかると予想していましたが、ここで何かがずれています。私は反復を正しく数えていませんか？

編集：

OK、3 つのアイテムでは不十分であることに気付きました。また、提案に従って、カウンターをifから移動しました。

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

反復回数が に変わります78。それは（高くなければならないという意味で）より良いですが、十分に高くはありません。では、これはアルゴリズムに O(logn) 時間があることを意味しますか? バブルソートはO（n ^ 2）だと思いましたか？

ありがとうございました

4

2 に答える 2

0

IterationsCounter++ を入れます。if ループの外側で反復回数をカウントします。スワップがある場合にのみインクリメントされるため、今のところ、コードはスワップの数をカウントするだけです。

于 2013-09-04T06:26:59.657 に答える
0

繰り返しではなく、スワップ操作の数を数えています。バブル ソートの平均実行時間は O(n^2) であり、すべてのバブル ソートが非常に多くの反復を実行する必要があるという意味ではありません。たとえば、並べ替えられた配列をバブル ソートし、配列全体のパスの後にスワップが行われた場合にフラグを設定するとします。スワップが行われない場合、2 つの要素をスワップする必要がないため、配列が既に適切であることは明らかです。その場合、バブルソートは終了するはずです。このシナリオでは、変更されたバブル ソートのパフォーマンスが O(N) であるため、平均時間の複雑さが O(n log n) であるクイックソートよりも高速に見えます。ただし、一般的なケースを考慮する必要があります。

于 2013-09-04T06:32:00.893 に答える