问冒泡排序实现来排序数组。效果如何？

EN

http://www.algolist.com是一个寻找算法实现的好网站。您可以找到关于冒泡排序这里的文章。

看起来，您的代码缺少一个检查是否真的需要交换的优化(正如Loki所指出的)。

这段代码摘自上面的URL，该URL实现了这个优化：

public void bubbleSort(int[] arr){
    boolean swapped = true;
    int j = 0;
    int tmp;
    while(swapped){
        swapped = false;
        j++;
        for(int i = 0; i < arr.length - j; i++){
            if(arr[i] > arr[i + 1]){
                tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                swapped = true;
            }
        }
    }
}

你可以从那一页读到更多关于它的信息，如果你是一个视觉学习者(就像我一样)，它也有一些有用的图表。

干杯

严格地说，这不是一种实现气泡排序的算法。它是泡泡排序的一个改进版本的实现，但是它没有正确地实现。

该实现使用的事实是，已知最后一项在第一次传递后处于正确位置，因此下一次传递可以对少一个项进行排序。最初的冒泡排序算法总是循环遍历所有的项目。

缺少的是该算法不检查什么时候不再进行掉期，而是一直循环，直到达到在最坏情况下可能需要的最大迭代次数为止。这意味着，它通常会在所有事情都已经解决后很长一段时间内保持循环。有一个变量num似乎就是用于这个目的的，但是有一些错误，因为该变量在任何地方都没有声明。

您应该在内部循环之前将num初始化为零，并在遍历项后循环直到它仍然为零为止：

import java.util.Arrays;
public class Tool {

  public static void main(String[] args){

    int[] n={4,8,12,87,32,98,12,45,94,42,938,84,63,67,86,37};

    int pass = n.length - 1;
    int num;
    do {
      num = 0;

      for(int x = 0; x < pass; x++){
        if(n[x] < n[x + 1]){
          int temp = n[x];
          n[x] = n[x + 1];
          n[x + 1] = temp
          num++;
        }

      }
      pass--;

    } while (num != 0);
    // To print the resulting array
    System.out.println(Arrays.toString(n));

  }
}

看见。

Bubble sort，也称为sinking sort，是一种简单的排序算法，它通过反复遍历要排序的列表，比较每一对相邻的项目，如果它们的顺序不对，就交换它们。遍历列表将被重复，直到不需要交换，这表明列表已被排序。该算法从较小的元素“冒泡”到列表顶部的方式获得它的名称。因为它只使用比较对元素进行操作，所以它是比较排序。虽然算法简单，但对大列表的排序效率不高，其他算法更好。维基百科 冒泡排序的最坏情况和平均复杂度都是n2(О)，其中n是被排序的项目数.有许多排序算法，其最坏情况或平均复杂度为O(n log )。即使是其他的n2排序算法，如插入排序算法，也往往比气泡排序算法具有更好的性能。因此，当n很大时，气泡排序不是一种实用的排序算法。 冒泡排序相对于大多数其他实现，甚至比快速排序(但不是插入排序)具有的唯一显著优势是，检测列表被排序的能力被有效地内置到算法中。对于已经排序的列表(最好的情况)，冒泡排序的性能是O(n).相反，大多数其他算法，甚至那些具有更好的平均案例复杂度的算法，在集合上执行他们的整个排序过程，因此更加复杂。但是，插入排序不仅具有这一机制，而且在基本上排序的列表(有少量倒置)上也表现得更好。 气泡排序中元素的位置将在很大程度上决定它的性能。列表开头的大型元素不会造成问题，因为它们很快就会被交换。然而，接近尾声的小元素移动到起点的速度非常缓慢。 这个行话文件也称气泡排序为“一般糟糕的算法”。该文件以“典型的反常糟糕的算法”而闻名。唐纳德·克努斯(2 Donald Knuth )在他的著名著作“计算机编程艺术”( The Art of Computer Programming )中得出结论：“气泡排序似乎没有什么可推荐的，只有一个醒目的名字。” 气泡排序与现代CPU硬件的交互能力也很差。它要求的写入量至少是插入排序的两倍，是未命中缓存的两倍。 在爪哇显示泡沫排序大约比 插入排序 慢5倍，比 选择排序慢40%。