如何在C++中对数组进行自定义排序，但不对其中的一部分进行排序？

Question

我想对数组进行排序，但将其中的一部分排除在外。遗漏的部分应由开始索引(n)和结束索引(m)指定。这两个索引之间的所有字段，包括两个指定的索引，都不应进行排序。所有其他的，包括间隔前和间隔之后的，都应分类。

例如：

• 输入串行{10 , 4 , 11 , 7 , 6 , 20}
• 非排序间隔开始索引n = 1
• 非排序间隔结束索引m = 3，
• { 6 , 4 , 11 , 7 , 10 , 20 } 输出：

4, 11, 7值从索引1到3的字段没有排序。

#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上工作。

Answer 2

对于一个范围库来说，这是一个很好的展示案例，例如Boost.Range。

我们首先为要对固定部件进行左、右排序的部分创建一个切片范围。

auto left = arr | sliced(0, n);
auto right = arr | sliced(m, 6);

然后，我们创建一个新的范围，将这两个切片连接起来。

auto s = join(left, right);

把它分类

auto r = sort(s);

与输出一起，这给我们提供了以下使用Boost.Range的代码：

#include<iostream>
#include<algorithm>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptor/sliced.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/range/join.hpp>

using namespace boost;
using namespace boost::adaptors;

int main(){
  //define original and temp arrays
  int arr[6] = {10, 4, 11, 7, 6, 20};
  auto n = 2;
  auto m = 4;

  auto left = arr | sliced(0, n);
  auto right = arr | sliced(m, 6);
  auto s = join(left, right);

  auto r = sort(s);

  std::cout << "sorted range: ";
  boost::copy(r, std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;

  std::cout << "array: ";
  boost::copy(arr, std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;

  return 0;
}

运行代码打印

sorted range: 6,7,10,20, 
array: 6,4,11,7,10,20,

它也应该非常有效，因为不需要额外的数据移动或复制。我也觉得它很有表现力。

Answer 3

您可以取出要排序的元素，并将它们存储在临时数组中，然后以所需的形式重新构造数组。我已经提供了一个粗略的代码解决方案；但是，您应该考虑使用std::vector或另一个std容器(数组长度也是硬编码的，如果要更改原始数组的长度，则需要使用类似于sizeof(a)/sizeof(a[0])的内容)。

#include<iostream>
#include<algorithm>

int main(){
  //define original and temp arrays
  int arr[6] = {10, 4, 11, 7, 6, 20};
  int temp[3] = {0};


  //cycle through arr, remove the static elements, and store in temp array
  int k = 0;
  for(int i = 0; i < 6; i++)
  {
    if(i > 0 && i < 4)
    {
      continue;
    }
    temp[k] = arr[i];
    k++;
  }

  //sort the temp array
  std::sort(temp, temp + 3);

  //restructure the array by placing the static elements back into the original array
  k = 0;
  for (int i = 0; i < 6; i++)
  {
    if (i > 0 && i < 4)
    {
      continue;
    }
    arr[i] = temp[k];
    k++;
  }

  //print out the sorted array with static elements
  for(int i = 0; i < 6; i++)
  {
    std::cout << arr[i] << " ";
  }

  return 0;
}