12

为什么我打印出来的数组没有在下面的代码中排序？

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

16 回答 16

45

您需要两个循环来实现冒泡排序。

示例代码：

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

        }
    }
}
于 2013-04-18T17:01:59.737 回答
12

你只通过你的阵列一次！冒泡排序要求你一直循环，直到你发现你不再做任何交换；因此 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循环具有在好于最坏的情况下提前终止的优势。

于 2013-04-18T17:04:53.700 回答
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

有关所有各种排序方法的优秀教程，请参阅此排序网站。

于 2013-04-18T17:02:46.137 回答
1

我使用这种方法进行冒泡排序

public static int[] bubbleSort (int[] a) {
    int n = a.length;
    int j = 0;
    boolean swap = true;
    while (swap) {
        swap = false;
        for (int j = 1; j < n; j++) {
            if (a[j-1] > a[j]) {
                j = a[j-1];
                a[j-1] = a[j];
                a[j] = j;
                swap = true;
            }
        }
        n = n - 1;
    }
    return a;
}//end bubbleSort
于 2018-04-25T13:04:08.130 回答
0

这不是冒泡排序算法，你需要重复，直到你没有东西可以交换：

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;
  }
}
于 2013-04-18T17:04:02.943 回答
0

冒泡排序嵌套循环应该这样写：

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;
       }                    
   }
}
于 2013-04-18T17:05:05.183 回答
0 
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);
    }
于 2017-12-25T16:45:56.870 回答
0 
public class Bubblesort{

  public static int arr[];

  public static void main(String args[]){

    System.out.println("Enter number of element you have in array for performing bubblesort");

    int numbofele = Integer.parseInt(args[0]);

    System.out.println("numer of element entered is"+ "\n" + numbofele);

    arr= new int[numbofele];

    System.out.println("Enter Elements of array");

    System.out.println("The given array is");


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

      arr[i]=Integer.parseInt(args[j]);

      System.out.println(arr[i]);

    }

    boolean swapped = false;

    System.out.println("The sorted array is");

    for(int k=0;k<numbofele-1;k++){


      for(int l=0;l+1<numbofele-k;l++){

        if(arr[l]>arr[l+1]){

          int temp = arr[l];
          arr[l]= arr[l+1];
          arr[l+1]=temp;
          swapped=true;

        } 

      }

         if(!swapped){

            for(int m=0;m<numbofele;m++){

       System.out.println(arr[m]);

    }

      return;

      }


    }

    for(int m=0;m<numbofele;m++){

       System.out.println(arr[m]);

    }


  }


}
于 2018-06-20T06:37:52.413 回答
0

冒泡排序算法是对数组元素进行排序的一种最简单的方法。大多数其他算法比冒泡排序算法效率更高。最坏情况和平均情况的时间复杂度为 (n^2)。让我们考虑如何实现冒泡排序算法。

