The core idea of non comparison based sorting is bucket sorting. The time complexity is O(N). Common non comparison based sorting include count sorting and cardinality sorting.
1, Count sort
The range of values applicable to sorting elements is relatively small and is an integer. (e.g. age)
1. Core idea:
(1) First, prepare a finite number (such as 200) of integer auxiliary arrays, traverse the original array one by one, and the value obtained is i, then add one to the value at position i of the auxiliary array
(2) Traverse the auxiliary array. If the value at the array position i is k, K i are output, and the ordered array is obtained
2. Detailed reference code:
/**
* @author Java And algorithm learning: Monday
*/
public static void countSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// Statistics
int max = Integer.MIN_VALUE;
for (int v : arr) {
max = Math.max(max, v);
}
int[] bucket = new int[max + 1];
for (int v : arr) {
bucket[v]++;
}
// sort
int i = 0;
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[i++] = j;
}
}
}
From the first step, we can see that if the sorting value span is relatively large, we have to prepare a large auxiliary array, but most of the arrays are empty, so it is a great waste of space. Therefore, we can also see the limitations of counting sorting.
2, Cardinality sort
Applies to decimal positive integers.
1. Core idea:
(1) Traverse the entire array to get the decimal digits of the maximum value, and supplement the high bits that do not meet the maximum digits with 0
(2) Prepare ten buckets, numbered from 0 to 9, and the size of each bucket is the size of the original array
(3) Traverse the array, taking the single digit as the standard. If the value of the single digit is i, put it into bucket i; After traversal, start from bucket 0 and pour out the numbers one by one (first in, first out). At this time, the numbers are sorted by single digits
(4) Traverse the array, taking the ten digits as the standard. If the value of the ten digits is i, put it into bucket i; After traversal, start from bucket 0 and pour out the numbers one by one (first in, first out). At this time, the numbers are sorted by ten digits
... until it reaches the highest level, the last inverted number is in order.
When the actual code is written, ten buckets are not prepared, but an array with a length of 10 is prepared, which can greatly save space.
2. Detailed reference code:
/**
* @author Java And algorithm learning: Monday
*/
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
sort(arr, 0, arr.length - 1, maxBit(arr));
}
/**
* Find the maximum decimal digits of the array
*/
public static int maxBit(int[] arr) {
int max = Integer.MIN_VALUE;
for (int value : arr) {
max = Math.max(max, value);
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
private static void sort(int[] arr, int l, int r, int digit) {
int radix = 10;
// Auxiliary array
int[] help = new int[r - l + 1];
// How many people can enter the barrel and exit the barrel several times
for (int d = 1; d <= digit; d++) {
// Prefix and array: count[i] how many current bits (d bits) are [0-i]
int[] count = new int[radix];
// Count how many times the number on the d-bit of the array appears at this time,
for (int i = l; i <= r; i++) {
// Get the value on bit d, range [0,9]
int v = getDigit(arr[i], d);
count[v]++;
}
// At this time, count[i] indicates how many current bits (d bits) are [0-i]
for (int i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
// Discharge the bucket from right to left
for (int i = r; i >= l; i--) {
// Get the value in bit d
int v = getDigit(arr[i], d);
help[--count[v]] = arr[i];
}
// Copy back to the original array
for (int i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
}
}
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
3, Comparison based sorting and non comparison based sorting
Comparison based sorting can be applied to a wider range (in any case), but the time complexity limit is O(N*logN)
Non comparison based sorting has narrow application scope, but better time complexity O(N)