This is the 10th day of my participation in the August Text Challenge.More challenges in August

Abstract

Bucket sort is similar to radix sort and is equivalent to another logic of radix sort. It treats the value range as the number of buckets created, and the length of the bucket is the size of the sequence. By processing the values of the comparison elements, placing the elements at specific locations in the bucket, and then iterating through the bucket, you get an ordered sequence.

logic

Create a number of buckets (arrays or linked lists). Make rules to distribute the elements of the sequence evenly in different buckets. Then sort within each bucket, and finally merge the non-empty buckets.

process

  1. Create a number of buckets
  2. Elements evenly distributed in the bucket (by rule)
  3. Bucket sort
  4. Merge non-empty buckets

Let’s also use an unordered sequence of integer elements to sort the sequence.

implementation

Get the maximum number of bits in the sequence, and determine how many times the maximum number of bits are in the sequence, so each bit is iterated over the comparison.

    // Get the maximum value
	int max = array[0];
	for (int i = 1; i < array.length; i++) {
		if(max < array[i]) { max = array[i]; }}Copy the code

Bucket sorting implementation method

Each integer has 10 base bits from 0 to 9, so we create 10 buckets for each of these 10 numbers, and the height of each bucket is the length of the sequence.

The next step is to create an array that keeps track of the size of each bucket to hold the number of elements, so that when you pull out elements from the bucket, you can determine the length of the traversal and reduce the amount of space that is useless for traversal. And this is the index position of the element in the bucket.

		
	/ / bucket array
	int[][] buckets = new int[10][array.length];
	// The number of elements in each bucket
	int[] bucketSizes = new int[buckets.length];
Copy the code

Next, elements are processed and sorted by the largest number of carries, bucketSizes records the number of carries and provides buckets’ array index position in the bucket.

For example, if you start with buckets[3] and 43, you should put buckets[3][0] in the bucket. If so, the 23 would be covered by the later 43. We use an array of bucketSizes[3], bucketSizes[3] plus buckets[3] after storing 23, so that 43 is buckets[3][1].

When all the elements are placed, buckets bucket is traversed by buckets, and the elements are taken out one by one. The maximum value of each bucket traversed is bucketSizes, so there is no need to traverse all buckets and reduce the number of traversals.

	for (int divider = 1; divider <= max; divider *= 10) {
		for (int i = 0; i < array.length; i++) {
			int no = array[i] / divider % 10; buckets[no][bucketSizes[no] ++] = array[i]; }}int index = 0;
	for (int i = 0; i < buckets.length; i++) {
		for (int j = 0; j < bucketSizes[i]; j++) {
			array[index ++] = buckets[i][j];
		}
		bucketSizes[i] = 0;
	}

Copy the code

Time and space complexity

  • Time complexity: O(n + n * logn – n * logm)
  • Space complexity: O(n+m)
  • It’s stable sort

M is the number of buckets