桶分類 算法

桶分類 (Bucket Sort)

Bucket sort is a sorting technique in which array is partitioned into the buckets. By this, each bucket will be sorted individually, by using some another sorting algorithm such as insertion sort. This sorting technique assumes that the input is drawn from a uniform distribution by which it has an average case of O(n). Bucket sort is a fast technique because bucket sort presumes that the input is generated by a process, which will distribute the element uniformly and independently over the interval.

存儲桶排序是一種將數組劃分為存儲桶的排序技術。 這樣，將使用其他一些排序算法(例如插入排序)分別對每個存儲桶進行排序。 這種排序技術假定輸入是從均勻分布中提取的，該輸入的平均情況為O(n) 。 桶分類是一種快速的技術，因為桶分類假定輸入是由某個進程生成的，該輸入將在間隔內均勻且獨立地分配元素。

桶分類算法 (Algorithm for Bucket Sort)

1. Set up an array of initially empty buckets.

   設置一系列最初為空的存儲桶。

2. Put the element in the corresponding bucket.

   將元素放入相應的存儲桶中。

3. Sort each non-empty bucket.

   對每個非空桶進行排序。

4. Visit the bucket in order and put all the elements into a sequence and print them.

   按順序訪問存儲桶，并將所有元素放入序列中并打印。

桶分類的偽代碼 (Pseudo code for Bucket Sort)

void bucketsort (int a[ ], int n, int max)
{
int i,j=0;
//initialize each bucket 0 and then make bucket empty.
int* buckets = calloc(max+1, size of (int));
for(int i=0; i<n; i++)
buckets[a[i]]++;
//now sort each bucket individually.
//sequentially empty each bucket in some array.
for(i=0; i<max; i++)
while (buckets[i]--)
b[j++]=i;
//display the array b as sorted list of elements.
}

Example:

例：

Let us sort the elements by using bucket sort. Elements which need to be sort are 56, 12, 84, 28, 0,-13, 47, 94, 31, 12.

讓我們使用存儲桶排序對元素進行排序。 需要排序的元素是56，12，84，28，0，-13，47，94，31，12。

Step 1) First set up an array which is given below:

步驟1)首先建立一個數組，如下所示：

Step 2) Now consider the range such that:

步驟2)現在考慮范圍，使得：

-20 to -1, 0 to 10 10 to 20, 20 to 30, 30 to 40, 40 to 50, 50 to 60, 60 to 70, 70 to 80, 80 to 90, 90 to 100.

-20至-1、0至10 10至20、20至30、30至40、40至50、50至60、60至70、70至80、80至90、90至100。

Now we fill up each bucket by given elements,

現在，我們通過給定的元素填充每個存儲桶，

Step 3) Now sort the each bucket and then print the array by visiting each bucket sequentially.

步驟3)現在，對每個存儲桶進行排序，然后依次訪問每個存儲桶以打印陣列。

-13, 0, 12, 12, 28, 31, 47, 56, 84, 94

-13、0、12、12、28、31、47、56、84、94

This is the sorted list.

這是排序的列表。

桶分類的缺點 (Drawbacks of Bucket Sort)

1. For the bucket sort, it’s the necessary part that the maximum value of the element must be known.

   對于存儲桶排序，必須知道元素的最大值是必不可少的部分。

2. In this type of technique, we have to create enough buckets in the memory for every element, to place in the array.

   在這種技術中，我們必須在內存中為每個元素創建足夠的存儲桶，以放置在數組中。

桶排序分析 (Analysis of the bucket Sort)

Average case, best case, and worst case time complexity of this algorithm is O(n).

該算法的平均情況，最佳情況和最壞情況的時間復雜度為O(n) 。

翻譯自: https://www.includehelp.com/algorithms/bucket-sort-algorithm.aspx

桶分類 算法