使用鏈接列表的桶排序

我想在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

使用鏈接列表的桶排序

回答

相關問題