使用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

你只需要通过你的阵列一次!冒泡排序要求你保持循环,直到你发现你不再进行任何交换; 因此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使用for循环n+1迭代替换外部循环,这将保证数组的顺序; 但是,while循环具有在优于最差情况下提前终止的优点.