一个有多个数字数组的数组，最优的冒泡排序算法是什么？

Question

固定正整数 n 和 k。

令 A 为长度为 n 的数组，其中 A[i] 是长度为 k 的数组，每个条目都是 n-i。例如，当 n=5 且 k=1 时，这只是

[ [5] , [4] , [3] , [2] , [1] ]

对于 n=5 和 k=2，这是

[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]

目标是通过交换相邻数组中的数字（例如，将A [i] [j1]与A [i + 1] [j2]交换），以使每个A [i]的条目都为i + 1，直到排序此数组的数组为止。问题是：需要多少次交换，以及什么是最佳算法？

注意：有许多更好的排序算法可用。但是，对于此问题，我只对应用上述冒泡排序感兴趣。我只能交换相邻数组的条目，并且我只对必要的最小交换次数感兴趣。我很感谢所有关于其他排序算法的建议，但这是我试图理解的问题。

示例：

对于k = 1，这是众所周知的。交换次数是将A视为排列的倒置数，因此最小交换次数是二项式系数(n choose 2) = n(n-1)/2，可以通过交换任何顺序不正确的对来实现：A[i]>A[j]。对于第一个示例，这是一个最佳的冒泡排序：

[ [5] , [4] , [3] , [2] , [1] ]
[ [4] , [5] , [3] , [2] , [1] ]
[ [4] , [5] , [2] , [3] , [1] ]
[ [4] , [2] , [5] , [3] , [1] ]
[ [4] , [2] , [5] , [1] , [3] ]
[ [4] , [2] , [1] , [5] , [3] ]
[ [4] , [1] , [2] , [5] , [3] ]
[ [1] , [4] , [2] , [5] , [3] ]
[ [1] , [4] , [2] , [3] , [5] ]
[ [1] , [2] , [4] , [3] , [5] ]
[ [1] , [2] , [3] , [4] , [5] ]

对于 k=2，使用相同的策略需要进行 2 (n choose 2) 次交换。对于上面的例子，这意味着需要进行 20 次交换。但是有一种解决方案只需要进行 15 次交换：

[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]
[ [5,4] , [5,4] , [3,3] , [2,2] , [1,1] ]
[ [5,4] , [3,4] , [5,3] , [2,2] , [1,1] ]
[ [5,4] , [3,4] , [2,3] , [5,2] , [1,1] ]
[ [5,4] , [3,4] , [2,3] , [1,2] , [5,1] ]
[ [5,4] , [3,4] , [2,1] , [3,2] , [5,1] ]
[ [5,4] , [3,1] , [2,4] , [3,2] , [5,1] ]
[ [1,4] , [3,5] , [2,4] , [3,2] , [5,1] ]
[ [1,4] , [3,2] , [5,4] , [3,2] , [5,1] ]
[ [1,4] , [3,2] , [2,4] , [3,5] , [5,1] ]
[ [1,4] , [3,2] , [2,4] , [3,1] , [5,5] ]
[ [1,4] , [3,2] , [2,1] , [3,4] , [5,5] ]
[ [1,4] , [1,2] , [2,3] , [3,4] , [5,5] ]
[ [1,1] , [4,2] , [2,3] , [3,4] , [5,5] ]
[ [1,1] , [2,2] , [4,3] , [3,4] , [5,5] ]
[ [1,1] , [2,2] , [3,3] , [4,4] , [5,5] ]

这个解决方案对于n=5和k=2是最优的（通过暴力找到所有解的证明）。对于n=6，最佳解需要22次交换，但解决方案看起来不像n=5那样好（先向右走5步，然后向左走1步，再向右走5步等等），所以我仍然不知道最优策略，更不用说公式或更好的交换次数上界了。

我已经思考了几天，没有想出任何有启发性的东西。如果有人对这个问题有任何想法，请分享。我很想了解k=2情况的更多信息。对于一般情况的任何想法都更好。

编辑：如果我无法激发您对此问题的兴趣，请原谅，但这里有一个尝试：排序排列所需的冒泡排序次数是组合数学和数论中非常重要的统计量，称为排列的逆序数。您可以使用更好的算法对无序排列进行排序，但这是给您提供代数意义的算法。如果这没有帮助，也许这篇相关的SO文章可以：冒泡排序有什么用处？

