大O - 冒泡排序

Question

我写了两个不同版本的冒号排序算法 - bubbleSort，你在教科书中看到的算法的传统版本，和sortIntArray，它与bubbleSort非常相似但是递归。

也许这是我的误解，但后一种算法调用本身让我觉得算法的效率不同于冒泡排序。有人可以向我解释这两者之间的区别吗？

private static int[] sortIntArray(int[] arr) {

    for(int i=0; i<arr.length-1; i++) {
        if(arr[i+1]<arr[i]) { // [i-2], [i-1], [i], [i+1], [i+2]
            printArr(arr);
            int temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
            sortIntArray(arr);
        }
    }
    return arr;
}

---

private static int[] bubbleSort(int[] arr) {

    boolean swap = false;
    while(!swap) {
        swap = true;
        for(int i = 0; i<arr.length-1; i++) {
            if(arr[i+1]< arr[i]) {
                printArr(arr);
                swap = false;
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
    }
    return arr;
}

---

/**
 * Returns an unordered integer array.
 * @return
 */
private static int[] getIntArray() {
    return new int[]{54, 899, 213, 2, 43, 8, 12, 11, 111, 43, 6, 44, 83, 3458};
}

Answer 1

我添加了一个静态计数器变量，我在每个方法中每次传递最内层循环时都会增加。因此对于sortIntArray，计数器的摘录将是：

for(int i=0; i<arr.length-1; i++) {
        o++;
        if(arr[i+1]<arr[i]) { // [i-2], [i-1], [i], [i+1], [i+2]
            ...

我还实现了一个不同的方法，基本上是维基百科中提供的冒泡排序，我改变了你的随机数组生成器来生成不同大小的数组：

private static int[] getIntArray() {
    int[] rand;
    if (MAX_SIZE - MIN_SIZE > 0) {
        rand = new int[new Random().nextInt(MAX_SIZE - MIN_SIZE) + MIN_SIZE + 1];
    } else {
        rand = new int[MIN_SIZE];
    }
    for (int i = 0; i < rand.length; i++) {
        rand[i] = new Random().nextInt(rand.length * 2);
    }
    return rand;
}

当列表大小为50时，这是一个示例结果。如果您自己构建测试代码，您将看到维基百科实现不仅可以保证排序，而且还提供了一个很好的基准：

Unsorted: [52, 48, 62, 47, 42, ...]
n: 50
Bubble sort: [3, 4, 6, 6, 11, ...]
O(n): 1960
Wikipedia sort: [3, 4, 6, 6, 11, ...]
O(n): 2450
Recursive sort: [3, 4, 6, 6, 11, ...]
O(n): 27391

有趣的是，可以清楚地看到，递归排序执行的是其他排序算法的更多迭代。基于10,000种类型的数据，我将其转储到CSV，看起来最大尺寸为30，n ^ 2项的系数是apx。 11.3对于严格的2次多项式拟合，而对于最大值50，它增加到大约19，这表明没有这样的m使得m * n ^ 2是算法的运行时复杂性的上限。

tl; dr：经验上，递归算法在时间上比O（n ^ 2）差。

Answer 2

实际上，新的实现似乎效率较低。传统的冒泡排序比较每次传递中的每对相邻元素，并且基本上将每个传递中最大的未排序元素过滤到数组中未排序部分的末尾。通道包括外环。

您的函数模拟以下迭代版本（实际上是插入排序）：

for (int i = 1; i < a.size(); ++i) {
    for (int j = i; j >= 1; --j) {
        if (a[j] < a[j - 1]) {
            int tmp = a[j];
            a[j] = a[j - 1];
            a[j - 1] = tmp;
        }
        else {
            break;
        }
    }
}

因为你在每次交换时调用递归函数，使用相同的数组并且递归调用在相同的索引处开始处理，所以你基本上模拟了一个额外的循环，（这可以使charged将遇到的反转从开头排序到那个使用递归调用。

可以这样想：对于您遇到的每次反转，您都会有一个递归调用。如果在循环中的任何一点，你有一个数组的初始排序部分，例如，让这个函数调用为f_1 2 3 7. 1 4 5 6

其中.表示数组已经排序到那一点。现在请注意，当循环达到7和1时，它会交换并递归调用函数，然后重复，以便1最终在前面结束（假设发生这种情况的调用是f_2），并且数组变为：

1 2 3 7. 4 5 6

请注意，f_2比f_1更深。此时，f_2没有返回，但是循环从1前进，这有效地模拟了f_1，但是更大的部分排序，这意味着当调用f_2返回时，整个数组将被排序。因此，f_2之前的额外递归调用不会做任何事情，只会占用堆栈空间。

您的算法的空间复杂度最差情况是O(n^2)，时间复杂度为O（n ^ 3），效率低于原始时间（对于时间复杂度，考虑具有n反演的大小n^2的反向排序数组，因此n^2递归调用，每个遍历完整数组，因此O(n^3)）。