0

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:

here is the algorithm I'm referring to

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

4

5 回答 5

0

Yes, it is possible to add multiple int to an array, but you would need to have an array where each item is an Object rather than an 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 List as its variable rather than separate 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.

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

于 2012-11-30T01:33:12.577 回答
0

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.

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).

于 2012-11-30T01:34:23.433 回答
0

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

于 2012-12-17T22:07:44.503 回答
0

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

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

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

如果有多个 int 将不再工作。

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

Java 锯齿状数组

于 2012-11-30T01:43:52.133 回答
0

除了可以将存储桶表示为列表或数组之外，还可以使用数组切片。在这种情况下，目标数组与输入数组的总大小相同。例如，存储桶 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]

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

于 2012-11-30T02:06:19.233 回答