---

更新:下面最老的答案给出了交换次数的下限和上限。第二老的答案提供的算法非常接近这个下限（通常达到它）。如果有人能够改进这个下限，或者更好的是，证明下面给出的算法是最优的，那将是很棒的。

- PengOne

---

我不明白。根据您的描述，当 k=1 时的结果应该是 [ [1], [2], [3], [4], [5] ]，这可以在2次交换中获得，而不是10次。我错在哪里了？ - svick

@svick：抱歉，我默认你只能交换相邻数组中的条目。现在我已经在问题中明确了这个假设。感谢您指出我的疏忽。 - PengOne

@Yochai：我完全不关心比较。我只允许执行的操作是相邻数组条目之间的交换，并且我想将这些操作最小化。 - PengOne

@Yochai：是的，主要是因为我们总是从“最坏情况”数组开始。 - PengOne

@PengOne - 你是对的 - 是我错了。 - user180247

Answer 1

这不是最佳答案，但我想分享我的尝试，因为有人可能会改进它。我没有考虑找到计算最小交换次数的公式，而是关注于最优的算法。该算法基于k = 2。

基本思路是基于信息增益。假设A={[i,j]：1<=i<=n, 1<=j<=n}表示一个配置。在每个步骤中，我们有4 * (n-1)种可能的交换方式，以从一种配置移动到另一种配置。例如，如果n=2（即A=[{2,2},{1,1}]），则我们有4种可能的交换A[0][0] <-> A[1][0]，A[0][0] <-> A[1][1]，A[0][1] <-> A[1][0]和A[0][1] <-> A[1][1]。因此，我们的目标是选择具有高信息增益的交换方式，以在需要从一种配置移动到另一种配置时使用。

棘手的部分将是“如何计算信息增益”。在我的解决方案（下面）中，信息增益基于值与其正确位置之间的距离。让我展示我的代码（用C++编写）来理解我想说的:

const int n = 5;
const int k = 2;

int gain(int item, int from, int to)
{
    if (to > from)
        return item - to;
    else
        return to - item ;
}

void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}

void print_config (int A[][k])
{
    cout << "[";
    for (int i=0; i<n; i++) {
        cout << " [";
        for (int j=0; j<k; j++) {
            cout << A[i][j] << ", ";
        }
        cout << "\b\b], ";
    }
    cout << "\b\b ]" << endl;
}

void compute (int A[][k], int G[][4])
{
    for (int i=0; i<n-1; i++)
    {
        G[i][0] = gain(A[i][0], i+1, i+2) + gain(A[i+1][0], i+2, i+1);
        G[i][1] = gain(A[i][0], i+1, i+2) + gain(A[i+1][1], i+2, i+1);
        G[i][2] = gain(A[i][1], i+1, i+2) + gain(A[i+1][0], i+2, i+1);
        G[i][3] = gain(A[i][1], i+1, i+2) + gain(A[i+1][1], i+2, i+1);
    }
}

int main()
{
    int A[n][k];
    int G[n-1][k*k];

    // construct initial configuration
    for (int i=0; i<n; i++)
        for (int j=0; j<k; j++)
            A[i][j] = n-i;

    print_config(A);

    int num_swaps = 0;
    int r, c;
    int max_gain;

    do {
        compute (A, G);

        // which swap has high info gain
        max_gain = -1;
        for (int i=0; i<n-1; i++)
            for (int j=0; j<k*k; j++)
                if (G[i][j] > max_gain) {
                   r = i;
                   c = j;
                   max_gain = G[i][j];
                }

        // Did we gain more information. If not terminate
        if (max_gain < 0) break;

        switch (c)
        {
            case 0: swap(A[r][0], A[r+1][0]); break;
            case 1: swap(A[r][0], A[r+1][1]); break;
            case 2: swap(A[r][1], A[r+1][0]); break;
            case 3: swap(A[r][1], A[r+1][1]); break;
        }

        print_config(A);
        num_swaps++;

    } while (1);
    cout << "Number of swaps is " << num_swaps << endl;
}

