vlambda博客
学习文章列表

    前面学习了计数排序，可以实现O(n+k)的时间复杂度，但是他有很大的局限性，最大的问题就是如果最大值和最小值之间相差太大的话，那么会浪费掉很大的空间，比如要排序{1,10000,99,64,120}我们可以根据之前的计算公式最大值减去最小值加一得到计数数组的长度，那么计数数组长度就应该是10000，但是实际上我们只存放了5个数据，中间浪费了极大的空间，所以在使用计数排序时，应该根据自己的实际情况来决定。

    什么是基数排序呢？基数排序和计数排序都是桶排序的一种思想，基数是一种关键字排序，例如我们有这样的一组数据{421,326,266,157,222,414}我们首先拿到每一个数的最后一位，也就是个位，然后进行排序，排序好后再取出十位进行排序，最后拿出百位来进行排序即可，而其中我们每次取的位就是对关键字的操作。

    ps:需要注意的是我们第一次根据个位排序时操作的是原数组，而根据十位排序的时候是在之前个位排好的基础上进行排序，同理百位则是对十位排好后的进行排序。

java代码实现如下

    实际上我们这个代码已经实现了自动加0的功能，我们用Math.pow（10，i）来产生10的i平方，然后拿到原数组中的值除以得到的平方数再求余10，如果是1除以1000是0，再用0取余10所以还是0，所以会自动补0。

    我们来看看时间复杂度和空间复杂度，实际上找出最大数的位数为多少位，这一步应该是在外面计算好了传递进来的，他并不属于基数排序里面的。

    最外层一共循环了d次，其中d就是我们最大数的位数，而循环体内我们对原数组遍历了2次，所以是2n，而计数数组执行了一次就是k，也就是O(d*(2n+k))，然后我们去掉一个常数阶，可以得到时间复杂度为O(d*(n+k)),那空间复杂度又是多少呢？根据我们写的代码，我们一共定义了一个计数数组和一个结果数组所以是O(n+10),然后去掉一个常数阶可以得到空间复杂度为O(n)。且基数排序是一个稳定的排序算法。

    如何用基数排序实现对字符串排序呢？我们还是使用同样的方式例如字符串数{"abc","def","sxf","sss","cbh"}，我们拿到最后一位放入对应的位置，比如abc，当我们拿到c时这个时候由于是字符串你是根本不知道放那个位置的，所以我们可以将他变成char的字符，由于c字符对应的ASCll是99，所以我们存放在99的位置就行，当然如果字符串位数不一致，同理我们可以在前面补一个比A的ASCll还小的值即可。字符串排序重点就是要借助ASCll来实现。