冒泡排序自适应（Java） [英] Bubble sort adaptive (java)

问题描述

我正在编写带有最差运行时间O（n ^ 2）和最佳情况O（n）的冒泡排序算法，以使其具有自适应性。我的想法是添加某种布尔标志变量来控制while循环，以便如果算法过早排序，算法将尽早停止。但是，它一直使我的JUnit测试失败。我认为这是实现布尔变量的方式，但是我不确定将其放在哪里。

I'm writing up the Bubble Sort algorithm with worst case runtime of O(n^2) and best case of O(n) so that it is adaptive. My idea was to add some sort of boolean flag variable to control the while loop so that the algorithm would stop early if it was sorted early. However, it keeps failing my JUnit testing. I think it's the way I'm implementing the boolean variable but I'm not sure where else to put it. Any contributions would be greatly appreciated.

    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。

here are the JUNITS I am using.

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

推荐答案

这样的事情怎么样：

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++) {
            if (comparator.compare(arr[i], arr[i + 1]) > 0) {
                T obj = arr[i];
                arr[i] = arr[i + 1]
                arr[i + 1] = obj;
                swapped = true;
            }
       }
   }


 }

这篇关于冒泡排序自适应（Java）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！