基数排序(Radix Sort) 算法的基本思想是，在待排序列里，分别从低位到高位依次排序，这样最后整个序列就有序了。例如，序列329,57,657,839,436 排序过程是这样的：
3 2 9 0 5 7 6 5 7 8 3 9 4 3 6 ^ | => | 4 3 6 0 5 7 6 5 7 3 2 9 8 3 9 ^ | => | 3 2 9 4 3 6 8 3 9 0 5 7 6 5 7 ^ | => | 0 5 7 3 2 9 4 3 6 6 5 7 8 3 9 |
这样看似更麻烦了，本来只需要排一次的东西现在要排好几次了，其实，这个主要是为了减轻上面1所讲的技术排序的限制，例如，如果一个序列里的数的范围很大，是2^32或者2^64，那么这个序列就无法用计数排序(Counting Sort)了，但是，如果用基数排序，每一轮用一次计数排序，总得时间复杂度是m*O(n)=O(n)。我们还可以根据内存等条件的具体情况，可以每2位或者3位作为一个单位进行排序。
这个算法要注意的一点是：排序时必须从后往前排，并且各个数字必须对齐。
没有评论:
发表评论