需要在数组的开头移动所有小于1的值(没有SORT,并且需要没有第二个数组的解决方案)
例如:
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;
}
std::stable_partition
[如果您想自己实现它,请注意,就地稳定分区不能比std::stable_partition(std::begin(arr), std::end(arr),
[](double d) { return d < 1; });
时更好。任何运行时间为O(N log N)
的算法均不正确。
基本思想是使用分而治之(类似于快速排序):
O(N)
[// Returns iterator to the first element of the second group
template<class It, class Pred>
It stable_partition(It first, It last, Pred pred) {
if (first == last)
return last;
if (last - first == 1)
return pred(*first) ? last : first;
// Split in two halves
auto mid = first + (last - first) / 2;
// Partition the left half: [TTTTTFFFFF]
// ^ left
auto left = stable_partition(first, mid, pred);
// Partition the right half: [TTTTTFFFFF]
// ^ right
auto right = stable_partition(mid, last, pred);
// Rotate the centeral part: [TTTTTFFFFF] [TTTTTFFFFF]
// [^ ^)
return std::rotate(left, mid, right);
}
本身很容易通过三个反转实现。