define

Bucket sort, or box sort, is a sorting algorithm that works by sorting an array into a finite number of buckets. Each bucket is sorted individually (it is possible to use a different sort algorithm or continue to use bucket sort recursively; this article uses insert sort). Bucket sort is a kind of induction result of pigeon nest sort. Bucket sorting uses linear time O(n) when the values in the array to be sorted are evenly distributed.

Sorting instance

  • When creating buckets, the distance between buckets does not have to be 1, but can be any value, depending on the situation. For example, if you know that the number to be sorted is between 0 and 100, you can define 10 buckets, and the distance between buckets is 10.
  • Bucket sort is applicable when the range of values to be sorted is known. If the range is not known, it is best not to apply this algorithm.
  • Bucket sorting is a typical space – time sorting algorithm
  • In the use of bucket sort, there is a small skills, such as capacity of 10 define each drum, the first of each barrel data is defined as the number of the ladle has been deposited in the data, also is the actual capacity of 9 each drum, the advantage is can directly know the barrel of the middle and lower one will be stored in the location of the data

Code implementation

namespace SuanFa.Sequence { class BucketSort { static void Main() { //create an object BucketSort bs = new BucketSort();  bs.bucketSort(); } public void bucketSort() {//define ordered sequence int[] array = {21, 8, 6, 11, 36, 50, 27,42,30,12}; // the size of the bucket is ten int[,] bucket = new int[10,10]; //initialize buckets for(int i=0; i<bucket.GetLength(0); i++) { for(int j=0; j<bucket.GetLength(1); j++) { bucket[i, j] = 0; } } //sort for(int i=0; i<array.Length; i++) { int index = getIndex(array[i]); insertSort(bucket,array[i],index); } //put the ordered sequence to array int t = 0; for (int i = 0; i < bucket.GetLength(0); i++) { for (int j = 0; j < bucket.GetLength(1); j++) { if(bucket[i,j]! =0&&j! =0) { array[t] = bucket[i,j]; t++; } } } //print ordered array print(array); } //insert sort public void insertSort(int[,] array,int k,int index) { //the position of the new element int i = array[index,0] + 1; while (i>0&&k<array[index,i]) { //move the bigger element back array[index,i + 1] = array[index,i]; i--; } //save new element array[index,i + 1] = k; array[index, 0]++; } //the index of the bucket public int getIndex(int i) { return i / 10 % 10; } /// <summary> /// print /// </summary> /// <param name="nums">the array which will printed</param> public void print(int[] nums) { for (int i = 0; i < nums.Length; i++) { Console.WriteLine("i=" + nums[i] + " "); } Console.WriteLine(); }}}Copy the code

Time complexity

Bucket sorting is fast, but it takes up a lot of memory. The time complexity of this algorithm is O(n).

The stability of

When the sorting algorithm is implemented in this paper, bucket sorting + direct insertion sorting algorithm is used, so the stability is high.

The resources

  • Zh.wikipedia.org/wiki/ bucket sort
  • www.cnblogs.com/skywang1234…