还剩6页未读,继续阅读
文本内容:
基数排序F此PPT介绍F基数排序,一种高效稳定的排序算法背景介绍历史渊源发展现状F基数排序起源于传统基数排序算法,后由法国由于其优异的表现,在计算机大数据处理、金计算机科学家发展而来融、图像处理等领域都有着广泛的应用算法概述F基数排序是一种稳定的排序算法,它将待排数据按位分割成F个桶,对每个桶排序后再依次合并基本思想模拟流水拼装将数据看做流水线上的流,按照不同位上的数字流对每个桶内的数据进行排序,再将各个桶的结果按进不同的桶里顺序拼接起来步骤设定桶的数量1F按照不同数位上的数字拆分为F个桶对每个桶排序2可以使用其他排序算法比如插入排序对每个桶进行排序合并所有桶3按照顺序将所有桶的结果合并为一个有序的序列示例演示对以下数字进行F基数排序457,327,189,910,726•4•57•910•3•27•726•1•89•457•9•10•327•7•26•189时间复杂度和空间复杂度时间复杂度空间复杂度12F基数排序的时间复杂度为Od*n+F,其中d F基数排序的空间复杂度为On+F,其中n为为数字位数,n为数组长度,F为桶的数量数组长度,F为桶的数量应用场景和优缺点应用场景适用于排序数据的最高位数相对较小的情况,如身份证号、学号等优点稳定、快速、易于实现缺点需要计算桶的数量,空间需求较高;对数据的最高位数有一定限制。