List of articles

• Assign sort —— Radix sorting
• • C++
  • python

Assign sort —— Radix sorting

C++

#include <iostream>
#define N 10
using namespace std;
// Find the maximum number of elements in the sequence to be sorted , for example 124 The maximum number of elements is 3
int MaxBit(int A[], int n)
{

// The maximum initialization element is A[0], The maximum number of digits is 0
int maxValue = A[0], digits = 0;
// For maximum 
for (int i = 1; i < n; i++)
{

if (A[i] > maxValue) maxValue = A[i];
}
// Decompose to get the number of bits of the largest element 
while (maxValue!=0)
{

digits++;
maxValue /= 10;
}
return digits;
}
// seek x The first bit A number in bits , Such as 238 The first 2 The number on the bit is 3
int BitNumber(int x, int bit)
{

int temp = 1;
for (int i = 1; i < bit; i++)temp *= 10;
return (x / temp) % 10;
}
void RadixSort(int A[], int n)
{

int i, j, k, b, bMax;
bMax = MaxBit(A, n); // Find the maximum number of elements 
// Allocate space 
int** B = new int* [10]; // Ten barrels 0,1...9
// Allocate space for each bucket ,B[i][0] Statistics No i Number of elements in a bucket 
for (i = 0; i < 10; i++) B[i] = new int[n + 1];
for (i = 0; i < 10; i++)B[i][0] = 0;
// From individual to high , Bucket sorting for different bits 
for (b = 1; b <= bMax; b++)
{

for (j = 0; j < n; j++) // Distribute 
{

int num = BitNumber(A[j],b);// take A[j] The first b A number in bits 
int index = ++B[num][0]; // In barrel numerical index 
B[num][index] = A[j];
}
for (i = 0,j = 0; i < 10; i++) // collect : First in, first out 
{

for (k = 1; k <= B[i][0]; k++)
A[j++] = B[i][k];
B[i][0] = 0; // Set the number of elements to zero after collection 
}
}
// Release space 
for (int i = 0; i < 10; i++) delete[]B[i];
delete []B;
}
int main()
{

int numbers[N] = {
 23,12,41,55,56,62,98,96,79,87 };
RadixSort(numbers, N);
for (int i = 0; i < N; i++)
cout << numbers[i] << " ";
cout << "\n";
return 0;
}

python

def maxBit(A):
digits = 0
maxValue = max(A)
while maxValue != 0:
digits += 1
maxValue //= 10
return digits
def bitNumber(x, bit):
temp = 1
for i in range(1, bit):
temp *= 10
return int((x / temp) % 10)
def radixSort(A, n):
bit_max = maxBit(A)
for b in range(1, bit_max + 1):
buckets = [[] for _ in range(10)] # 10 A barrel 
for j in range(n): # collect 
num = bitNumber(A[j], b) # take A[j] The first b A number in bits 
buckets[num].append(A[j])
j = 0
for i in range(10): # Distribute 
length = len(buckets[i])
A[j:j + length] = buckets[i]
j += length
if __name__ == '__main__':
r = [4, 23, 12, 41, 55, 56, 62, 98, 96, 79, 87]
radixSort(r, len(r))
print(r)