Java To realize the cardinal sort based on the idea of bucket sort and count sort

Count sorting

Premise ： All the keywords in the to sort table must be different from each other ;

thought ： The count sort algorithm is for each record in the table , Scan the table to be sorted once , How many records in the statistical table have a smaller key than the key of the record , Suppose for a record , The count is calculated as c, Then the storage location of the record in the new ordered table is c.

performance ： Spatial complexity ：o(n); Time complexity :o(n^2);

public int[] countSort(int[] array){
int[] tempArray = new int[array.length]; // Introduce auxiliary array
for(int i=0;i<array.length;i++){
int count = 0;
for(int j=0;j<array.length;j++){
if(array[i]>array[j]){
count++;
}
}
tempArray[count] = array[i];
}
return tempArray;
}

Bucket sort

Bucket sorting requires that the sequence to be sorted satisfies the following two characteristics ：

All the values of a sequence can be in the range of ;

The enumerable range of the sequence to be sorted should not be too large , Otherwise, the sorting overhead is too high .

The specific steps of sorting are as follows ：

（1） For this enumerable range, build a buckets Array , Used to record “ fall into ” The number of elements in each bucket ;

（2） take （1） Obtained in buckets The array is recalculated , Recalculate as follows ：

buckets[i] = buckets[i] +buckets[i-1] ( among 1<=i<buckets.length);

public static void bucketSort(int[] data) {
// Get the maximum and minimum values of the elements to be sorted
int max=data[0],min=data[0];
for(int i=1;i<data.length;i++){
if(data[i]>max){
max = data[i];
}
if(data[i] < min){
min = data[i];
}
}
// Cache array
int[] tmp = new int[data.length];
// buckets Used to record information about elements to be sorted
// buckets Array defines max-min+1 A barrel
int[] buckets = new int[max-min+1];
// Count the number of times each element appears in the sequence
for (int i = 0; i < data.length; i++) {
buckets[data[i] - min]++;
}
// Calculation “ fall into ” The position of the elements in each bucket in an ordered sequence
for (int i = 1; i < max - min; i++) {
buckets[i] = buckets[i] + buckets[i - 1];
}
// take data The elements in are completely copied to tmp Array
System.arraycopy(data, 0, tmp, 0, data.length);
// according to buckets The information in the array puts the elements of the sequence to be sorted in the corresponding position
for (int k = data.length - 1; k >= 0; k--) {
data[--buckets[tmp[k] - min]] = tmp[k];
}
}

Based on the idea of bucket sort and count sort, the cardinality sort is realized ：

Each group of keywords in the elements to be sorted is bucket allocated in turn .

public int[] radixSortBuckets(int[] array, int radix) {
// Find the largest element in the sequence to be sorted
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
// Determine the number of digits of the largest element maxBits
int maxBits = 0;
while (max > 0) {
max = max/10;
maxBits++;
}
int[] tempArray = new int[array.length]; // For temporary elements
int[] buckets = new int[radix]; // For bucket sort
int rate = 1;
// Conduct maxBits Sub distribution and collection
for(int i=0; i< maxBits;i++){
// take array The elements in are completely copied to arrayTemp Array
System.arraycopy(array, 0, tempArray, 0, array.length);
Arrays.fill(buckets, 0); // Reset buckets Array
// Distribute ： Calculate the subkey of each element to be sorted , And add the number of times to the corresponding bucket
for(int j=0;j<tempArray.length;j++){
buckets[(tempArray[j]/rate)%radix] ++;
}
// Calculation “ fall into ” The position of the elements in each bucket in an ordered sequence
for(int k=1;k<buckets.length;k++){
buckets[k] = buckets[k]+buckets[k-1];
}
// collect ： Sort the specified data by subkey
for(int m=tempArray.length-1;m>=0;m--){
int subKey = (tempArray[m]/rate)%radix;
array[--buckets[subKey]] = tempArray[m];
}
rate *= radix;
}
return array;
}