如何在C++中自定义数组,但是将其中的一部分保留为未排序？

Question

我想对一个数组进行排序,但是将其中的一部分留下来.遗漏的部分应由起始索引(n)和结束索引(m)指定.这两个索引之间的所有字段,包括两个指定的字段,都不应进行排序.所有其他的,包括间隔之前的那些和之后的那些,应该被整理在一起.

例如:

• 输入序列号 {10 , 4 , 11 , 7 , 6 , 20}
• 非排序间隔开始索引 n = 1
• 非排序区间结束索引m = 3,
• 输出: { 6 , 4 , 11 , 7 , 10 , 20 }

索引1到3的字段与值4, 11, 7不进行排序.

#include <iostream>
#include <algorithm>
using namespace std;

int main () {
    int arr[5] = {10, 4, 11, 7, 6, 20};
    sort (arr,arr+5);
    for (int i = 0; i < 5; i++){
        cout << arr[i] << " ";
    }
    return 0;
}

我怎样才能做到这一点？

Answer 1

这是一种使用std::rotate和实现它的方法std::sort.
它将不应该排序的元素旋转到最后,然后对开始部分进行排序,然后将我们移动的元素旋转回来.

#include <iostream>
#include <iterator>
#include <array>
#include <algorithm>

int main() {
    std::array<int, 6> arr = {10, 4, 11, 7, 6, 20};

    unsigned from = 1;
    unsigned to = 3;

    unsigned distance = to - from + 1;

    if (to + 1 != arr.size())
        std::rotate(arr.begin(), arr.begin() + to + 1, arr.end());

    std::sort(arr.begin(), arr.end() - distance);

    std::rotate(arr.begin() + from, arr.end() - distance, arr.end());

    for (auto v : arr)
        std::cout << v << ' ';
}

我使用的是a std::array而不是c风格的数组.同样适用于std::vector.