故障冒泡排序（遞歸）的整數中的Java

Question

試圖實現遞歸方法的陣列排序整數數組：

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); 
    } 

}

這似乎爲第幾個回合正常工作，將集合中最小的整數移到前面，但它只是在中途停止工作。任何想法爲什麼？謝謝！

Answer 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

FYI：冒泡排序的最壞情況下的性能是O（n^2），也許你會想要實現更好的排序算法一樣快速排序或歸併排序？

Answer 2

您的算法每次將最小值移動到數組的開頭，然後忽略後續調用中的最後一個元素。不幸的是，最後一個因素不能保證是最大的。

解決這個問題的一種方法可能是將index初始化爲arr.length - 1，然後繼續循環，而index > arr.length - n。

Answer 3

更改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; 
       } 
      } 
     } 
    }