使用BubbleSort對int數組進行排序

Question

爲什麼我的打印出來的數組未在下面的代碼中排序？

public class BubbleSort { 

    public void sortArray(int[] x) {//go through the array and sort from smallest to highest 
     for(int i=1; i<x.length; i++) { 
     int temp=0; 
     if(x[i-1] > x[i]) { 
      temp = x[i-1]; 
      x[i-1] = x[i]; 
      x[i] = temp; 
     } 
     } 
    } 

    public void printArray(int[] x) { 
     for(int i=0; i<x.length; i++) 
     System.out.print(x[i] + " "); 
    } 

    public static void main(String[] args) { 
     // TestBubbleSort 
     BubbleSort b = new BubbleSort(); 
     int[] num = {5,4,3,2,1}; 
     b.sortArray(num); 
     b.printArray(num); 
    } 
} 

Answer 1

您需要兩個循環來實現氣泡排序。

示例代碼：

public static void bubbleSort(int[] numArray) { 

    int n = numArray.length; 
    int temp = 0; 

    for (int i = 0; i < n; i++) { 
     for (int j = 1; j < (n - i); j++) { 

      if (numArray[j - 1] > numArray[j]) { 
       temp = numArray[j - 1]; 
       numArray[j - 1] = numArray[j]; 
       numArray[j] = temp; 
      } 

     } 
    } 
} 

Answer 2

你選邏輯是錯誤的。這是冒泡排序的僞代碼：

for i = 1:n, 
    swapped = false 
    for j = n:i+1, 
     if a[j] < a[j-1], 
      swap a[j,j-1] 
      swapped = true 
    → invariant: a[1..i] in final position 
    break if not swapped 
end 

好的教程，請參閱本sorting web site所有的各種排序方法上。

Answer 3

這不冒泡排序算法，你需要重複，直到你有什麼交換：

public void sortArray(int[] x) {//go through the array and sort from smallest to highest 
    for(;;) { 
     boolean s = false; 
     for(int i=1; i<x.length; i++) { 
     int temp=0; 
     if(x[i-1] > x[i]) { 
      temp = x[i-1]; 
      x[i-1] = x[i]; 
      x[i] = temp; 
      s = true; 
     } 
     } 
     if (!s) return; 
    } 
} 

Answer 4

你只能通過你的陣列做一遍！泡泡排序要求你保持循環，直到你發現你不再做任何交換;因此O（n^2）的運行時間。

試試這個：

public void sortArray(int[] x) { 
    boolean swapped = true; 
    while (swapped) { 
     swapped = false; 
     for(int i=1; i<x.length; i++) { 
      int temp=0; 
      if(x[i-1] > x[i]) { 
       temp = x[i-1]; 
       x[i-1] = x[i]; 
       x[i] = temp; 
       swapped = true; 
      } 
     } 
    } 
} 

一旦swapped == false在循環結束時，你已經取得了全通沒有找到哪裏x[i-1] > x[i]，因此，你知道數組排序任何實例。只有然後可以終止算法。

您也可以用外循環while代替循環n+1迭代，這將保證數組的順序;然而，while循環具有在優於最壞情況下提前終止的優點。

Answer 5

冒泡排序嵌套循環應該這樣寫：

int n = intArray.length; 
int temp = 0; 

for(int i=0; i < n; i++){ 
    for(int j=1; j < (n-i); j++){       
     if(intArray[j-1] > intArray[j]){ 
      //swap the elements! 
      temp = intArray[j-1]; 
      intArray[j-1] = intArray[j]; 
      intArray[j] = temp; 
     }      
    } 
} 

Answer 6

public class SortingArray { 
public static void main(String[] args) { 

int[] a={3,7,9,5,1,4,0,2,8,6}; 
int temp=0; 

boolean isSwapped=true; 


System.out.println(" before sorting the array: "); 

for(int i=0;i<a.length;i++) 
{ 
    System.out.print(a[i]); 
} 
System.out.println(""); 

do 
{ 

isSwapped=false; 

for(int i=0;i<a.length-1;i++) 

{ 

    if(a[i]>a[i+1]) 

    { 

     temp=a[i]; 

     a[i]=a[i+1]; 

     a[i+1]=temp; 

    } 



} 


}while(isSwapped); 


System.out.println("after sorting the array: "); 

    for(int array:a) 

    { 

     System.out.print(array); 


    } 
    } 
} 

Answer 7

public class BubbleSort { 

    public void sorter(int[] arr, int x, int y){ 

      int temp = arr[x]; 
      arr[x] = arr[y]; 
      arr[y] = temp; 

    } 

    public void sorter1(String[] arr, int x, int y){ 

     String temp = arr[x]; 
     arr[x] = arr[y]; 
     arr[y] = temp; 

    } 

    public void sertedArr(int[] a, String[] b){ 
     for(int j = 0; j < a.length - 1; j++){ 
      for(int i = 0; i < a.length - 1; i++){ 
       if(a[i] > a[i + 1]){ 
        sorter(a, i, i + 1); 
        sorter1(b, i, i + 1); 
       } 
      } 
     } 
     for(int i = 0; i < a.length; i++){ 
      System.out.print(a[i]); 
     } 
     System.out.println(); 
     for(int i = 0; i < b.length; i++){ 
      System.out.print(b[i]); 
     } 
     // 
    } 
    public static void main(String[] args){ 
     int[] array = {3, 7, 4, 9, 5, 6}; 
     String[] name = {"t", "a", "b", "m", "2", "3"}; 
     BubbleSort bso = new BubbleSort(); 
      bso.sertedArr(array, name); 
    } 
} 

Answer 8

標準冒泡排序實現Java中：

//Time complexity: O(n^2) 
public static int[] bubbleSort(int[] arr) { 

    if (arr == null || arr.length <= 1) { 
     return arr; 
    } 

    for (int i = 0; i < arr.length; i++) { 
     for (int j = 1; j < arr.length - i; j++) { 
      if (arr[j - 1] > arr[j]) { 
       arr[j] = arr[j] + arr[j - 1]; 
       arr[j - 1] = arr[j] - arr[j - 1]; 
       arr[j] = arr[j] - arr[j - 1]; 
      } 
     } 
    } 

    return arr; 
} 

Answer 9

Java代碼

public void bubbleSort(int[] arr){ 

    boolean isSwapped = true; 

    for(int i = arr.length - 1; isSwapped; i--){ 

     isSwapped = false; 

     for(int j = 0; j < i; j++){ 

      if(arr[j] > arr[j+1]}{ 
       int temp = arr[j]; 
       arr[j] = arr[j+1]; 
       arr[j+1] = temp; 
       isSwapped = true; 
      } 
     } 

    } 

} 

Answer 10

public static void BubbleSort(int[] array){ 
     boolean swapped ; 
     do { 
      swapped = false; 
      for (int i = 0; i < array.length - 1; i++) { 
       if (array[i] > array[i + 1]) { 
        int temp = array[i]; 
        array[i] = array[i + 1]; 
        array[i + 1] = temp; 
        swapped = true; 
       } 
      } 
     }while (swapped); 
    }