java - 缩短冒泡排序循环

Question

我已经改变了我的冒泡排序，在排序的每个步骤中实现应用程序遍历整个列表。

这不是必需的，因为在第一次遍历之后，最小的项目将位于列表的末尾，而在第二次遍历之后，第二小的项目将位于其正确的位置（倒数第二个），依此类推。我有点不确定到底需要改变什么。

我需要修改冒泡排序，这样它就不会执行不必​​要的比较。

   private void bubbleSort() {
      int currentCount = 0;
      showStatus("Sorting ...");
      boolean swap = true;
      while (swap) {
         swap = false;
         for (int i = 0; i < items.length - 1; i++) {
            if (greaterThan(items[i], items[i + 1])) {
               swapItems(items[i], items[i + 1]);
               swap = true;
               currentCount++;
            }
         } // for
      } // while
      showStatus("Sort complete, number of swaps = " + currentCount);
   } // bubbleSort   private void bubbleSort() {

标签： javasortingbubble-sort

Answer 1

冒泡排序将执行不必要的比较，这就是为什么您不在生产中将其用于任何合理大小的任何数据集的原因。特别是关于您的代码。简单看一下Rosettacode上的参考实现（因为我不想真正重新编写它，你只在学校这样做）看起来表明它进行了完全相同数量的比较。如果你想要一个足够大的 N 的真正好的排序算法，请尝试合并排序。

参考

public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
    boolean changed = false;
    do {
        changed = false;
        for (int a = 0; a < comparable.length - 1; a++) {
            if (comparable[a].compareTo(comparable[a + 1]) > 0) {
                E tmp = comparable[a];
                comparable[a] = comparable[a + 1];
                comparable[a + 1] = tmp;
                changed = true;
            }
        }
    } while (changed);
}