计数排序将负整数和正整数作为输入(不允许使用Map)

Question

正如您在这段代码中看到的，我刚刚完成了如何使用计数排序对正整数进行排序作为输入的负数和正数必须对使用计数排序的数组。找到数组中的最低值，然后不允许接受输入。我不知道这样做的逻辑和解决方案是什么。

注意：如果我在输入中取任何负数。该值的输出显示为0。

输入：9, 8, 6, -7, 2, 1

输出：-7, 1, 2, 6, 8, 9

int k=0;
void Counting_Sort(int A[],int B[],int n)
{
int C[k+1];
for(int i=0; i<=k; i++)
{
C[i]=0;
}
for(int j=1; j<=n; j++)
{
C[A[j]]++;
}
for(int i=1; i<=k; i++)
{
C[i]+=C[i-1];
}
for(int j=n; j>=1; j--)
{
B[C[A[j]]]=A[j];
C[A[j]]=C[A[j]]-1;
}
}

//驱动程序代码

int main()
{
int n;
cout<<"Enter the size of the array :";
cin>>n;
int A[n],B[n];
for(int i=1; i<=n; i++)
{
cin>>A[i];
if(A[i]>k)
{
/*It will modify k if an element
occurs whose value is greater than k*/
k=A[i];
}
}
Counting_Sort(A,B,n);
/*It will print the sorted sequence on the
console*/
for(int i=1; i<=n; i++)
{
cout<<B[i]<<" ";
}
cout<<endl;
return 0;
}

Answer 1

对此也有一个简单的解决方案。只需将maxValue(假设这是数字可以具有的最大绝对值(添加到所有元素中，使用计数排序对它们进行排序，然后减去maxValue即可返回原始值。加法使它们都是非负的。

Answer 2

这个问题有一些限制，但可以通过将负数反转为正数并将负数和正数存储在两个不同的数组中来解决。然后你可以先打印负片阵列，然后打印正片阵列：

#include <iostream>
#include <cstring>
using namespace std;
const int maxval = 10000; //maximum absolute value of each element, you can change this
int positiveArr[maxval+1], negativeArr[maxval+1]; //positive and negative array
int main()
{
int n; cin >> n;
memset(positiveArr, 0, sizeof(positiveArr)); //set all value to 0
memset(negativeArr, 0, sizeof(negativeArr)); //set all value to 0
for (int i = 1; i <= n; i++)
{
int x; cin >> x; //input number;
if (x >= 0) //if x is non-negative
{
positiveArr[x]++; //add count of x
}
else
{
negativeArr[-x]++; //add count of -x
}
}
for (int i = maxval; i >= 1; i--) //printing the negative array
{
if (negativeArr[i] > 0)
{
for (int j = 1; j <= negativeArr[i]; j++) {cout << -i << " ";}
}
}
for (int i = 0; i <= maxval; i++) //printing the positive array
{
if (positiveArr[i] > 0)
{
for (int j = 1; j <= positiveArr[i]; j++) {cout << i << " ";}
}
}
return 0;
}

结果：

6
9 8 6 -7 2 1
-7 1 2 6 8 9

另一个测试：

19
-7 -9 0 1 -1 4 -3 -2 4 9 1 -9 -7 1 0 9 -7 -2 12
-9 -9 -7 -7 -7 -3 -2 -2 -1 0 0 1 1 1 4 4 9 9 12