使用动态数组实现基数排序

C++C++Beginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

简介

在本实验中,我们将使用 C++ 实现基数排序算法,通过动态数组对数组进行排序。基数排序(Radix Sort)是一种通过处理不同位置上的单个数字来进行排序的算法。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("`C++`")) -.-> cpp/BasicsGroup(["`Basics`"]) cpp(("`C++`")) -.-> cpp/ControlFlowGroup(["`Control Flow`"]) cpp(("`C++`")) -.-> cpp/FunctionsGroup(["`Functions`"]) cpp(("`C++`")) -.-> cpp/IOandFileHandlingGroup(["`I/O and File Handling`"]) cpp(("`C++`")) -.-> cpp/StandardLibraryGroup(["`Standard Library`"]) cpp(("`C++`")) -.-> cpp/SyntaxandStyleGroup(["`Syntax and Style`"]) cpp/BasicsGroup -.-> cpp/arrays("`Arrays`") cpp/BasicsGroup -.-> cpp/strings("`Strings`") cpp/ControlFlowGroup -.-> cpp/conditions("`Conditions`") cpp/ControlFlowGroup -.-> cpp/for_loop("`For Loop`") cpp/FunctionsGroup -.-> cpp/function_parameters("`Function Parameters`") cpp/IOandFileHandlingGroup -.-> cpp/output("`Output`") cpp/StandardLibraryGroup -.-> cpp/standard_containers("`Standard Containers`") cpp/SyntaxandStyleGroup -.-> cpp/code_formatting("`Code Formatting`") subgraph Lab Skills cpp/arrays -.-> lab-96162{{"`使用动态数组实现基数排序`"}} cpp/strings -.-> lab-96162{{"`使用动态数组实现基数排序`"}} cpp/conditions -.-> lab-96162{{"`使用动态数组实现基数排序`"}} cpp/for_loop -.-> lab-96162{{"`使用动态数组实现基数排序`"}} cpp/function_parameters -.-> lab-96162{{"`使用动态数组实现基数排序`"}} cpp/output -.-> lab-96162{{"`使用动态数组实现基数排序`"}} cpp/standard_containers -.-> lab-96162{{"`使用动态数组实现基数排序`"}} cpp/code_formatting -.-> lab-96162{{"`使用动态数组实现基数排序`"}} end

包含库并设置函数

首先在 ~/project 目录下创建一个名为 main.cpp 的 C++ 文件。包含 iostreamvector 库,并设置一个 radix_sort 函数,该函数接收一个整数类型的 std::vector

#include <iostream>
#include <vector>
using namespace std;

void radix_sort(vector<int>& nums) {

}

定义 getMax 函数

定义一个 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;
}

定义 CountingSort 函数

定义一个 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];
}

定义 RadixSort 函数

定义一个 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++ 中实现基数排序算法。基数排序算法通过处理不同位置上的单个数字来工作,是一种常用于整数和字符串的排序算法。

您可能感兴趣的其他 C++ 教程