16

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

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

12 回答 12

26

首先，您有一个越界访问：

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

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

将对上面的示例进行排序，其中只有一次通过整个数组，其余的仅通过（短）前缀。

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

于 2013-04-24T15:31:25.307 回答
2

您应该为内部循环使用变量“大小”并将其更改为每个循环中最新的交换元素。这样，您的内部循环将上升到最新的“交换”元素并传递其余未交换的元素（也就是在它们的正确位置）。IE

do {
    int newsize = 0;
    for (int i = 1; i < size; i++) {
        if (a[i - 1] > a[i]) {
            int temp;
            temp = a[i - 1];
            a[i - 1] = a[i];
            a[i] = temp;
            newsize = i;
        }
    }
    size = newsize;
} while (size > 0);
于 2014-10-19T14:19:02.563 回答
1 
public static Integer[] optimizedBubbleSort(Integer[] input) {
    long startTime = System.nanoTime();
    boolean swapped = true;
    for (int pass = input.length - 1; pass >= 0 && swapped; pass--) {
        swapped = false;
        for (int i = 0; i < pass; i++) {
            if (input[i] > input[i + 1]) {
                int temp = input[i];
                input[i] = input[i + 1];
                input[i + 1] = temp;
                swapped = true;
            }
        }
    }
    System.out.println("Time taken for OPTIMIZED bubbleSort: "
            + (System.nanoTime() - startTime));
    return input;
}
于 2015-06-11T04:04:30.973 回答
1 
public static void BubbleSorter(params int[] input) {
    int newSize = input.Length - 1, size = 0;
    bool swap;
    do {
        swap = false;
        for (int j = 0; j < newSize; j++) {
            if (input[j] > input[j + 1]) {
                int temp = input[j + 1];
                input[j + 1] = input[j];
                input[j] = temp;
                swap = true;
                size = j;
            }
        }
        newSize = size;
    } while (swap);
    DisplayArrayElements(input);
}
于 2015-11-01T05:10:35.847 回答
0

我设计了一种方法，通过排除在先前循环中已排序的数组开头和结尾的部分来减少迭代次数。

static int[] bubbleSortOptimized(int arr[]) {
    int start = 0, stop = arr.length - 1, control = 0;
    boolean ordered, nsCaught;
    while (true) {
        ordered = true;
        nsCaught = false;
        for (int i = start; i < stop; i++) {
            if (i > 1) {
                if (!nsCaught && arr[i - 2] > arr[i - 1]) {
                    ordered = false;
                    start = i - 2;
                    nsCaught = true;
                }
            }
            if (arr[i] > arr[i + 1]) {
                int hold = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = hold;
                control = i;
            }
        }
        System.out.println(Arrays.toString(arr));
        if (ordered) return arr;
        stop = control;
    }
}

但正如@Daniel Fischer在之前的回答中所说，它对较大的数组没有多大作用。

于 2017-10-27T10:40:00.500 回答
0

在上面的示例中，数组在第 3 遍后排序，但我们仍将继续第 4、第 5 遍。假设如果数组已经排序，那么就不会发生交换（因为相邻的元素总是按顺序排列的），但我们仍然会继续遍历，仍然会有 (n-1) 次遍历。

如果我们可以确定数组已排序，那么我们应该停止执行进一步的遍历。这是对原始冒泡排序算法的优化。

如果在特定传递中没有交换，则意味着数组已排序，因此我们不应该执行进一步的传递。为此，我们可以有一个标志变量，在每次传递之前设置为真，并在执行交换时设置为假。

void bubbleSort(int *arr, int n) {
    for (int i = 0; i < n; i++) {
        bool flag = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                flag = true;
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
        // No Swapping happened, array is sorted
        if (!flag) {
            return;
        }
    }
}
于 2018-05-20T18:35:33.453 回答
0 
public class Tester {
    static boolean bubbleFlag = true;

    public static void main(String[] args) {
        int array[] = new int[]{1, 9, 2, 3, 4, 5, 6};
        bubbleSort(array);
    }

    private static void bubbleSort(int... array) {
        System.out.println("Before Sorting: " + Arrays.toString(array));

        for (int i = 0; i < array.length - 1; i++) {
            if (i > 0) if (bubbleFlag) break;

            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) array = swap(j, j + 1, array);
                System.out.println("Iteration "+j+" :"+Arrays.toString(array));
            }
            bubbleFlag = true;
        }
    }

    private static int[] swap(int i1, int i2, int... is) {
        bubbleFlag = false;
        is[i1] = is[i1] + is[i2];
        is[i2] = is[i1] - is[i2];
        is[i1] = is[i1] - is[i2];
        return is;
    }
}

输出：

