java 你能在一个数组索引中存储多个整数吗?

ee7vknir  于 2023-05-21  发布在  Java
关注(0)|答案(5)|浏览(111)

我正在尝试进行基数排序,我见过的一些算法有一个buckets[ ]数组,该数组应该将多个整数保存到bucket数组的一个索引中,下面是我所指的算法:

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

4bbkushb

4bbkushb1#

bucket本身就是int[](或List或任何可以存储多个项目的东西)。
你不能在一个索引中放入更多的东西。

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

如果有一个以上的int,就不再起作用。
最简单的可能是使用int[][]数组。现在左框中的每个索引都指向整个数组。这些数组也可以有不同的长度:
Java Jagged Array

sq1bmfud

sq1bmfud2#

是的,可以将多个int添加到数组中,但需要有一个数组,其中每个项目都是Object而不是int
比如...

// 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>();

当然,如果你不总是在一个桶中有<=3个项目,你可以只改变Bucket类,使用数组或List作为它的变量,而不是单独的int s。
你也可以使用多维数组…

// 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'

但是,如果您开始使用不同大小的桶,那么它会变得有点混乱,并且您需要进行更多的错误检查以确保……
1.当您尝试访问存储桶中的项目时,这些项目不是空的
1.当你向bucket中添加一个数字时,你需要检测第二维中下一个空的位置,这样你就不会覆盖已经在那里的int s。
正是由于这些原因,我建议使用基于对象的数组而不是多维数组。

xnifntxz

xnifntxz3#

两种情况创建存储桶

  • 这些数字不是唯一的
  • 基数排序在每个数字位置(十进制情况下为个位、十位、百位)上排序,然后继续到下一个数字-因此如果在第一个数字上排序将匹配,则为003和019。

第一种情况实际上只是第二种情况的退化。
请注意,根据您对数字排序的顺序,有几种基数排序变体。
太回答数据结构部分的问题-不,你不能,也不会存储多个值在每个索引。相反,每个桶通常表示为阵列的子序列。然后,每个桶由其开始的偏移表示(结束可以是隐式的)。

kxeu7u2r

kxeu7u2r4#

除了将存储桶表示为List或数组的可能性之外,还可以使用数组切片。在这种情况下,目标数组的总大小与输入数组相同。例如,bucket 0中有2个元素,bucket 1中有2个,bucket 2中有3个,bucket 3中有1个,bucket 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]

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

enxuqcxy

enxuqcxy5#

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

相关问题