简介
在本实验中,我们将使用 C++ 实现基数排序算法,通过动态数组对数组进行排序。基数排序(Radix Sort)是一种通过处理不同位置上的单个数字来进行排序的算法。
在本实验中,我们将使用 C++ 实现基数排序算法,通过动态数组对数组进行排序。基数排序(Radix Sort)是一种通过处理不同位置上的单个数字来进行排序的算法。
首先在 ~/project
目录下创建一个名为 main.cpp
的 C++ 文件。包含 iostream
和 vector
库,并设置一个 radix_sort
函数,该函数接收一个整数类型的 std::vector
。
#include <iostream>
#include <vector>
using namespace std;
void radix_sort(vector<int>& nums) {
}
定义一个 get_max
函数,该函数接收一个整数向量作为输入并返回最大值。
int get_max(vector<int>& nums) {
int max = nums[0];
for(int i = 1; i < nums.size(); i++) {
if(nums[i] > max)
max = nums[i];
}
return max;
}
定义一个 counting_sort
函数,该函数接收一个整数向量、一个表示当前位值的整数值以及一个用于输出的整数向量。该函数将使用计数排序算法根据当前位值对向量进行排序。
void counting_sort(vector<int>& nums, int place, vector<int>& output) {
const int max = 10;
int count[max];
for(int i = 0; i < max; i++)
count[i] = 0;
for(int i = 0; i < nums.size(); i++)
count[(nums[i] / place) % 10]++;
for(int i = 1; i < max; i++)
count[i] += count[i - 1];
for(int i = nums.size() - 1; i >= 0; i--) {
output[count[(nums[i] / place) % 10] - 1] = nums[i];
count[(nums[i] / place) % 10]--;
}
for(int i = 0; i < nums.size(); i++)
nums[i] = output[i];
}
定义一个 radix_sort
函数,该函数接收一个整数向量作为输入。此函数将从输入向量中获取最大值,并使用 counting_sort
函数根据每个位值对向量进行排序。
void radix_sort(vector<int>& nums) {
int max = get_max(nums);
for(int place = 1; max / place > 0; place *= 10) {
vector<int> output(nums.size());
counting_sort(nums, place, output);
}
}
通过创建一个 main
函数来测试 radix_sort
函数,该函数会生成并打印一个测试向量。
int main() {
vector<int> test = {121, 432, 564, 23, 1, 45, 788};
radix_sort(test);
for(int num : test)
cout << num << " ";
cout << endl;
return 0;
}
在终端中使用以下命令编译并运行程序:
g++ main.cpp -o main && ./main
你应该会看到以下输出:
1 23 45 121 432 564 788
在本实验中,我们学习了如何使用动态数组在 C++ 中实现基数排序算法。基数排序算法通过处理不同位置上的单个数字来工作,是一种常用于整数和字符串的排序算法。