优化的气泡排序

optimization java recursion bubble-sort

2022-09-03 05:13:24

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

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

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

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

答案 1

首先，您具有越界访问权限：

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

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

但是，在气泡排序中，您知道在传递之后，最大的元素在数组的最后一个条目处排序，因此传统的气泡排序使用kkk

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,...,1kk+1100000000k

但是，如果您还记得上次进行掉期的位置，您就会知道在该索引之后，有最大的元素按顺序排列，因此

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

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

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

答案 2

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