class buble_sort{
  public static void main(String a[]){

    int[] num={7,9,2,4,5,6,3};
    int i,j,tmp;

    for(i=0;i<num.length;i++){
        for(j=0;j<num.length-i;j++){
            if(j==(num.length-1)){
                break;
            }
            else{
                if(num[j]>num[j+1]){
                    tmp=num[j];
                    num[j]=num[j+1];
                    num[j+1]=tmp;
                }
            }
        }
    }

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

}

于 2018-07-07T19:54:49.700 回答
0

开始了

static String arrayToString(int[] array) {
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < array.length; i++) {
      stringBuilder.append(array[i]).append(",");
    }
    return stringBuilder.deleteCharAt(stringBuilder.length()-1).toString();
  }

  public static void main(String... args){
    int[] unsorted = {9,2,1,4,0};
    System.out.println("Sorting an array of Length "+unsorted.length);
    enhancedBubbleSort(unsorted);
    //dumbBubbleSort(unsorted);
    //bubbleSort(unsorted);
    //enhancedBubbleSort(unsorted);
    //enhancedBubbleSortBetterStructured(unsorted);
    System.out.println("Sorted Array: "+arrayToString(unsorted));

  }

  // this is the dumbest BubbleSort
  static int[] dumbBubbleSort(int[] array){
    for (int i = 0; i<array.length-1 ; i++) {
      for (int j = 0; j < array.length - 1; j++) {
        if (array[j] > array[j + 1]) {
          // Just swap
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
      }
      System.out.println("After "+(i+1)+" pass: "+arrayToString(array));
    }
    return array;
  }

  //this "-i" in array.length - 1-i brings some improvement.
  // Then for making our bestcase scenario better ( o(n) , we will introduce isswapped flag) that's enhanced bubble sort

  static int[] bubbleSort(int[] array){
    for (int i = 0; i<array.length-1 ; i++) {
      for (int j = 0; j < array.length - 1-i; j++) {
        if (array[j] > array[j + 1]) {
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
      }
      System.out.println("After "+(i+1)+" pass: "+arrayToString(array));
    }
    return array;
  }

  static int[] enhancedBubbleSort(int[] array){
    int i=0;
    while (true) {
      boolean swapped = false;
      for (int j = 0; j < array.length - 1; j++) {
        if (array[j] > array[j + 1]) {
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
          swapped =true;
        }
      }
      i++;
      System.out.println("After "+(i)+" pass: "+arrayToString(array));
      if(!swapped){
        // Last iteration (of outer loop) didnot result in any swaps. so stopping here
        break;
      }
    }
    return array;
  }

  static int[] enhancedBubbleSortBetterStructured(int[] array){
    int i=0;
    boolean swapped = true;
    while (swapped) {
      swapped = false;
      for (int j = 0; j < array.length - 1; j++) {
        if (array[j] > array[j + 1]) {
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
          swapped = true;
        }
      }
      i++;
      System.out.println("After "+(i)+" pass: "+arrayToString(array));
    }
    return array;
  }
于 2019-02-04T03:53:39.657 回答
0

这是一个bubbleSort的例子，时间复杂度是 O(n)。

 int[] bubbleSort(int[] numbers) {
        if(numbers == null || numbers.length == 1) {
            return numbers;
        }

        boolean isSorted = false;

        while(!isSorted) {
            isSorted = true;
            for(int i = 0; i < numbers.length - 1; i++) {
                if(numbers[i] > numbers[i + 1]) {
                    int hold = numbers[i + 1];
                    numbers[i + 1] = numbers[i];
                    numbers[i] = hold;
                    isSorted = false;
                }
            }
        }

        return numbers;
    }
于 2019-03-21T19:05:53.823 回答
0

真的没有得到bubble sort，这可以更恰当地称为下沉排序，因为它实际上是在大多数答案中将更大/更重的东西下沉到底部。最典型的例子之一是

private static void sortZero(Comparable[] arr) {
    boolean moreSinkingRequired = true;
    while (moreSinkingRequired) {
        moreSinkingRequired = false;
        for (int j = 0; j < arr.length - 1; ++j) {
            if (less(arr, j + 1, j)) { 
                exch(arr, j, j + 1);
                moreSinkingRequired = true;
            }
        }
    }
}

顺便说一句，您必须多穿越一次才能提前停止。

但是当我看到它冒泡时

private static void sortOne(Comparable[] arr) {
    for (int i = 0; i < arr.length - 1; ++i) {
        for (int j = arr.length - 1; j > i; --j) { // start from the bottom
            if (less(arr, j, j - 1)) {
                exch(arr, j - 1, j);
            }
        }
    }
}

您必须知道这种方法实际上更好，因为它跟踪终点以j > i与[0, i-1]已经排序的比较。

我们也可以添加更早的终止，但它会变得冗长为

private static void sortTwo(Comparable[] arr) {
    boolean moreBubbleRequired = true;
    for (int i = 0; i < arr.length - 1 && moreBubbleRequired; ++i) {
        moreBubbleRequired = false;
        for (int j = arr.length - 1; j > i; --j) {
            if (less(arr, j, j - 1)) {
                exch(arr, j - 1, j);
                moreBubbleRequired = true;
            }
        }
    }
}

用于使流程简洁的实用程序是

public static boolean less(Comparable[] arr, int i, int j) {
    return less(arr[i], arr[j]);
}

public static boolean less(Comparable a, Comparable b) {
    return a.compareTo(b) < 0;
}

public static void exch(Comparable[] arr, int i, int j) {
    Comparable t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
于 2019-04-01T01:45:45.497 回答
-1 
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);


    }
  }
}
于 2015-10-28T06:57:00.750 回答
-1 
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);
    }
}
于 2015-11-08T16:22:45.473 回答
-1

爪哇代码 

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

    }

}
于 2016-11-10T18:38:58.417 回答
-2

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;
}
于 2016-07-28T20:43:27.320 回答