对已根据元素绝对值排序的数组进行排序

---

在本文中，我们将对给定的数组进行排序。给定的数组已经根据元素的绝对值排序，我们只需要根据元素的真实值对数组进行排序。

在第一种方法中，我们将使用排序算法，例如归并排序、冒泡排序、插入排序、快速排序等等。在本例中，我们将使用内置的排序函数来排序我们的数组。

在第二种方法中，我们将使用双端队列。我们将正元素推入双端队列的前面，并将负元素推入双端队列的后面。这种方法允许我们无需执行任何排序算法即可获得排序后的数组。

问题陈述

给定一个包含N个整数的数组，这些整数已根据元素的绝对值排序，我们需要根据数组中元素的真实值对数组进行排序。

示例

输入

arr = {1, 2, -3, -8, 16}

输出

-8, -3, 1, 2, 16

解释

将输入数组按升序排序后，负值出现在数组的开头，我们得到最终的输出。

输入

arr = {8, -8, -8, 8}

输出

-8, -8, 8, 8

解释

由于 -8 小于 8，因此在排序后它应该出现在 8 之前。

输入

arr = {-2, -33, -71, 81, 93}

输出

-71, -33, -2, 81, 93

解释

负值在输出中将以相反的顺序出现。

方法一

在这种方法中，我们将使用排序技术对输入数组进行排序。我们可以使用多种排序技术，例如归并排序、快速排序、冒泡排序、选择排序、插入排序等等。解决方案的时间和空间复杂度将取决于所使用的排序技术的类型。在下面的示例中，我们将使用内置的排序函数来排序数组。

算法

• 步骤 1 − 将输入数组作为参数。

• 步骤 2 − 创建一个新数组 res，并将输入数组的元素复制到 res 中，并保持相同的顺序。

• 步骤 3 − 使用内置排序函数对新数组 res 进行排序。

• 步骤 4 − 返回排序后的数组。

示例

#include <bits/stdc++.h>
using namespace std;
vector<int> sort_abs_sorted(vector<int> &arr){
   vector<int> res = arr;
   sort(res.begin(),res.end());
   return res;
}
int main(){
   vector<int> arr = {-2, -33, -71, 81, 93};
   vector<int> sorted = sort_abs_sorted(arr);
   for(int i=0;i<sorted.size();i++)cout<<sorted[i]<<" ";
   return 0;
}

输出

-71 -33 -2 81 93

时间复杂度 − O(N*log(N))，其中 N 是数组中元素的数量。

空间复杂度 − O(N)，用于在新数组中存储元素

方法二

在这种方法中，我们将使用双端队列根据元素的真实值对数组进行排序。首先，我们将从左到右遍历原始数组。如果当前元素为正，我们将元素推入队列的后面。如果当前元素为负，我们将元素推入队列的前面。遍历所有元素后，我们将创建一个新的数组来存储排序后的元素。我们一个接一个地从双端队列中获取元素并将其添加到我们的最终数组中。

算法

• 步骤 1 − 创建一个双端队列。

• 步骤 2 − 从左到右遍历输入数组。

• 步骤 2.1 − 如果当前元素为正，则将其推入双端队列的后面。

• 步骤 2.2 − 如果当前元素为负，则将其推入队列的前面。

• 步骤 3 − 创建一个最终数组来存储排序后的元素。

• 步骤 3.1 − 从双端队列中弹出元素并将其添加到最终数组中。

• 步骤 3.3 − 返回排序后的数组。

示例

#include <bits/stdc++.h>
using namespace std;
vector<int> sort_abs_sorted(vector<int> &arr){
   vector<int> res;
   deque<int> deq;
   for(int i=0;i<arr.size();i++){
      if(arr[i]>=0)deq.push_back(arr[i]);
      else deq.push_front(arr[i]);
   }
   for(auto it:deq)res.push_back(it);
   return res;
}
int main(){
   vector<int> arr = {-2, -33, -71, 81, 93};
   vector<int> sorted = sort_abs_sorted(arr);
   for(int i=0;i<sorted.size();i++)cout<<sorted[i]<<" ";
   return 0;
}

输出

-71 -33 -2 81 93

时间复杂度 − O(N)，其中 N 是数组中元素的数量。

空间复杂度 − O(N)，用于在队列中存储元素。