优化冒泡排序 [英] Optimized Bubble Sort

问题描述

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

I would like to know how else I can optimize bubble sort so that it overlooks elements that have already been sorted, even after the first pass.

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

我们观察到 [4,5,6] 已经按顺序排列了，我该如何修改我的代码，让它在下一次通过时忽略这 3 个元素?这意味着排序会更有效率吗?您是否建议使用递归方法?

We observe that [4,5,6] are already in sorted order, how can I modify my code so that it overlooks this 3 elements in the next pass? Which means the sort would be more efficient? Do you suggest a recursive method?

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

推荐答案

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

First of all, you have an out-of-bounds access:

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

对于j == a.length-1，所以循环条件应该是j .

for j == a.length-1, so the loop condition should rather be j < a.length-1.

但是，在冒泡排序中，你知道在 k 次通过后，最大的 k 元素被排序在 k数组，所以传统的冒泡排序使用

But, in Bubble sort, you know that after k passes, the largest k elements are sorted at the k last entries of the array, so the conventional Bubble sort uses

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 次.

Now, that would still do a lot of unnecessary iterations when the array has a long sorted tail of largest elements, say you have k,k-1,...,1 as the first k elements and k+1 to 100000000 in order after that. The standard Bubble sort will pass k times through (almost) the entire array.

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

But if you remember where you made your last swap, you know that after that index, there are the largest elements in order, so

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

对上面的例子进行排序，只遍历整个数组，剩下的只遍历一个(短)前缀.

would sort the above example with only one pass through the entire array, and the remaining passes only through a (short) prefix.

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

Of course, in general, that won't buy you much, but then optimising a Bubble sort is a rather futile exercise anyway.

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