使用链接列表的桶排序

我想在Java中实现桶排序以整理一个整数数组。我正在尝试使用链表作为我的桶，但在理解如何做时遇到了一些麻烦。任何人都可以提供实现吗？使用链接列表的桶排序

我已经提供了这个算法，但它并没有多大意义，对我说： enter image description here

来源

2014-02-15 user2276280

检查这个网站可能会有所帮助 https://jlmedina123.wordpress.com/2014/04/10/bucket-sort/ –

既然你没有代码可以分析，我会给出一个写出来的答案。创建一个包含两个数字（0-9,10-19等）之间的范围的Bucket类，一个插入方法（按顺序插入）和一个空数组。然后创建桶的名单像这样：

enter image description here

遍历输入列表并插入每个号码存入遗愿清单内相应的桶。当你插入值时，它会为你排序。最后，获取所有Bucket的数组，然后合并输出列表。

这里是一个循序渐进的过程关闭的Wikipedia：

设定的最初为空的“桶”的阵列。
Scatter：遍历原始数组，将每个对象放在它的存储桶中。
对每个非空桶进行排序。
收集：按顺序访问存储桶并将所有元素放回到原始数组中。

这是你提供的算法：

enter image description here

这个简单的转换为：

A是输入阵列，其必须进行排序
n是长度的输入阵列A
您必须将输入数组A的所有元素插入到您的存储桶列表中B
现在为存储桶列表中的每个存储桶订购B。
创建一个新的列表/数组返回，这将是所有有序的桶名单。

注意：你做第3步根据您的实现步骤4实际上可以发生。

这个算法并没有深入你必须编码的复杂细节。这只是帮助您入门的简单指南。

来源

2014-02-15 20:32:21

我将如何确定要创建的桶数。我的数组的最大值可以是任何给定的整数。例如，在一个案例中，我可能有一个[20,45,10,1]的数组。在这种情况下，我可能会创建五个桶。但是，如果我有这种情况：[2000,1,200,50]？ – user2276280

在循环输入列表时创建该范围的桶。如果您看到2000并且其中不存在Bucket，请创建一个2000-2009 Bucket。你不应该需要做所有的值0-1999 ...正是你需要的。确保你保持你的桶的名单秩序。此外，你可以随时选择自己喜欢的范围（这是一个设计决定）。你可以使它相对，或者你可以对它进行硬编码。我将首先对它进行硬编码（意思是始终执行10的范围），因为它会使实现更简单。 –

你可能会开始分析这个：bucket example

来源

2014-02-15 20:25:07 Elfentech

好了，我不知道Java，但仍我可以给你算法。

最简单的方法是以数组形式制作存储桶，其中每个数组索引指向一个空的链接列表。

for each integer : 
    integer goes to bucket i // bucket number depends on your implementation 
    pointer = bucket[i] 

    while pointer is not NULL 
     pointer = pointer->next 

    allocate new node 
    pointer points to this node 
    pointer.data = integer 
    pointer.next = NULL

来源

2014-02-15 20:29:28

你需要制定的一些方法哪个桶要排序的需要进入每一个元素 - 您可以创建一个给你，你可以调用这样做一些常见方法的接口：

public interface Indexable { 
    public int getIndex(); 
}

然后你可以实现一个桶排序算法是这样的：

public static <T extends Indexable> LinkedList<T> BucketSort(ArrayList<T> listToSort) 
{ 
    // work out how many buckets you need. 
    int max = 0; 
    for (T listElement : listToSort) 
     max = Math.max(max, listElement.getIndex()); 

    // initialise the buckets. 
    ArrayList<LinkedList<T>> buckets = new ArrayList<LinkedList<T>>(max); 
    for (int i = 0; i <= max; ++i) 
     buckets.add(new LinkedList<T>()); 

    // add items to the buckets. 
    for (T listElement : listToSort) 
     buckets.get(listElement.getIndex()).addLast(listElement); 

    // concatenate the buckets into a single list. 
    LinkedList<T> result = new LinkedList<T>(); 
    for (LinkedList<T> bucket : buckets) 
     result.addAll(bucket); 

    return result; 
}

测试此使用Indexable接口存储整数并将其分配给基于单位数字水桶的实现：

public static class IndexableInteger implements Indexable { 
    private final int value; 

    public IndexableInteger(int value) { 
     this.value = value; 
    } 

    public int getIndex() { 
     return value % 10; 
    } 

    public String toString(){ 
     return Integer.toString(value); 
    } 
}

那么这样的：

public static void main(String[] args) { 
    ArrayList<IndexableInteger> ints = new ArrayList<IndexableInteger>(); 
    int[] values = { 45, 71, 16, 31, 0, 25, 6, 51, 40, 81 }; 
    for (int v : values) 
     ints.add(new IndexableInteger(v)); 

    LinkedList<IndexableInteger> sorted = BucketSort(ints); 
    System.out.println(sorted); 
}

输出这个（该数字在最后一个数字的顺序，但如果它们具有相同的最后一个数字，然后他们在相同的顺序输入）：

[0, 40, 71, 31, 51, 81, 45, 25, 16, 6]

注意：您可能不想使用LinkedList，因为它的addAll()方法以线性时间而非恒定时间运行，但它很容易用于演示，这就是为什么我在这里使用它。

来源

2014-02-15 22:08:00 MT0

使用链接列表的桶排序

回答

相关问题