0

整数の配列をソートする再帰メソッドを実装しようとしています:

    public static void bubbleSort(int[] arr, int n){

      int index = n-1;

      System.out.println("Round number: " + n);
      System.out.println(Arrays.toString(arr));

      while(index>=1)
      {
          if(arr[index] <  arr[index-1])
              swap(arr, index, index-1);


          index--;
      }
      if(n>1)
          bubbleSort(arr, n-1);
  }

}

セット内の最小の整数を前に移動して、最初の数ラウンドはうまく機能しているように見えますが、途中で機能しなくなります。理由はありますか？ありがとう！

4

3 に答える 3

1

if条件を次のように変更します。

...
if(arr[index] <  arr[index-1]){
   swap(arr, index, index-1);
   index = n;
}
index--;
...

問題は、配列全体で「委任」する配列メンバーを見つけた後、「再検討」する必要がある他のメンバーが存在する可能性があるため、「再起動」する必要があることです。デバッガーを実行して、私の説明が十分に明確でない場合は、私が何を意味するかを確認してください。

完全なソリューション:

import java.util.Arrays;

/**
 * User: alfasin
 * Date: 8/5/13
 */
public class BubbleSort {

    public static void bubbleSort(int[] arr, int n){

        int index = n-1;

        System.out.println("Round number: " + n);
        System.out.println(Arrays.toString(arr));

        while(index>=1)
        {
            if(arr[index] <  arr[index-1]){
                swap(arr, index, index-1);
                index = n;
            }
            index--;
        }
        if(n>1)
            bubbleSort(arr, n-1);
    }

    private static void swap(int[] arr, int index, int i) {
        arr[i] = arr[i] ^ arr[index];
        arr[index] = arr[i] ^ arr[index];
        arr[i] = arr[i] ^ arr[index];
    }

    public static void main(String...args){
        int[] arr = {4,2,9,6,2,8,1};
        bubbleSort(arr, arr.length);
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i]+" ");
        }
    }

}

sjee397 が提案したように、これはバブルソートの「バージョン」のようなものです...

バブルソートのより「保守的な」バージョン:

public static void bubbleSort(int[] arr, int n){
        boolean swapped= true;
        while (swapped){
            swapped = false;
            for(int i=0; i<arr.length-1; i++){
                if(arr[i]>arr[i+1]){
                    swap(arr,i,i+1);
                    swapped = true;
                }
            }
        }
    }
于 2013-08-06T01:14:07.740 に答える
1

これを試して：

import java.util.*;

public class Test{
    public static void main(String[] args){
        int[] ttt = {9,8,7,6,5,4,3,2,1};

        bubbleSort(ttt, ttt.length);
    }

    public static void bubbleSort(int[] arr, int n){
        int index = 0;

        System.out.println("Round number: " + n);
        System.out.println(Arrays.toString(arr));

        while(index < n - 1){
            if(arr[index] >  arr[index + 1]){
                swap(arr, index, index + 1);
            }
            index++;
        }

        if(n > 1){
            bubbleSort(arr, n-1);
        }
    }

    public static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

あなたの場合、すべてのラウンドで、すべてのラウンドの終わりまでに最小の数値がその場所にプッシュされることを保証しますが、配列の最後の要素は省略します。これは必ずしも最大の数値ではありません。それを逆の順序で実行し、最大の数字をその場所にプッシュしてから、次のラウンドで除外する必要があります。

http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif

参考までに: バブル ソートの最悪の場合のパフォーマンスは O(n^2) です。おそらく、クイックソートやマージ ソートなどのより優れたソート アルゴリズムを実装する必要がありますか?

于 2013-08-06T01:27:59.007 に答える