题目：一个给定的不规则数组，其中包含了正负数（奇偶数），暂时将0处理为正数，请将所有的负数放到正数的前面？

解法一、

        不限制是否开辟空间，时间复杂度为O(n）。开辟一个同样大小数组，先遍历一遍算出负数个数，然后再遍历插入。

void calc_num_one() { std::vector<int> veAr = { 4, -1, 2, -4, 8, -9, -5, 8, 2, -4, -6, -8, 1, -2 }; copy(veAr.begin(), veAr.end(), ostream_iterator<int>(cout, " ")); cout << endl; std::vector<int> veArTmp(veAr); int iNegaNum = 0; for (auto &it : veAr) { if (it < 0) iNegaNum++; } int j = 0; for (int i = 0; i < veAr.size(); ++i) { if (veAr[i] >= 0) veArTmp[iNegaNum++] = veAr[i]; else veArTmp[j++] = veAr[i]; } veArTmp.swap(veAr); copy(veAr.begin(), veAr.end(), ostream_iterator<int>(cout, " ")); }

解法二、

       不能开辟空间，要求时间复杂度O(n)，空间复杂度O(1)。用两个下标，标记正数与负数，如果被标记的负数在正数前面，放弃处理，否则将正负数位置替换。

讯享网void calc_num_two() { std::vector<int> veAr = { 4, -1, 2, -4, 8, -9, -5, 8, 2, -4, -6, -8, 1, -2 }; copy(veAr.begin(), veAr.end(), ostream_iterator<int>(cout, " ")); cout << endl; int iPosiPos = 0; int iNegaPos = 0; while (iPosiPos < veAr.size() && iNegaPos < veAr.size()) { while (iPosiPos < veAr.size() && veAr[iPosiPos] < 0) iPosiPos++; while (iNegaPos < veAr.size() && veAr[iNegaPos] >= 0) iNegaPos++; if (iPosiPos >= veAr.size() || iNegaPos >= veAr.size()) break; if (iNegaPos > iPosiPos) //负数必须在正数前才处理 { int iTmp = veAr[iPosiPos]; veAr[iPosiPos] = veAr[iNegaPos]; veAr[iNegaPos] = iTmp; } iPosiPos++; iNegaPos++; } copy(veAr.begin(), veAr.end(), ostream_iterator<int>(cout, " ")); }

解法三、

讯享网

       解法二虽然效率很高，但是改变了元素的相对位置。例如，{4，-1,2，-4}经过解法二之后{-1，-4,2,4}。其中正数的相对位置变化。解法三欲不改变其相对位置。

       解法三分两步，第一步，从末尾元素开始，每次找到连续的负数集合和正数集合。第二步，将集合整体替换。

        如上图，第一次找到第一个黑框里的负数集合{-1，-8}和正数集合{9,2}，进行替换得到第二个黑框。然后找到第二个黑框里的负数集合{-3，-7，-1，-8}和正数集合{9}。以此类推。只需要遍历一遍，但是替换时候重复替换，时间复杂度OlogN，空间复杂度O(1)，并且保持相对位置。

void move_swap(std::vector<int> &veAr, int iLeft, int iRight) { while (iLeft < iRight) { int iTmp = veAr[iLeft]; veAr[iLeft++] = veAr[iRight]; veAr[iRight--] = iTmp; } } void move(std::vector<int> &veAr, int iPosiLeft, int iPosiRight, int iNegaLeft, int iNegaRight) { //cout << iPosiLeft << " " << iPosiRight << " " << iNegaLeft << " " << iNegaRight << endl; move_swap(veAr, iPosiLeft, iPosiRight); move_swap(veAr, iNegaLeft, iNegaRight); move_swap(veAr, iPosiLeft, iNegaRight); } void calc_num() { std::vector<int> veAr = {4,-1,2,-4,8,-9,-5,8,2,-4,-6,-8,1,-2}; copy(veAr.begin(), veAr.end(), ostream_iterator<int>(cout, " ")); cout << endl; int iNegaLeft = -1; //负数左界限 int iNegaRight = -1; //负数右界限 int iPosiPos = -1; //正数界限 int iLen = veAr.size() - 1; while (iLen >= 0) { if (veAr[iLen] >= 0) { if (iNegaLeft != -1 && iNegaRight != -1) { //处理末尾开始全是正数的情况 iPosiPos = iLen; } } else { if (iPosiPos != -1) { iLen++; move(veAr, iLen, iNegaLeft-1, iNegaLeft, iNegaRight); //处理完成之后，iNegaRight回退到当前负数最后一个位置 int iPosTmp = iNegaRight - iNegaLeft; iNegaLeft = iLen; iNegaRight = iLen + iPosTmp; iPosiPos = -1; } else { iNegaRight = iNegaLeft == -1 ? iLen : iNegaRight; iNegaLeft = iLen; } } iLen--; } if (iPosiPos != -1) //处理前边全是正数的情况 move(veAr, 0, iNegaLeft-1, iNegaLeft, iNegaRight); copy(veAr.begin(), veAr.end(), ostream_iterator<int>(cout, " ")); }