C ++将值移到数组的开头 [英] C++ shift values to begin of array

问题描述

需要在数组开头移动所有小于1的值(没有SORT，并且需要没有第二个数组的解决方案)

Need to move all values which is less than 1 in begin of array (WITHOUT SORT, and need solution without second array)

例如:

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}

有我的解决方案，但效果不佳，因为最终我们收到了:

There is my solution but it doesn't work very well, because at final we receive:

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

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

Values which less than 1, moves to begin of array, but 4 and 5 elements not in correct order

#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;
}

推荐答案

使用 :

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

---

如果您想自己实现它，请注意，就地稳定分区(使用比较和交换)不能比在O(N log N)时间内做得更好.任何具有O(N)运行时间的算法都是错误的.

---

If you want to implement it yourself, note, that in-place stable partition (using comparisons and swaps) cannot be done better than in O(N log N) time. Any algorithm with O(N) running time is incorrect.

采用分而治之的方法可以获得一种可能的解决方案:

One possible solution can be obtained with divide-and-conquer approach:

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本身可以很容易地通过三个反向实现.

It resembles quicksort, but here we do not actually sort the range. std::rotate itself can be easily implemented via three reverses.

这篇关于C ++将值移到数组的开头的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！