java - 通过使其注意到最后一次交换发生的位置来改进冒泡排序

Question

如何改进此代码以使其不每次将 i 减一，而是将其设置为上次交换发生的位置(较低的位置)。如果没有发生交换，i 应设置为零，这将结束循环

public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
    for (int i = a.length - 1; i > 0; --i) {
        for (int j = 0; j < i; ++j) {
            numComp++;
            if (a[j].compareTo(a[j + 1]) > 0) {
                numAsgn += 3;
                T temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
        }
        if (tracing) {
            System.out.println("one more bubbled up: "
                    + Arrays.toString(a));
        }
    }
}

这是我的尝试。

 public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
    boolean swap = false;
    for (int i = a.length - 1; i > 0;) {
        for (int j = 0; j < i; ++j) {
            numComp++;
            if (a[j].compareTo(a[j + 1]) > 0) {
                numAsgn += 3;
                T temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
                swap = true;
            }
            if (swap) {
                i = j;
            } else {
                i = 0;
            }
        }
        if (tracing) {
            System.out.println("one more bubbled up: "
                    + Arrays.toString(a));
        }
    }
}

打印输出的代码如下:

 bubbleSort(check);
    System.out.printf("%1$-19s %2$10d %3$19d %4$19d", "Bubble", numComp, numAsgn, numComp + numAsgn);
    System.out.println();
    resetCounts(); //resets numComp and numAsgn to 0

输入示例:[2, 5, 5, 3, 1, 3, 4, 4, 3, 4]

输出:

Answer 1

大概是这样的:

public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
    int lastSwap = a.length - 1, i;
    for (i = lastSwap; i > 0;) {
        for (int j = 0; j < i; ++j) {
            numComp++;
            if (a[j].compareTo(a[j + 1]) > 0) {
                numAsgn += 3;
                T temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
                lastSwap = j;
            }
        }
        if(i == lastSwap) {
            //sorted
            break;
        }
        i = lastSwap;
        if (tracing) {
            System.out.println("one more bubbled up: "
                    + Arrays.toString(a));
        }
    }
}

这应该会给您带来一些改进，但最坏的情况仍然如预期的那样。