第二十章 基数排序法
::: hljs-center
目录
第二十章 基数排序法
●前言
●认识排序
●一、基数排序法是什么？
1.简要介绍
2.图形理解
3.算法分析
●二、案例实现
1.案例一
●总结
:::
前言
排序算法是我们在程序设计中经常见到和使用的一种算法，它主要是将一堆不规则的数据按照递增或递减的方式重新进行排序。在如今的互联网信息时代，随着大数据和人工智能的发展，大型企业的数据库中有亿级的用户数据量。因此对其进行处理，排序算法也就成为了其中必不可缺的步骤之一。
认识排序
排序功能对计算机领域而言，是一项非常重要而且普遍的工作。排序中数据的移动方式可分为直接移动和逻辑移动两种方式，直接移动是直接交换存储数据的位置，而逻辑移动并不会移动数据存储的位置，仅改变指向这些数据辅助指针的值。排序通常按照数据量的多少和所使用的内存，可分为内部排序和外部排序，数据量小可以全部加载到内存来进行排序的，就称为内部排序，大部分排序属于此类。数据量大而无法一次性加载到内存中，必须借助磁带，磁盘等辅助存储器进行排序的，则称为外部排序。随着数据结构科学的进步，如今，陆续被提出的冒泡排序法，选择排序法，插入排序法，合并排序法，快速排序法，堆积排序法，希尔排序法，基数排序法，直接合并排序法等等，它们各有其特色和其应用场合。并且在算法中，我们非常关注算法程序代码的时间复杂度和空间复杂度，因为它会直接体现出我们程序代码的执行效率以及编程人员的逻辑思维等等的综合能力。当数据量相当庞大时，排序算法所花费的时间就显得相当重要，排序算法的时间复杂度可分为最好情况、最坏情况以及平均情况。另外，对于任何的排序算法都会有数据交换的操作，数据互换位置会暂时用到一个额外的空间，这也是排序算法中空间复杂度要考虑到的问题，而在排序算法中所使用的额外空间越小，它的空间复杂度就越好。
一、基数排序法是什么？
1.简要介绍
基数排序法与我们之前学习的排序方法有所不同，它并不需要进行元素之间的比较操作而是一种分配模式排序方式。该排序算法按照比较的方向可以分为最高位优先(MSD)和最低位优先(LSD)两种。最高位优先是从最左边的位数开始比较的，而最低位优先是从最右边的位数开始比较的。
2.图形理解
在下面，我们用最低位优先的方法对下面的数据进行从小到大的排序。具体情况如下图所示：
①把每个整数先按个位数字放到列表中，并且将其合并。具体情况如下图所示：
②把每个整数按十位数字放到列表中，并且将其合并。具体情况如下图所示：
③把每个整数按百位数字放到列表中，并且将其合并完成最后的排序。具体情况如下图所示：
3.算法分析
在基数排序法中将会分析到三个参数：n是原始数据的个数，p是数据字符数，k是原始数据的最大值。就像我们上面的示例中，n为12，p为3，若n很大p固定或很小则其排序的效率将会很高。 ①基数排序法在所有情况下，时间复杂度都为O()。 ②基数排序法是稳定排序法。 ③基数排序法要使用很大的额外空间来存放列表数据，其空间复杂度为O(n*p)。
二、案例实现
1.案例一
①范例情况：用基数排序法对52，718，686，321，658，367，545，117，22，217这十个数据元素进行从小到大的排序，并且输出每次列表下的具体情况。
②代码展示：
#include<iostream>
using namespace std;
#define size 10 //事先声明排序数据的个数
class radix {
public:
int data[size];
void showresult() {
for (int i = 0; i < size; i++)
cout << data[i] << " ";
cout << endl;
}
void radix_start() {
//待排序数据最高是三位数，则需要进行个，十，百位的三次列表，所以n的执行条件为n<=100。要是需要进行4次列表，则n的执行条件为n<=1000
for (int n = 1; n <= 100; n *=10)
{
int temp[10][10] = { 0 }; //暂存数组，具体情况需要根据排序数据的数目和具体情况来定义
for (int i = 0; i < size; i++)
{
int m = (data[i] / n) % 10; //m分别为个，十，百位的值，它是用来当作暂存数组的下标去使用的
temp[m][i] = data[i]; //将data[i]的值按位数的情况，分别暂存在二维数组中不同的的位置，作为下面的使用
}
int num = 0;
for (int j = 0; j < size;j++)
{
for (int k = 0; k < size; k++)
{
if (temp[j][k] != 0)
{
data[num++] = temp[j][k]; //把temp中的值重新放回到数组data中
}
}
}
cout << n << "位数排序：";
showresult();
}
}
};
void text()
{
radix r;
cout << "请输入要排序的" << size << "个数据" << endl;
for (int i = 0; i < size; i++)
cin >> r.data[i];
cout << "排序前：" << endl;
r.showresult();
r.radix_start();
cout << "排序后：" << endl;
r.showresult();
}
int main()
{
text();
}
③结果展示：
总结
以上就是基数排序法的讲解，基数排序法又被称为桶子排序法，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，是一种非常好的算法思维。在某些时候，基数排序法的效率高于其它的稳定性排序法。
<您的三连和关注是我最大的动力> ???? 文章作者：Keanu Zhang 分类专栏：算法之美（C++系列文章）