基数排序算法– C/C++实现的基础
基数排序算法是一种独特的排序算法，它根据数字是一组数字的基本原理进行工作。
"基数排序"仅适用于整数值，因为整数只有一个数学成分，即数字。
在这种排序算法中，数字最初是根据其最低有效位排列的，然后移至其最高有效位，同时保持先前的顺序。
基数排序算法如何工作？
让我们通过并排运行的示例快速跳转到算法的细节。
步骤1：找出最大元素
如前所述，该算法使用最低有效位到最高有效位来排列数字，因此我们需要知道这些迭代的范围。
为此，我们需要找到最大元素。
找到最大数量后，我们需要计算其位数。
步骤2：计算最大位数的位数
我们需要知道必须安排数组的次数，因此有必要计算数字的位数。
如我们所见，最大元素具有三位数，因此该排列将进行三次。
步骤3：根据最低有效数字排列数字
排序的初始安排要求我们根据元素的最低有效位数对其进行排序。
使用单位放置数字排列数字
这里要注意的关键点是，具有不同单位的数字放置在其他位置，但是相同数字在其他位置以正确的方式相互排列。
例如，索引3处的数字36和索引7处的数字32在单位位置具有不同的数字，但其他数字相同。
最初，32在数组中的36之后，但是根据单位位置排列数字之后，32在36之前。
步骤4：根据下一个有效数字排列数字
在保持当前排列不变的情况下，我们将尝试在十位的基础上排列数字。
为此，我们将需要在执行过程中进行稳定的排序。
稳定的排序算法是这样的算法，可以保留相等数量的初始排列。
使用十位数字排列数字
在完成基于十位数字的排序后，我们可以注意到所有低于100的数字在它们之间都是正确排列的。
基本上，如果一个数组包含的数字小于100，则仅两次迭代即可对整个数组进行排序。
注：10以下的数字（没有十位数字）视为十位数字为0。这是有意义的，因为它们被放在数字之前，十位数字是1。
步骤5：继续执行该过程，直到最高位
在此示例中，最高有效位是百位数字。
因此，这是基数排序算法的最后一步。
使用数百位数字排列数字
如我们所见，该数组现在已完全排序。
只要按照最高有效位排列数组，就会发生这种情况。
在继续介绍Radix Sort的实现之前，我们建议您研究Counting Sort Algorithm的概念，该算法用作基于单个数字对数字进行排序的子例程。
基数排序算法在C++中的实现
#include<bits/stdc++.h>
using namespace std;
//Function that performs Radix Sort
void radix_sort(int arr[], int n){
//Step 1: Find the maxumum element
int maximum = arr[0];
for(int i=1;i<n;i++){
maximum = max(maximum, arr[i]);
}
//Step 2: Count the number of digits of the maximum number
int digits = 0;
while(maximum > 0){
digits++;
maximum /= 10;
}
//Step 3, 4, 5: Arrange the numbers on the basis of digits
for(int i=0;i<digits;i++){
//Units/Tens/Hundreds - used to determine which digit
int power = pow(10, i);
//Holds the updated array
int new_array[n];
//Counting Sort Array - required for arranging digits [0-9]
int count[10];
//Initializing Count Array
memset(count, 0, sizeof(count));
//Calculating frequency of digits
for(int j=0;j<n;j++){
//The digit under consideration in this iteration
int num = (arr[j]/power) % 10;
count[num]++;
}
//Cumulative frequency of count array
for(int j=1;j<10;j++){
count[j] += count[j-1];
}
//Designating new positions in the updated array
for(int j=n-1;j>=0;j--){
//The digit under consideration in this iteration
int num = (arr[j]/power) % 10;
new_array[count[num]-1] = arr[j];
count[num]--;
}
//Updating the original array using New Array
for(int j=0;j<n;j++)
arr[j] = new_array[j];
}
//Printing the sorted array
for(int j=0;j<n;j++)
cout<<arr[j]<<" ";
cout<<endl;
}
//The main function
int main(){
//The array containing values to be sorted
int arr[] = {15, 120, 53, 36, 167, 81, 75, 32, 9, 60};
//Size of the array
int n = sizeof(arr)/sizeof(n);
//Function call for the Radix Sort Algorithm
radix_sort(arr, n);
return 1;
}
输出：
9 15 32 36 53 60 75 81 120 167
C语言基数排序算法的实现
#include<stdio.h>
//Function that performs Radix Sort
void radix_sort(int arr[], int n){
//Step 1: Find the maxumum element
int maximum = arr[0];
for(int i=1;i<n;i++){
if(maximum < arr[i])
maximum = arr[i];
}
//Step 2: Count the number of digits of the maximum number
int digits = 0;
while(maximum > 0){
digits++;
maximum /= 10;
}
//Units/Tens/Hundreds - used to determine which digit
int power = 1;
//Step 3, 4, 5: Arrange the numbers on the basis of digits
for(int i=0;i<digits;i++){
//Holds the updated array
int new_array[n];
//Counting Sort Array - required for arranging digits [0-9]
int count[10];
//Initializing Count Array
for(int j=0;j<10;j++)
count[j] = 0;
//Calculating frequency of digits
for(int j=0;j<n;j++){
//The digit under consideration in this iteration
int num = (arr[j]/power) % 10;
count[num]++;
}
//Cumulative frequency of count array
for(int j=1;j<10;j++){
count[j] += count[j-1];
}
//Designating new positions in the updated array
for(int j=n-1;j>=0;j--){
//The digit under consideration in this iteration
int num = (arr[j]/power) % 10;
new_array[count[num]-1] = arr[j];
count[num]--;
}
//Updating the original array using New Array
for(int j=0;j<n;j++)
arr[j] = new_array[j];
//Updating the digit to be considered next iteration
power *= 10;
}
//Printing the sorted array
for(int j=0;j<n;j++)
printf("%d ", arr[j]);
printf("\n");
}
//The main function
int main(){
//The array containing values to be sorted
int arr[] = {15, 120, 53, 36, 167, 81, 75, 32, 9, 60};
//Size of the array
int n = sizeof(arr)/sizeof(n);
//Function call for the Radix Sort Algorithm
radix_sort(arr, n);
return 1;
}
输出：
9 15 32 36 53 60 75 81 120 167
基数排序算法涉及的复杂性
时间复杂度
让我们研究算法中每个步骤的时间复杂度：
- 第1步：要找到最大元素，我们线性遍历整个数组-O(n)
- 第2步：如果我们将'd'作为最大元素中的位数，则用于计算位数的循环将运行'd'次-O(d)
- 步骤3、4、5：这些步骤的工作原理与以数字为基础的数字相同。
这些步骤运行'd'次，每次执行"计数排序"子例程-O(d * n)时。
总时间复杂度：O(d * n)
注意：运行Count数组的循环并不具有显著的时间复杂度，因为运行所述10次的循环被视为恒定时间使用。
空间复杂度
- 步骤1：我们需要一个变量来存储最大元素-O(1)
- 步骤2：一个变量存储位数-O(1)
- 步骤3、4、5："计数排序"的每次迭代都要求我们创建一个数组来存储新排列的值-O(n)。
总空间复杂度：O(n)
