-4

私はバブルソートアルゴリズムを学んでいますが、それを実装する2つの方法に出くわしたので、私の質問はどちらが優れているのか、なぜですか?

1位

for(k=0;k<array.length-1;k++){ 
            if(array[k] > array[k+1]){
                int temp = array[k];
                array[k] = array[k+1];
                array[k+1] = temp;
            }
        }

2位

for(i=array.length-1;i>=0;i--){
        for(k=0;k<i;k++){ 
            if(array[k] > array[k+1]){
                int temp = array[k];
                array[k] = array[k+1];
                array[k+1] = temp;
            }
        }
        }
4

6 に答える 6

1

どちらが優れているかではなく、まずどちらが配列をソートし、答えは2番目です

これをチェックして、より多くのアイデアを得る

于 2013-02-18T11:30:54.350 に答える
0

アルゴリズムが2つの隣接する要素のみを切り替えることができるため、実装の最初は正しくソートされません。

元。

入力データ {6,5,4,3,2}

最初の繰り返し make this -> {5,6,4,3,2} そして今 5 は 1 番目の位置にあり、ループ インデックス(k) が 1 であるため、この位置を変更する機会がありません。さらに繰り返しが増加します..

バブルソートには常に 2 つのループが必要です

public static void bubbleSort(int[] array){
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if(array[j] < array[j+1]){
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }
}
于 2013-02-18T11:57:02.303 に答える
0

ウィキペディア ( http://en.wikipedia.org/wiki/Bubble_sort )でより効率的なものを見つけました。

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       newn = 0
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             newn = i
           end if
       end for
       n = newn
    until n = 0
end procedure
于 2014-03-05T16:18:19.023 に答える
0

2 つ目は、配列をソートします。ただし、最後の反復で少なくとも 1 つのスワップがある場合にのみ実行することで、2 番目のループでの比較を減らすことができます。

于 2014-03-05T16:38:06.790 に答える
-2

バブルソートを使用しないでください (代わりに挿入ソートを使用してください)。

編集：

人々はこれに反対票を投じ続けているので、http://warp.povusers.org/grrr/bubblesort_misconceptions.htmlを読んでください。

バブルソートは、たとえば挿入ソートや選択ソートよりも遅く、理解するのが難しいため、パレート非効率的です。バブルソートを使用しない (または教えない) だけです。

于 2013-02-18T13:55:13.863 に答える