首页 > 代码库 > 【算法28】冒泡排序中的交换次数问题
【算法28】冒泡排序中的交换次数问题
问题描述
题目来源：Topcoder SRM 627 Div2 BubbleSortWithReversals
给定待排序数组A，在最多反转K个A的不相交子数组后，对A采用冒泡排序，问最小的swap次数是多少？冒泡排序的伪代码如下：
BubbleSort(A):
循环len(A) - 1次：
for i from 0 to len(A) - 2:
if (A[i] > A[i+1])
swap(A[i], A[i+1])
问题分析
首先，容易分析得到：对于任意待排序数组A，其采用冒泡排序所需要的swap次数=A中逆序对的个数。这是因为冒泡排序的过程就是对于任意两个元素，判断两个元素是否逆序（即小的元素排在大元素之后），如果逆序，则swap。上面的结论是显而易见的。
【思路1】接下来，问题就变为，求给定数组在reverse最多K个子数组之后，A中的逆序对数的最小值。给定一个数组A，求解逆序对数是比较简单的，直接两个for循环判断并计数就可以了。问题难在允许reverse最多K个子数组，这样我们需要依次考虑reverse 0, 1, 2, ..., K个子数组，假设我们此时考虑reverse k (0 =< k <= K) 个子数组, 我们还需要去找到是哪k个子数组，reverse后计算逆序对数，这情况就多了去了，很难理清头绪，这条路似乎难以走通。
【思路2】我们意识到这是一个典型的优化问题，对于复杂优化问题动态规划可是神器，让我们来试试看。运用动态规划需要满足两个条件:（1）重叠子问题，即在求解最优解的过程中会反复求解一些规模更小的子问题；（2）最优子结构，即当前问题的最优解可以通过其子问题的最优解得到。
考虑由下标j贡献的逆序对数 = 下标i的个数满足i < j && A[i] > A[j]， 即在j之前且与A[j]成逆序关系的元素个数。容易观察到下标j前面的元素排序并不影响下标j贡献的逆序对数，因为j前面的元素无论如何排序，大于A[j]的元素的个数是不会变的。定义子问题 f(x, k) 表示在最多reverse k个不重叠子数组后，由所有大于x的下标j贡献的逆序对数，即\[f(x, k) =\sum_{j >= x}^{n} contribution(j), with\ revserse\ at\ most\ k\ disjoint\ subarrays\ \] 那么f(0, K)表示在最多reverse K个不重叠子数组后，由所有元素j >= 0构成的逆序对数，即为原问题的解。
[1] Base Case: f(n, k) = 0, k = 0, 1, ..., K, 因为没有大于等于n的下标。接下来分为两种情况，
[2] reverse的子数组中不包含x :此时f(x, k)的值等于有x贡献的逆序对数+y(y >= x + 1)贡献的逆序对数，由于reverse的数组不包含x，而前面已经说明在x前的子数组无论如何reverse是不会影响x贡献的逆序对数的，因而reverse的子数组在x之后最多有k个，从而\[f(x, k) = contribution(x) + f(x + 1, k)\]
[3] reverse 的子数组中包含x: 此时我们只需要考虑从x开始reverse的子数组即可（为什么？因为其他情况可以转化为这种情况），假设我们reverse了子数组(A[x], A[x+1],...A[y-1], A[y])从而得到子数组(A[y], A[y-1], ..., A[x + 1], A[x]), 那么我们需要计算所有的contribution(j)， x <= j <= y. 为了计算contribution(j) 我们可以取子数组B = (A[0], A[1], ..., A[x], ....A[y]), 在B中计算contribution(j)。 之后问题转化为在y+1之后的数组最多reverse (k - 1)个子数组 (因为已经用掉一次reverse)后的逆序对数, 即\[f(x, k) = \sum_{j >= x}^{y}contribution(j) + f(y + 1, k - 1)\] 遍历y = x + 1, ..., n的每个取值，取所有情况中最小的f(x,k)。
[4] 在[2]和[3]情况中选择最小的f(x, k).
程序源码
经过上面的分析，我们可以采用bottom to up的方法给出如下源码
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <map> 5 #include <set> 6 #include <algorithm> 7 #include <functional> 8 #include <cstdio> 9 #include <cstdlib>10 using namespace std;11 12 // nSwap == nNiXuNumber13 class BubbleSortWithReversals14 {15 public:16 // return the number of nixu with index >= x17 int getCurNiXuNumber(vector<int> A, int x)18 {19 int n = A.size();20 int cnt = 0;21 for (int i = x; i < n; ++i)22 {23 for (int j = 0; j < i; ++j)24 {25 if (A[j] > A[i])26 {27 cnt++;28 }29 }30 }31 32 return cnt;33 }34 35 // DP solution:36 // Define: f(x, k) = the number of nixu with indices i >= x that can reverse37 // at most k subarray without overlap, thea number of xinu at index i,38 // is the number of index j with j < i && A[j] > A{i]39 //40 // Then the f(0, K) is the answer of original problem41 //42 // Base Case: f(n, k) = 0 with k = 0, 1, 2, ... MAX_K;43 // Recursive relationship:44 // Case 1: A[x] is not in the reversed subarray, which means A[x] stays in index45 // x after the most k reverses of subarray, Note that the order of elems46 // A[j] with j < x do not affect the the number of Nixu at index x47 // So in this case48 // f(x, k) = The number of nixu at index x + f(x + 1, k)49 // Case 2: A[x] is in the reversed subarray, we only need to consider the reversed 50 // subarray (A[x], A[x+1], ..., A[y-1], A[y]), cause if the reversing 51 // start before index x such as (A[a], A[b], A[c], A[x], ...), then when52 // x = a, it equals exactly the situation of current time53 // So in this Case:54 // We first revere (A[x], A[x+1], ..., A[y-1], A[y]) to obtain55 // (A[0],...A[x-1], A[y], A[y-1], ..., A[x+1], A[x])56 // Then we caculate The number of nixu at index x + f(y+1, k-1)57 // f(x, k) = the number of nixu at x + f(y + 1, k - 1);58 // Compare case 1 and case 2 to get the minimum59 60 61 int getMinSwaps(vector<int> A, int K)62 {63 int n = A.size();64 int f[MAX_K][MAX_K] = {0}; 65 // init66 for (int k = 0; k < MAX_K; ++k) f[n][k] = 0;67 68 //69 for (int x = n - 1; x >= 0; --x)70 {71 for (int k = 0; k <= K; ++k)72 {73 // Case 1: x not in the reversed subarray74 vector<int> B1(A.begin(), A.begin() + x + 1);75 f[x][k] = getCurNiXuNumber(B1, x) + f[x+1][k];76 77 // Case 2: x in the reversed subarray78 if (k >= 1)79 {80 for (int y = x + 1; y < n; ++y)81 {82 vector<int> B2(A.begin(), A.begin() + y + 1);83 reverse(B2.begin() + x, B2.begin() + y + 1);84 f[x][k] = min(f[x][k],85 getCurNiXuNumber(B2, x) + f[y+1][k-1]);86 }87 }88 }89 }90 91 return f[0][K];92 }93 public:94 static const int MAX_K = 51;95 };
复杂度分析
子函数获取当前逆序对数的时间复杂度为 O(n^2), 主函数外层循环nk次, 对于case 1, 只需要计算x处的贡献，因而子函数在此处复杂度为O(n);对于case 2, 子函数需要计算在x,..., y的contribution, 而在i(x <= i <=y)处需循环ｉ次，从而复杂度为 $\sum_{y = x + 1}^{y < n} \sum_{i = x}^{y} i = O(n^2)$，从而总的时间复杂度为在case2时出现，为O(NK^3)。
参考文献
[1] Topcoder Editorial SRM 627
[2] Dynamic Programming