使用冒泡排序算法对整型数组进行排序

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

- Phong

---

你的冒泡排序实现不正确。它需要嵌套循环。请参考维基百科上的冒泡排序伪代码。 - prashant

num[] 是通过值传递的方式传递... 当你对 num 的副本进行排序时，它会被排序... 你应该将数组返回给调用者，然后使用 Print Array 打印新数组。 - Akshay Joy

@AkshayJoy 将数组传递给方法并不会创建副本。如果是这样的话，java.util.Arrays 中一半的方法将变得无用。 - Philipp Reichart

冒泡排序是一种简单的排序算法。它重复地遍历要排序的列表，比较每对相邻的项目，并在顺序不正确的情况下交换它们。过程通过多次遍历列表来完成，每次遍历都将剩余未排序的最大值放在列表末尾。 - James Oravec

http://www.roseindia.net/java/beginners/arrayexamples/bubblesort.shtml - Raghunandan

@prashant 抱歉，我不明白为什么需要使用 println 而不是只用 print。谢谢大家的反馈。 - Phong

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

        }
    }
}

- AllTooSir

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 循环替换为 n+1 次迭代的 for 循环来保证数组的排序；然而，while 循环具有更好的早期终止能力，在某些情况下比最坏情况更优。

- Ant P

---

顺便提一下，你可以用 while (swapped) 替换 while (swapped == true)。 - Steve Kuo

比之前的更快 ;) - parlad

Answer 3

您的排序逻辑有误。以下是冒泡排序的伪代码：

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

请查看这个排序网站，了解各种排序算法的详细教程。

- OldProgrammer

---

非常感谢您的回答。我刚开始学习编程，所以您的这种方法对我来说是新的。 - Phong

Answer 4

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

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

- John Doe

Answer 5

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

- shams keshk

Answer 6

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

    }


  }


}

- suyash saurabh

---

欢迎来到 Stack Overflow！请不要只是把您的源代码扔在这里。友好地并尝试给出一个详细的描述，使其他人会喜欢它并点赞。参见：如何撰写一个好的答案？ - sɐunıɔןɐqɐp

Answer 7

这是一个关于 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;
    }

- myusko

Answer 8

真的不太理解冒泡排序，更恰当地说它实际上是将较大/较重的元素沉到底部，而不是像大多数答案所述的“冒泡”上来。其中最典型的一个是

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

- Hearen

Answer 9

这不是冒泡排序算法，你需要重复执行直到没有可以交换的元素为止。

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

- Denys Séguret

Answer 10

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

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

- anubhava