我按照上述代码分别对n=1、2、...和7进行了测试。这里分别是它们的答案（即交换次数）：0、2、5、10、15、23（非常接近）和31。我认为当n为偶数时，函数 gain() 的效果不好。您能否通过验证n=7时的交换次数来确认一下？在n为7时，您的方程的下限为31，因此这是最佳交换次数。

这里是 n=5 时的输出结果（因为您正在寻找模式）：

[ [5, 5],  [4, 4],  [3, 3],  [2, 2],  [1, 1] ]
[ [4, 5],  [5, 4],  [3, 3],  [2, 2],  [1, 1] ]
[ [4, 5],  [3, 4],  [5, 3],  [2, 2],  [1, 1] ]
[ [4, 5],  [3, 4],  [2, 3],  [5, 2],  [1, 1] ]
[ [4, 5],  [3, 4],  [2, 3],  [1, 2],  [5, 1] ]
[ [4, 3],  [5, 4],  [2, 3],  [1, 2],  [5, 1] ]
[ [4, 3],  [2, 4],  [5, 3],  [1, 2],  [5, 1] ]
[ [4, 3],  [2, 4],  [1, 3],  [5, 2],  [5, 1] ]
[ [4, 3],  [2, 4],  [1, 3],  [1, 2],  [5, 5] ]
[ [4, 3],  [2, 1],  [4, 3],  [1, 2],  [5, 5] ]
[ [1, 3],  [2, 4],  [4, 3],  [1, 2],  [5, 5] ]
[ [1, 3],  [2, 4],  [1, 3],  [4, 2],  [5, 5] ]
[ [1, 3],  [2, 1],  [4, 3],  [4, 2],  [5, 5] ]
[ [1, 1],  [2, 3],  [4, 3],  [4, 2],  [5, 5] ]
[ [1, 1],  [2, 3],  [2, 3],  [4, 4],  [5, 5] ]
[ [1, 1],  [2, 2],  [3, 3],  [4, 4],  [5, 5] ]

- badawi

---

这很有趣，谢谢！我的n=9的下限是51，所以如果你真的能得到53，那就非常接近并且可能是最优解。我需要再思考一下，但非常感谢你！ - PengOne

如果n = 7，该算法会给出下限31，这是最优解。 - badawi

Answer 2

我知道自问自答有点俗气，但我刚刚想到了解决方法，虽然它更接近于一个答案而不是问题的一部分。但是，这并不是一个完整的答案，也不会被接受，所以如果有人能改进，请发表您的想法。

对于k=2，最小交换次数m受到限制：

2 * (n choose 2) >= m >= (2n choose 2) / 3

为什么这个方法可行？

上限是通过对数组的第一个元素进行冒泡排序，然后对数组的第二个元素进行冒泡排序得出的。这部分并不那么棘手。

下限有点棘手，但是我是这样得出它的。让我们计算通道的数量，当一个较大的数字从较小的数字的左侧移动到该数字的右侧时，就会发生通道。这可以通过1次交换a和b来完成，其中a较大且在b左侧的数组中。如果a在一次交换中移动到与b相同的数组中，并在稍后的交换中继续移动，则可能需要2次交换。在这种情况下，要正确跟踪事物，请将通道分成两半进行计数。为了使计数更加容易，当两个相同的数字分开然后重新组合时，它也被视为一个通道。

在进行一次交换时，数组完全排序后需要(2n choose 2)通道，因此唯一的问题是一次交换可以发生多少通道。以下是一个简单的示例，其中交换了a和c：

... [a,b] , [c,d] ... 
... [c,b] , [a,d] ... 

现在让我们来计算可能发生的最大通行证数量：

• 由于 a > c，我们肯定会得到 1 个完整通行证。
• 如果 a > b，那么我们会得到 1/2 个通行证，因为 a 必须在某个时候被留在了 b 左边。
• 如果 a > d，那么我们会得到 1/2 个通行证，因为 a 在某个时候将会在 d 的右边。
• 如果 c < d，那么我们会得到 1/2 个通行证，因为 d 必须在某个时候被留在了 c 左边。
• 如果 c < b，那么我们会得到 1/2 个通行证，因为 b 将在某个时候在 c 右边。

