使用带负值的计数排序？(降序)
对于x > 0，我有一个计数排序，它按降序排列数组。但是，当考虑负数时，我的实现逻辑就会分崩离析，因为我正在进入助手数组values中的负索引。我正在考虑以某种方式使用uint，但我对它不太熟悉。
我怎么能用一种计数的方式来克服这件事。
static void countingSort(int[] arr)
{
int i, j, max = -1; // I think it falls apart about here
int[] values;
for (i = 0; i < arr.Length; i++)
if (arr[i] > max) max = arr[i];
values = new int[max + 1];
//Here it reaches for a negative index when i = 2,looking for -6.
for (i = 0; i < arr.Max(); i++)
values[arr[i]]++;
i = 0; j = values.Length - 1;
while (i < arr.Length)
{
if (values[j] > 0)
{
values[j]--;
arr[i] = j;
i++;
}
else j--;
}
}我知道我的问题是帮助数组的索引。而且，由于我不想继续制作带有负索引的数组，所以我有点困惑。
您甚至可以在不将整个类实现为索引的情况下在c#中这样做吗？我知道在C语言中你可以这样做，它定义得很好：
来自C99§6.5.2.1/2:下标运算符[]的definition是E1E2与(*((E1)+(E2))相同)。
我的测试数组是{ 8, 5, -6, 7, 1, 4 }
我的预期输出是{ 8, 7, 5, 4, 1, -6 }
回答 4
Stack Overflow用户
发布于 2016-11-08 00:14:19
在您的示例中，您已经在扫描输入数组以找到最大值。所缺少的是，您也没有扫描输入数组以找到最小值。如果添加该值，然后知道最小值，则可以偏移数组索引的范围，以允许出现负数(如果只处理正数，甚至可能减小数组的大小)。
看起来是这样的：
static void Sort(int[] array)
{
int min = int.MaxValue, max = int.MinValue;
for (int i = 0; i < array.Length; i++)
{
if (array[i] < min)
{
min = array[i];
}
if (array[i] > max)
{
max = array[i];
}
}
int[] counts = new int[max - min + 1];
for (int i = 0; i < array.Length; i++)
{
counts[array[i] - min]++;
}
int k = 0;
for (int j = max; j >= min; j--)
{
for (int i = 0; i < counts[j - min]; i++)
{
array[k++] = j;
}
}
}请注意，这类排序的一个显著缺点是需要维护一个连续数组，该数组保存输入中所有可能的值。即使输入数组中只有两个元素，如果它们的值为int.MinValue和int.MaxValue，则需要一个16 get的中间数组(忽略一下使用int计算数组长度的整数运算会遇到麻烦)。
另一种方法是使用字典存储计数。这允许您避免为不存在的输入值分配内存。它还允许您只扫描一次输入，而不是两次(但是这样做的代价是，在添加新元素时必须重新分配其底层存储的数据结构，因此算法的复杂性并没有真正降低多少)。
看起来是这样的：
static void Sort(int[] array)
{
int min = int.MaxValue, max = int.MinValue;
Dictionary<int, int> counts = new Dictionary<int, int>();
for (int i = 0; i < array.Length; i++)
{
if (array[i] < min)
{
min = array[i];
}
if (array[i] > max)
{
max = array[i];
}
int count;
// If the key is not present, count will get the default value for int, i.e. 0
counts.TryGetValue(array[i], out count);
counts[array[i]] = count + 1;
}
int k = 0;
for (int j = max; j >= min; j--)
{
int count;
if (counts.TryGetValue(j, out count))
{
for (int i = 0; i < count; i++)
{
array[k++] = j;
}
}
}
}Stack Overflow用户
发布于 2016-11-08 00:05:51
实际上，它可以在一个非常容易的转变中完成，在这里，您需要更新排序：
static void countingSort(int[] arr)
{
int i, j, max = -1;
int[] values;
//get the highest absolute value to determine the size of the array
for (i = 0; i < arr.Length; i++)
if (Math.Abs(arr[i]) > max) max = Math.Abs(arr[i]);
//create double the max size array
values = new int[max*2 + 1];
//when reaching a value make a shift of max size
for (i = 0; i < arr.Length; i++)
values[arr[i]+max]++;
i = 0; j = values.Length - 1;
while (i < arr.Length)
{
if (values[j] > 0)
{
values[j]--;
//shift back when putting in the sorted array
arr[i] = j-max;
i++;
}
else j--;
}
}这样，假设您有一个{ -4 ,3,2}数组，您将创建一个大小数组(4*2+1)=9，因为最高的绝对值是-4，移位将是4，因此-4将位于索引0中，例如2将位于值数组的索引6中，这样您就可以避免问题并得到所需的结果。
Stack Overflow用户
发布于 2016-11-07 23:57:15
看看这个。sort。
问题在于"values[arri]++“。如果arri中的值返回负数，则它将无效。
一种可能是编写一个函数"Hash- key (arri)“，该函数接受数组中的任意数字，并将其转换为字典键值。您可以自己编写或使用库。
如果您使用的是C#，那么"System.Collections“有许多类来方便字典索引。
using System;
using System.Collections;
public class SamplesArrayList {
public static void Main() {
// Creates and initializes a new ArrayList.
ArrayList myAL = new ArrayList();
myAL.Add("Hello");
myAL.Add("World");myAL.Add("!")；
您的助手将被加载源"arr“数组中的数据。希望这能有所帮助。
https://stackoverflow.com/questions/40476521
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号