算法与数据结构基数排序

一、基数排序算法示意图

下方的基数排序算法的实现是利用“桶”来实现的，首先我们创建10个桶，然后按照基数入桶，基数的取值是从数字的低位到高位以此取值。我们还是以[62, 88, 58, 47, 62, 35, 73, 51, 99, 37, 93]这个序列为例，使用基数排序的方式对该序列进行升序排列。

下方截图就是上述序列基数排序的具体过程，在排序之前我们先得创建10个空桶，并进行0-9的编号。这10个空桶会在基数排序的过程中存储我们要排序的数值。下方就是对基数排序步骤的详细介绍：

二、基数排序算法的代码实现

看完基数排序的原理后，接下来我们就要给出相应的代码实现了。当然本篇博客我们依然使用Swift面向对象语言来给出相应的代码实现。下方代码的实现主要是按照上述示意图的步骤，接下来我们就来循序渐进的来看一下代码的具体实现。

1.创建10个空桶

首先我们需要创建10个空桶，在此我们用一个数组中存放10个数组，这10个数组就是我们相应的桶。而这10个数组所对应的下标就是桶的编号。下方这个createBucket()方法就负责创建10个空桶，并返回。返回结果的类型是Array，是一个二维数组。外层数组中存放的就是10个桶，下标是桶的编号。内层数组就是一个桶，负责存放与该桶编号相等的基数对应的数值。具体代码如下所示。

2.计算无序序列中最大的数值

接着我们要实现一个函数用来计算无序序列中最大的数值，取基数入桶出桶的次数以此最大数值的位数为准。比如最大数值为5位，那么我们取基数就从第一位取到第5位，每取一位基数就要按照该基数进行入桶和出桶操作。下方代码就是计算无序数列中最大的那个值，代码还是比较简单的，如下所示：

3、获取数字的长度

上面计算完元素后，我们需要计算该最大值的长度。因为长度的值，就是取基数的次数。下面就是获取数值的长度的函数，其实就是将数字转换成字符串，字符串再转换成字符数组，然后返回字符数组的个数。具体代码如下所示：

4、获取数值中特定位数的值

下方的函数就是获取某数字特定位数的值，你可以通过取余以及求模的方式来获取，以239为例，我想获取十位数值3，那么我们需要将239执行Int((239%100)/10), 通过该操作，我们就可以获取十位上的数值。但是在下方函数中并未采用此方法，而是采用将数字转换成字符串，然后将字符串转换成字符数组，这样我们就可以轻松的取出数字中的任何一位。下方就是具体代码的实现：

5、基数排序的具体代码实现

万事俱备只欠东风，上述做的都是基数排序的准备工作，接下来我们就开始调用上述的方法来实现我们的基数排序的具体代码了。下方就是基数排序的具体代码，如果上述的几个函数搞明白了，那么下方代码并不难理解。先创建桶，获取无序数列中最大的值，然后获取这个最大值的长度。然后就是通过for循环不断的去基数进行入桶和出桶的操作了，如下所示：

三、测试用例

用我RadixSort类遵循了SortType方法，我们依然可以使用之前的测试用例。下方就是我们的测试用例，与之前使用的一直，只不过需要将RadixSort这个类的对象传给我们的测试函数即可，如下所示：

上述测试用例的输出结果如下所示：