复习数据结构：排序算法（八）——基排序

￡神魔★判官ぃ 2022-08-07 01:57 240阅读 0赞

基排序是外排序，稳定的排序算法。

它的时间复杂度：O(d(r+n))，d为每个数的长度，r表示基数，n表示数组中元素的个数。

基数排序是另外一种比较有特色的排序方式，它是怎么排序的呢？我们可以按照下面的一组数字做出说明：12、 104、 13、 7、 9
（1）按个位数排序是12、13、104、7、9
（2）再根据十位排序104、7、9、12、13
（3）再根据百位排序7、9、12、13、104
这里注意，如果在某一位的数字相同，那么排序结果要根据上一轮的数组确定，举个例子来说：07和09在十分位都是0，但是上一轮排序的时候09是排在07后面的；同样举一个例子，12和13在十分位都是1，但是由于上一轮12是排在13前面，所以在十分位排序的时候，12也要排在13前面。
所以，一般来说，10基数排序的算法应该是这样的？
（1）判断数据在各位的大小，排列数据；
（2）根据1的结果，判断数据在十分位的大小，排列数据。如果数据在这个位置的余数相同，那么数据之间的顺序根据上一轮的排列顺序确定；
（3）依次类推，继续判断数据在百分位、千分位……上面的数据重新排序，直到所有的数据在某一分位上数据都为0。
说了这么多，写上我们的代码。也希望大家自己可以试一试

参考链接：

http://blog.csdn.net/feixiaoxing/article/details/6876831

http://blog.csdn.net/hguisu/article/details/7776068

http://blog.csdn.net/xiazdong/article/details/8462393

发表评论

表情：
评论列表 （有 0 条评论，240人围观）

还没有评论，来说两句吧...

相关阅读

    相关 复习八大排序

    这篇文章用来复习一下数据结构中常提到的八大排序和三大查找算法 八大排序 八大排序都有哪些？ 八大排序按照种类可以分为以下几种： 1. 交换排序：冒泡，快排 2.

    左手的ㄟ右手左手的ㄟ右手/ 0 赞/ 45 阅读