java 您可以在一个数组索引处存储多个整数吗？

Can you store multiple integers at one array index?

提问by Gcap

I'm trying to do a radix sort and some algorithms I've seen have a buckets[ ] array that's supposed to hold multiple integers into one index of the bucket array, here is the algorithm I'm referring to:

我正在尝试进行基数排序，我见过的一些算法有一个 buckets[] 数组，该数组应该将多个整数保存到桶数组的一个索引中，这是我指的算法：

Is it really possible to have multiple integers in one index? And how so?
Or is there a simpler radix sort algorithm out there?

一个索引中真的可以有多个整数吗？怎么会这样？
或者是否有更简单的基数排序算法？

Thanks!!

谢谢！！

回答by wattostudios

Yes, it is possible to add multiple intto an array, but you would need to have an array where each item is an Objectrather than an int.

是的，可以将多个添加int到数组中，但是您需要有一个数组，其中每个项目都是一个Object而不是一个int。

For example...

例如...

// the items to store in the array, which contain 3 ints
public class Bucket {
    int number1 = -1;
    int number2 = -1;
    int number3 = -1;

    public void addInt(int number){
        if (number1 == -1){
            number1 = number;
        }
        else if (number2 == -1){
            number2 = number;
        }
        else if (number3 == -1){
            number3 = number;
        }
    }
}

// the array, as used in other classes
Bucket[] bArray = new Bucket[6]; // 6 items in the array, where each item is a Bucket that contains 3 ints

// assigning ints into the array
bArray[2].addInt(56); // add the int '56' to the bucket at index '2' of the array

// You could also use other Array-like structures
ArrayList<Bucket> bList = new ArrayList<Bucket>();

Of course, if you don't always have <=3 items in a bucket, you could just change the Bucket class to use an array or a Listas its variable rather than separate ints.

当然，如果您的存储桶中并不总是 <=3 项，您可以更改 Bucket 类以使用数组或 aList作为其变量，而不是单独的ints。

You could also use multi-dimensional arrays...

您还可以使用多维数组...

// creating the buckets
int[][] buckets = new int[6][3];

// assigning ints into the array
bArray[2][0] = 56; // add the int '56' to the bucket at index '2' of the array, position '0'

It would get a little messy, however, if you start playing around with different-sized buckets, and you'd need to do more error-checking to ensure that...

但是，如果您开始使用不同大小的存储桶，它会变得有点混乱，并且您需要进行更多的错误检查以确保......

1. The items in the bucket aren't empty when you try to access them
2. When you're adding a number to a bucket, you need to detect the next position in the second dimension that is empty, so you don't overwrite the ints that are already in there.

1. 当您尝试访问时，存储桶中的项目不为空
2. 当您向桶中添加一个数字时，您需要检测第二维中的下一个空位置，因此您不会覆盖int已经在那里的s。

If is for these reasons why I would recommend using an Object-based array over a multi-dimensional array.

如果出于这些原因，我建议在多维数组上使用基于对象的数组。

回答by DrC

Two cases create buckets

两种情况创建桶

• the numbers aren't unique
• radix sort sorts on each digit position (ones, tens, hundreds in the decimal case) before going on to the next one - so 003 and 019 if sorting on the first digit will match.

• 这些数字不是唯一的
• 基数排序对每个数字位置（十进制情况下的个、十、百）进行排序，然后再继续下一个 - 因此，如果第一个数字的排序匹配，则为 003 和 019。

The first case is really just a degenerate case of the second.

第一种情况实际上只是第二种情况的退化情况。

Note that there are a couple of radix sort variants depending on which order you sort the digits in.

请注意，根据您对数字进行排序的顺序，有几种基数排序变体。

Too answer the data structure part of the question - no you can't and wouldn't store multiple values at each index. Instead, each bucket is typically represented as a sub-sequence of the array. Each bucket is then represented by the offset of its start (the end can be implicit).

太回答问题的数据结构部分 - 不，您不能也不会在每个索引处存储多个值。相反，每个桶通常表示为数组的一个子序列。然后每个桶由其开始的偏移量表示（结束可以是隐式的）。

回答by zapl

a bucketwould be an int[](or Listor anything that can store multiple items) itself.

abucket将是一个int[]（或List任何可以存储多个项目的东西）本身。

You can't put more that one thing into 1 index.

您不能将更多的一件事放入 1 个索引中。

int[] array = new array[6];
int value = array[5];

would no longer work if there was more than one int.

如果有多个 int 将不再起作用。

The easiest is probably to use an int[][]array. Now each index in the left box refers to a whole array. Those arrays can be different length too:

最简单的方法可能是使用int[][]数组。现在左边框中的每个索引都指向一个完整的数组。这些数组的长度也可以不同：

Java Jagged Array

Java 锯齿状数组

回答by Patricia Shanahan

In addition to the possibility of representing a bucket as a List or array, it is possible to use an array slice. In this case, the destination array is the same total size as the input array. For the example, you have 2 elements in bucket 0, 2 in bucket 1, 3 in bucket 2, 1 in bucket 3, and 2 in bucket 5.

除了可以将桶表示为列表或数组之外，还可以使用数组切片。在这种情况下，目标数组与输入数组的总大小相同。例如，您在存储桶 0 中有 2 个元素，在存储桶 1 中有 2 个元素，在存储桶 2 中有 3 个元素，在存储桶 3 中有 1 个元素，在存储桶 5 中有 2 个元素。

Bucket 0 : d[0], d[1]
Bucket 1 : d[2], d[3]
Bucket 2 : d[4], d[5], d[6]
Bucket 3 : d[7]
Bucket 5 : d[8], d[9]

Doing it this way, the sort has to track the next index for each bucket.

这样做，排序必须跟踪每个桶的下一个索引。

回答by Kevin Melkowski

Wow, array's and lists are not the way to implement a radix sort. Yes lists work, but it slows it down, when I did that, it was slower than a merge sort. Best way is to implement a frequency array as part of a counting sort per each byte. I posted my code here, only in reference to parallel sorting. Hope it helps.

哇，数组和列表不是实现基数排序的方法。是的列表工作，但它减慢了它，当我这样做时，它比合并排序慢。最好的方法是实现一个频率数组，作为每个字节计数排序的一部分。我在这里发布了我的代码，仅参考并行排序。希望能帮助到你。