时间戳

首页 > 解决方案 > 冒泡排序自适应（java）

java - 冒泡排序自适应（java）

问题描述

我正在编写具有 O(n^2) 的最坏情况运行时间和 O(n) 的最佳情况的冒泡排序算法，以便它是自适应的。我的想法是添加某种布尔标志变量来控制 while 循环，这样如果算法提前排序，算法就会提前停止。但是，它一直未能通过我的 JUnit 测试。我认为这是我实现布尔变量的方式，但我不知道该放在哪里。任何贡献将不胜感激。

    public static<T> void bubbleSort(T[] arr, Comparator<T> comparator) {
        if (arr == null || comparator == null) {
            throw new IllegalArgumentException("Comparator nor array can be null.");
        }
        boolean swapped = true;

        while (swapped) {
            swapped = false;
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = 0; j < arr.length - i - 1, j++) {
                    if (comparator.compare(arr[j], arr[j + 1]) > 0) {
                        T obj = arr[j];
                        arr[j] = arr[j + 1]
                        arr[j + 1] = obj;
                        swapped = true;
                    }
                }
           }
       }
  }

编辑：这是我正在使用的 JUNITS。

public class SortingTests {
    private TeachingAssistant[] tas;
    private TeachingAssistant[] tasByName;
    private ComparatorPlus<TeachingAssistant> comp;
    private static final int TIMEOUT = 200;

@Before
public void setUp() {
        tas = new TeachingAssistant[10];
        tas[0] = new TeachingAssistant("Adrianna");
        tas[1] = new TeachingAssistant("Chad");
        tas[2] = new TeachingAssistant("Jackie");
        tas[3] = new TeachingAssistant("Miguel");
        tas[4] = new TeachingAssistant("Ashley");
        tas[5] = new TeachingAssistant("Scott");
        tas[6] = new TeachingAssistant("Tim");
        tas[7] = new TeachingAssistant("Joey");
        tas[8] = new TeachingAssistant("Raymond");
        tas[9] = new TeachingAssistant("Bartosz");
        tasByName = new TeachingAssistant[10];
        tasByName[0] = tas[0];
        tasByName[1] = tas[4];
        tasByName[2] = tas[9];
        tasByName[3] = tas[1];
        tasByName[4] = tas[2];
        tasByName[5] = tas[7];
        tasByName[6] = tas[3];
        tasByName[7] = tas[8];
        tasByName[8] = tas[5];
        tasByName[9] = tas[6];

        comp = TeachingAssistant.getNameComparator();
    }

    @Test(timeout = TIMEOUT)
    public void testBubbleSort() {
        Sorting.bubbleSort(tas, comp);
        assertArrayEquals(tasByName, tas);
        assertTrue("Number of comparisons: " + comp.getCount(),
                comp.getCount() <= 44 && comp.getCount() != 0);
}

标签： javaalgorithmsortingbubble-sort

解决方案

如果我理解正确，您希望在数组已经排序（或半排序）的情况下实现 O(n)。如果你想提高你的时间复杂度，你需要做这样的事情：

for (int i = 0; i < arr.length - 1; i++) {
     boolean swapped = false;
     for (int j = 0; j < arr.length - i - 1, j++) {
          if (comparator.compare(arr[j], arr[j + 1]) > 0) {
              T obj = arr[i];
              arr[i] = arr[i + 1]
              arr[i + 1] = obj;
              swapped = True;
          }
     }
     if (swapped == false)
         break; // no inner swap done so can exit the upper loop
}

推荐阅读