c++ - 根据条件划分数组中的元素

Question

据我所知，它被称为(3,4 年前)分区步骤，它是快速排序的一部分，但我不确定。

我必须根据条件拆分数组中的元素，例如条件:x < 5

对于数组:

7,2,7,9,4,2,8

结果是:

2,4,2,7,7,8,9 

元素的顺序无关紧要。它应该在一个 for 循环内完成，而无需在内部嵌入 for 循环。

我正在寻找伪代码或 C++ 代码，以了解如何根据这种“枢轴”条件交换元素。

我已经设法创建的代码:

#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
#include <functional>
using namespace std;

template <typename T>

size_t partition(T arr[], size_t size, function<bool(T)> fun) {
    //here I would like to split it against the fun():boolean result
    return 4;
}

template <typename T>
void printTable(T arr[], size_t size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

template <typename T> bool less10(T a) {
    return a < 10;
}
int main(){
    cout << "BLABLA" << endl;
    int arri[] = { 1, 20, 3, 50, 6, 7 };
    size_t sizi = sizeof(arri) / sizeof(arri[0]); printTable(arri, sizi);
    size_t fi = partition(arri, sizi, (function<bool(int)>)less10<int>);
    printTable(arri, sizi);
    cout << "index: " << fi << endl; cout << endl;
    double arrd[] = { 1, 20, 3, 50, 6, 7 };
    size_t sizd = sizeof(arrd) / sizeof(arrd[0]); printTable(arrd, sizd); function<bool(double)> lambda =
        [](double x) -> bool {return x > 10; }; size_t fd = partition(arrd, sizd, lambda); printTable(arrd, sizd);
    cout << "index: " << fd << endl;
    system("PAUSE");
    return 0;
}

Answer 1

你可以这样写

#include <algorithm>

int main()
{
    int ar[] = {7,2,7,9,4,2,8};

    std::partition(std::begin(ar), std::end(ar), [](int val) {
        return val < 5; });
}

如果 std::partition 的实现很重要，你可以检查一个简单的实现

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred)
{
  while (first!=last) {
    while (pred(*first)) {
      ++first;
      if (first==last) return first;
    }
    do {
      --last;
      if (first==last) return first;
    } while (!pred(*last));
    swap (*first,*last);
    ++first;
  }
  return first;
}