java - 优化冒泡排序

Question

我想知道我还能如何优化冒泡排序，使其忽略已经排序的元素，即使是在第一次排序之后也是如此。

Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**]

我们观察到 [4,5,6] 已经按排序顺序排列，我该如何修改我的代码，以便它在下一次传递中忽略这 3 个元素？这意味着排序会更有效率？你建议使用递归方法吗？

public static void bubbleSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        boolean is_sorted = true;
        for (int j = 0; j < a.length; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                is_sorted = false;
            }
        }
        if (is_sorted) return;
    }
}

Answer 1

首先，你有一个越界访问:

for (int j = 0; j < a.length; j++) {
    if (a[j] > a[j + 1]) {

j == a.length-1 , 所以循环条件应该是 j < a.length-1 .

但是，在冒泡排序中，您知道在 k 之后通过，最大k元素在 k 处排序数组的最后一个条目，所以传统的冒泡排序使用

public static void bubbleSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        boolean is_sorted = true;
        // skip the already sorted largest elements
        for (int j = 0; j < a.length - i; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                is_sorted = false;
            }
        }
        if (is_sorted) return;
    }
}

现在，当数组有一个由最大元素组成的长排序尾部时，这仍然会做很多不必要的迭代，假设你有 k,k-1,...,1作为第一个k元素和 k+1至 100000000之后按顺序。标准冒泡排序将通过 k遍历(几乎)整个数组。

但是如果你还记得上次交换的位置，你就会知道在那个索引之后，顺序是最大的元素，所以

public static void bubbleSort(int[] a) {
    int lastSwap = a.length - 1;
    for (int i = 1; i < a.length; i++) {
        boolean is_sorted = true;
        int currentSwap = -1;
        for (int j = 0; j < lastSwap; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                is_sorted = false;
                currentSwap = j;
            }
        }
        if (is_sorted) return;
        lastSwap = currentSwap;
    }
}

将对上述示例进行排序，仅通过整个数组一次，其余仅通过(短)前缀。

当然，一般来说，这不会给您带来太多好处，但无论如何优化冒泡排序都是徒劳的。