Article From:https://www.cnblogs.com/ranjiewen/p/9060492.html

For a int array, please write a counting sort algorithm to sort the array elements.

Test sample:
`[1,2,3,5,2,3],6`
`[1,2,2,3,3,5]`
• ### Counting sorting

```class CountingSort {
public:
int* countingSort(int* A, int n) {
// write code here
int min=A[0],max=A[0];
for(int i=1;i<n;i++)
{
if(A[i]<min) min=A[i];
if(A[i]>max) max=A[i];
}
int k=max-min+1;
int* B=new int[k](); //Initialization is 0
for(int i=0;i<n;i++)
B[A[i]-min]++;
int idx=0;
for(int i=min;i<=max;i++)
for(int j=0;j<B[i-min];j++)
A[idx++]=i;
delete []B;
return A;
}
};```

For a int array, please write a cardinality sorting algorithm to sort the array elements.

Given an array of intAAnd the size of an arrayn，Please return to the sorted array. The guarantee element is less than 2000.

Test sample:
`[1,2,3,5,2,3],6`
`[1,2,2,3,3,5]`
• ### Cardinality sorting

```#include <iostream>
using namespace std;
const int MAX = 10;

void print(int *a, int sz) {
for (int i = 0; i < sz; i++)
cout << a[i] << " ";
cout << endl;
}

{
int i, bucket[MAX], maxVal = 0, digitPosition = 1;
for (i = 0; i < arraySize; i++) {
if (a[i] > maxVal) maxVal = a[i];
}

int pass = 1;  // used to show the progress
/* maxVal: this variable decide the while-loop count
if maxVal is 3 digits, then we loop through 3 times */
while (maxVal / digitPosition > 0) {
/* reset counter */
int digitCount[10] = { 0 }; //For each bit: Statistics 0-10 for numbers

/* count pos-th digits (keys) */
for (i = 0; i < arraySize; i++)
digitCount[a[i] / digitPosition % 10]++;

/* accumulated count */
for (i = 1; i < 10; i++)
digitCount[i] += digitCount[i - 1];

/* To keep the order, start from back side */
for (i = arraySize - 1; i >= 0; i--)
{
int temp = a[i] / digitPosition % 10;
bucket[--digitCount[temp]] = a[i];
}

/* rearrange the original array using elements in the bucket */
for (i = 0; i < arraySize; i++)
a[i] = bucket[i];

/* at this point, a array is sorted by digitPosition-th digit */
cout << "pass #" << pass++ << ": ";
print(a, arraySize);

/* move up the digit position */
digitPosition *= 10;
}
}```