c++ - 如何在 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 << ' ';
}

我使用了 std::array 而不是 c 风格的数组。也适用于 std::vector。