The sort we’ve seen before, selection sort, bubble sort, insertion sort, merge sort, and quicksort are all comparation-based sorts, but bucket sort offers a new idea, which is sort based on the state of the data.

Sort under the idea of bucket sort

  • Count sorting
  • Radix sort

Characteristics of bucket sort

  • All sorts under the bucket sort idea are sort based on no comparison
  • The time complexity is O(N), the extra space load is O(M)
  • The application scope is limited, and the data condition of the sample needs to meet the bucket division

Classical count sort and radix sort to the sample requirements

  • In general, counting sort requires that the samples be integers and the range is narrow
  • In general, radix sorting requires that the samples be positive decimal integers

The idea of bucket sort

  1. Get the range of values for an unordered array

2. Create buckets based on the value range.

3. Go through the array, putting each element into the corresponding “bucket”.

4. Sort the array by iterating over the elements in the bucket and placing them in the array.

A bucket is a container that can be implemented in any number of data structures, including arrays, queues, or stacks.

Count sorting

The illustration

1. Find the maximum number of unordered arrays and create an empty array of the maximum length +1

2. Iterate over the array and count the number of occurrences of each element

3. Iterate over the “buckets”, that is, the array used for counting the number of elements, to get an ordered array

code

public static void countSort(int[] arr){ if (arr == null ||arr.length<2){ return; } // Find the largest number in the array int Max = Integer.min_value; for (int i =0; i<arr.length; i++){ max = Math.max(max,arr[i]); Int [] bucket = new int[Max +1]; For (int I =0; int I =0; i<arr.length; i++){ bucket[arr[i]]++; } // Int I =0; for (int j=0; j<bucket.length; j++){ while (bucket[j]-->0){ arr[i++]=j; }}}Copy the code

Classical cardinality sort

The idea is to cut an integer into bits and compare each bit separately. The invention of radix sort can be traced back to Herman Hollery’s contribution in 1887 with the Tabulation Machine.

Radix sort uses buckets, which, as the name implies, are compared by the bits (ones, tens, hundreds…). , the sorted elements are allocated to 0 to 9 buckets, so as to achieve the sorting effect. In some cases, the efficiency of radix sorting is higher than other comparative sorting methods.

Algorithm steps

  1. Find the largest number in the data and determine the largest number of bits in the sorted array.
  2. All the values to be compared (positive integers) are unified into the same digit length, and the digits with shorter digits are supplemented with zero
  3. The order is sorted from the lowest order
  4. After sorting from the lowest to the highest bits, the sequence becomes an ordered sequence

The demo

The illustration

The following array is an example

 int[] arrays = {6,  4322, 432, 344, 55 };
Copy the code

We now have 10 buckets, each of which can hold arrays. Length of numbers…

int[][] buckets = new int[arrays.length][10];
Copy the code

1. Allocate each [unit digit] of the array to different buckets:

After the allocation, we recycle in order: the result should look like this: {4322,432,344,55,6}

2. Allocate each of the ten digits in the array to a different bucket (for numbers like 6, add 0 to the front) :

After the allocation, we recycle in order: the result should look like this: {6,4322,432,344,55}

3. Assign each hundred to a different bucket (for numbers like 6 and 55, add 0 to the front) :

After the allocation, we recycle in order: the result should look like this: {6,55,4322,344,432}

4. Assign each [thousand digit] in the array to a different bucket (add 0 to the front for numbers like 6 and 55)

After the allocation, we recycle in order: the result should look like this: {6,55,344,432,4322}

code

public static int findMax(int[] arrays) { int max = Integer.MIN_VALUE; for (int i = 0; i < arrays.length; i++) { max = Math.max(max, arrays[i]); } return max; } public static void radixSort(int[] arrays) { int max = findMax(arrays); For (int I = 1; int I = 1; max / i > 0; i = i * 10) { int[][] buckets = new int[arrays.length][10]; // Retrieve each digit (digits, tens, hundreds, thousands... For (int j = 0; j < arrays.length; j++) { int num = (arrays[j] / i) % 10; Buckets [J][num] = arrays[J]; buckets[J]; buckets[J]; } // Reclaim the bucket element int k = 0; For (int j = 0; j < 10; For (int l = 0; int l = 0; l < arrays.length ; If (buckets[l][j]! = 0) { arrays[k++] = buckets[l][j]; } } } } }Copy the code

Upgraded cardinality sort

Classical radix sort requires an extra stack or queue, but the same effect can be achieved by the number of times each digit occurs and the order in which it is traversed.

The illustration

code

public static void radixSortPlus(int[] arr){ if (arr == null ||arr.length<2){ return; } radixSortPlus(arr,0,arr.length-1,maxbits(arr)); } //arr[l..r] sort, Public static void radixSortPlus(int[] arr,int L,int R,int DIGIT){final int radix = 10; int i=0; int j=0; Int [] help = new int[r-l +1]; for (int d=1; d<=digit; D++){// the maximum number of bits, In and out of how many times / / / / count 10 space [0] current (d) is 0 Numbers how many / / count [1] current (d) is the (number of 0 and 1) how many / / count [2] current (d) is the (0, 1 and 2) the number of how many a / / Int [] count = new int[radix]; int[] count = new int[radix]; // count[0..9] for (i=L; i<=R; i++){ j = getDigit(arr[i],d); Count [j]++; } for (I =1; i<radix; i++){ count[i] = count[i]+count[i-1]; } for (I =R; i>=L; i--){ j = getDigit(arr[i],d); help[count[j]-1] =arr[i]; count[j]--; } for (i = L, j = 0; i <= R; i++, j++) { arr[i] = help[j]; }}} public static int getDigit(int x,int d){return ((x/((int) math.pow (10,d-1)) %10); }Copy the code

Ps: Part of the picture source network, intrusion deletion.

Sorting summary

The stability of

Summary of sorting algorithm

  • 1) The ranking is not based on comparison. It has strict requirements on sample data and is not easy to rewrite
  • 2) Based on comparison, as long as the size ratio of two samples is defined, it can be directly reused
  • 3) Comparison-based sorting, the limit of time complexity is O(N*logN)
  • 4) There is no stable comparison-based ordering with time complexity O(N*logN), extra space complexity less than O(N).
  • 5) In order to choose the absolute speed fast row, in order to save space select heap row, in order to stability select merge