因此，在交换中你能做到的最好情况是获得 3 个通行证（1 个完整和 4 个半个）。

为什么这不是一个完整的答案？

我不知道下限是否总是可达到的！ 我认为它不是，尽管进行了几次失败的尝试，我无法编写出一个能够实现它的算法。

- PengOne

---

你可以得到15个5和22个6，这些是你认为最好的数字。那么你会得到多少个7？ - Daniel

Answer 3

这里是我想到的一个直观算法。它给出了我认为最优解的构造性证明。

以下是算法：

我尝试了n=4、5、6、7、9，结果与badawi的相同：

思路如下：

1：选择一个不在最终位置上的极值（从1或n开始）

2：找到距离最终位置最近的极值（在我的示例中用箭头标注）

3： 如果它是最大元素之一，

那么将其移动到另一侧，并将每对最小元素向左移动

否则

将其移动到另一侧，并将每对最大元素向右移动。

注意：移位等效于将该值与每对最小（resp最大）元素“冒泡”。

4：回到步骤2，但如果您选择了其中一个较大的值，则选择一个较小的值，反之亦然。

它非常直观，似乎也很有效：

例如n=5：

11 22 33 44 55 
^
|
12 23 34 45 51 (4 moves) // shifted all larger numbers to the left
          ^
          |
52 13 24 43 51 (3 moves) // shifted all smaller numbers to the right
   ^
   |
52 34 24 35 11 (3 moves) // shifted all larger numbers to the left
          ^
          |
55 24 34 32 11 (3 moves) // smaller to the right
   ^
   |
55 44  33 22 11 (2 moves) // larger to left

总共有15步移动。

第二个例子 n=7：

11 22 33 44 55 66 77 // 6 moves
 ^
12 23 34 45 56 67 71 //5 moves
                ^
72 13 24 35 46 56 71 //5 moves
   ^
72 34 25 36 46 57 11 // 4 moves
                ^
77 24 35 26 36 45 11 //4 moves
   ^
77 45 36 26 35 42 11 //1 move
       ^       
77 65 34 26 35 42 11 //2 moves
         ^
77 65 34 56 34 22 11 //2 moves
          ^
77 66 54 53 34 22 11 //1 move
          ^
77 66 54 45 33 22 11 //1 move
          ^
77 66 55 44 33 22 11

总计：31

如果我讲得不清楚，请不要犹豫问我问题。

手动操作相当容易。您可以使用6或7尝试自己操作，或编写算法。

我使用6进行了尝试，结果为23。使用7则为31，使用9则为53，手动计算只需1分钟，无需计算机。

为什么这个解决方案是最优的：

每次将一个大元素移到相反侧面时，您将所有最小元素对中最小的那个向左移动。

因此，移动所有大元素不会使您失去任何移动所有最小元素的机会。

您始终朝“正确的方向”移动元素

而且，移动极端元素需要进行最少的移动。（这是因为算法采用距离其上一位置最近的极值，从而无需任何移动丢失）

对于小元素也是同样的道理。

该算法提供了最优的移动，因为它不做任何不必要的移动。

希望我没有犯任何错误。

这证明了Badawi的结果如您所预期的那样是最优的。

- Ricky Bobby

---

那么，没有任何反应吗？至少说一句话，看起来是否属实？ - Ricky Bobby

据我所知，这是巴达维算法。你所谓的“证明”并不是真正的证明，而更像是一种启发式方法。在你所做的移动类型中，这些是最好的，但不清楚是否有更好的移动可供选择。从信息论的角度来看，你希望最大化“传递”的次数，就像我的边界论证一样，但你的方法并不能保证全局优化，只能保证局部优化。因此，每一步都是最优的，但可能在关键位置进行次优的移动会得到更好的结果。 - PengOne

@PengOne 好的，谢谢。我明白为什么它不能证明最优性了。思考一下，证明这个解法是最好的唯一方法就是达到下界（但不是这种情况），就像在k=1的情况下演示的那样。 - Ricky Bobby