C++ 将值移至数组开头

Question

需要移动数组开头的所有小于 1 的值（不排序，并且需要没有第二个数组的解决方案）

例如：

START ARRAY: {-2.12, -3, 7.36, 6.83, -1.82, 7.01}

FINISH ARRAY: {-2.12, -3, -1.82, 7.36, 6.83, 7.01}

这是我的解决方案，但效果不是很好，因为最终我们收到：

FINISH ARRAY: {-2.12, -3, -1.82, 6.83, 7.36, 7.01}

小于 1 的值移至数组开头，但 4 和 5 个元素的顺序不正确

#include <iostream>

using namespace std;

int main() {
    double arr[6] = {-2.12, -3, 7.36, 6.83, -1.82, 7.01};

    cout << "Start array: " << endl;
    for (int x = 0; x < 6; x++) {
        cout << arr[x] << ", ";
    }

    int index=0;
    double temp;
    for (int i = 0; i < 6; i++) { 
        if (arr[i] < 1) {
            temp=arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
            index++;
        }
     }
    cout << endl << "FINISH ARRAY: " << endl;
    for (int x = 0; x < 6; x++) {
        cout << arr[x] << ", ";
    }



    return 0;
}

Answer 1

使用std::stable_partition：

std::stable_partition(std::begin(arr), std::end(arr), 
    [](double d) { return d < 1; });

如果您想自己实现它，请注意，就地稳定分区（使用比较和交换）不可能比及时完成更好O(N log N)。O(N)任何有运行时间的算法都是不正确的。

通过分而治之的方法可以得到一种可能的解决方案：

template<class It, class Pred>
It stable_partition(It first, It last, Pred pred) {
    // returns the iterator to the first element of the second group:
    // TTTTTFFFFFF
    //      ^ return value

    if (first == last)
        return last;
    if (last - first == 1) {
        if (pred(*first))     // T
            return last;      //  ^ last  
        else                  // F
            return first;     // ^ first
    }

    // Split in two halves
    const auto mid = first + (last - first) / 2;

    // Partition the left half
    const auto left = stable_partition(first, mid, pred);
    // TTTTTFFFFF
    //      ^ left
    //           ^ mid 

    // Partition the right half
    const auto right = stable_partition(mid, last, pred);
    // TTTTTFFFFF
    //      ^ right
    // ^ mid

    // Rotate the middle part: TTTTTFFFFFTTTTTFFFFF
    //                              ~~~~~~~~~~
    //                              ^ left    ^ right
    //                                   ^ mid
    const auto it =  std::rotate(left, mid, right);
    // TTTTTTTTTTFFFFFFFFFF
    //           ^ it
    return it;
}

它类似于快速排序，但这里我们实际上不对范围进行排序。std::rotate本身可以通过三个反向操作轻松实现。