Before Sorting: [1, 9, 2, 3, 4, 5, 6]
Iteration 0 :[1, 9, 2, 3, 4, 5, 6]
Iteration 1 :[1, 2, 9, 3, 4, 5, 6]
Iteration 2 :[1, 2, 3, 9, 4, 5, 6]
Iteration 3 :[1, 2, 3, 4, 9, 5, 6]
Iteration 4 :[1, 2, 3, 4, 5, 9, 6]
Iteration 5 :[1, 2, 3, 4, 5, 6, 9]
于 2018-07-26T07:24:32.683 回答
0

我认为这就是你所需要的。关键是只考虑数组，直到最后一次交换发生的索引（新）。

public static void bubbleSort(int[] a) {
    int i, n, newn;
    n = a.length;
    while (n > 0) {
        newn = 0;
        for (i = 1; i < n; i++) {
            if (a[i - 1] > a[i]) {
                temp = a[i];
                a[i] = a[i - 1];
                a[i - 1] = temp;
                newn = i;
            }
        }
        n = newn;
    }
    return a;
}
于 2019-06-30T19:59:15.377 回答
0

这是使用 while 循环的最简单、最佳和最优的冒泡排序算法。它按升序从左到右对给定数组形式中的数字进行排序。它非常易于理解且易于实施。

private static int[] bubbleSort(int[] array) {
    int length = array.length - 1;
    int index = 0;

    while (index < length) {
        if (array[index] > array[index + 1]) {
            swap(array, index, index + 1);
        }
        index++;

        if (index == length) {
            index = 0;
            length--;
        }
    }
    return array;
}

private static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

public static void main(String[] args) {
    int[] arr = {4, 2, 3, 1, 5, 6};
    System.out.println(Arrays.toString(arr));
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}

输出：

[4, 2, 3, 1, 5, 6]
[1, 2, 3, 4, 5, 6]
于 2019-07-23T10:58:56.720 回答
0

您可以使用单个do-while-loop而不是两个嵌套的 for-loop并将逻辑移动到内部if-statement 中。通过通过索引，后续通过更短。

public static void bubbleSort(int[] arr) {
    boolean swapped = false;
    int i = 0, pass = 0;
    do {
        if (i < arr.length - 1 - pass) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
            i++;
        } else {
            i = 0;
            pass++;
            swapped = false;
        }
    } while (i < arr.length - 1 - pass || swapped);
}

public static void main(String[] args) {
    int[] arr = {6, 1, 5, 8, 4, 3, 9, 2, 0, 7};
    System.out.println(Arrays.toString(arr));
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}

输出：

[6, 1, 5, 8, 4, 3, 9, 2, 0, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

另请参阅：冒泡排序输出不正确

于 2021-04-06T16:08:23.373 回答
0

我没有代码，但您可以使用 n 位来跟踪在最后一次传递中执行交换的位置。或者，效率较低，使用单个变量来跟踪执行第一次交换的位置。我们不需要重新比较未交换的元素——它们是相同顺序的相同元素，所以我们知道比较将是相同的，我们可以安全地跳过它们。

直觉上我觉得，即使进行了上述优化，冒泡排序仍然无法击败二进制插入排序的比较，并且会引入更多的分支逻辑（在辅助空间之上）来跟踪交换。所以这可能不值得研究，除非有人好奇。

于 2021-10-06T20:02:00.453 回答
-1

优化的冒泡排序，只有 1 个 for 循环

/*Advanced BUBBLE SORT with ONE PASS*/
/*Authored by :: Brooks Tare  AAU*/
public class Bubble {
    public int[] bubble(int b[]) {
        int temp, temp1;
        for (int i = 0; i < b.length - 1; i++) {
            if (b[i] > b[i + 1]) {
                ///swap(b[i],b[i+1]);
                temp = b[i];
                b[i] = b[i + 1];
                b[i + 1] = temp;
                
                // Checking if there is any number(s) greater
                // than the current number. If there is swap them.
                while (i > 0) {
                    if (b[i] < b[i - 1]) {
                        ///swap(b[i]<b[i-1])
                        temp1 = b[i];
                        b[i] = b[i - 1];
                        b[i - 1] = temp1;
                        i--;
                    } else if (b[i] > b[i - 1]) {
                        i--;
                    }
                }
            } else {
                continue;
            }
        }
        return b;
    }

    ///the following is a function to display the Array 
    public void see(int[] a) {
        for (int j = 0; j < a.length; j++) {
            System.out.print(a[j] + ",");
        }
    }

    public static void main(String[] args) {
        ///You can change the Array to your preference..
        // u can even make it dynamic
        int b[] = {5, 1, 4, 2, 0, 3};
        int v[] = new int[100];
        Bubble br = new Bubble();
        v = br.bubble(b);
        br.see(v);
    }
}
于 2018-08-17T15:01:37.937 回答