可视化基数排序算法

前言

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

概念介绍

概念介绍

  • 基数排序是非比较型整数排序算法

  • 它将整数按位数切割成不同的数字，然后按照每个位数分别比较

原理讲解

我们以[12 8 3 24 21 36 11 15 32 9]这个序列为例说明基数排序算法的实现原理

  1. 当未开始排序时，此时效果如下图

    在这里插入图片描述

  2. 我们建立下标为0-9的十个数组用于存放数据，此时效果如下图

    在这里插入图片描述

  3. 首先我们以未排序序列个位上的数字为基数。开始遍历，将第一个元素12，放到下标为2的数组中。此时效果如下图

    在这里插入图片描述

  4. 继续遍历，将第二个元素8，放到下标为8的数组中。此时效果如下图

    在这里插入图片描述

  5. 继续遍历，将第三个元素3，放到下标为3的数组中。此时效果如下图

    在这里插入图片描述

  6. 继续遍历，将第四个元素24，放到下标为4的数组中。此时效果如下图

    在这里插入图片描述

  7. 继续遍历，将第五个元素21，放到下标为1的数组中。此时效果如下图

    在这里插入图片描述

  8. 继续遍历，将第六个元素36，放到下标为6的数组中。此时效果如下图

    在这里插入图片描述

  9. 继续遍历，将第七个元素11，放到下标为1的数组中。此时效果如下图

    在这里插入图片描述

  10. 继续遍历，将第八个元素15，放到下标为5的数组中。此时效果如下图

    在这里插入图片描述

  11. 继续遍历，将第九个元素32，放到下标为2的数组中。此时效果如下图

    在这里插入图片描述

  12. 继续遍历，将第十个元素9，放到下标为9的数组中。此时效果如下图

    在这里插入图片描述

  13. 至此第一次遍历结束，此时效果如下图

    在这里插入图片描述

  14. 然后我们将0-9下标中数组存的数据进行输出。开始输出下标为0的数组中的元素，此时效果如下图

    在这里插入图片描述

  15. 继续输出下标为1的数组中的元素，此时效果如下图

    在这里插入图片描述

  16. 继续输出下标为2的数组中的元素，此时效果如下图

    在这里插入图片描述

  17. 继续输出下标为3的数组中的元素，此时效果如下图

    在这里插入图片描述

  18. 继续输出下标为4的数组中的元素，此时效果如下图

    在这里插入图片描述

  19. 继续输出下标为5的数组中的元素，此时效果如下图

    在这里插入图片描述

  20. 继续输出下标为6的数组中的元素，此时效果如下图

    在这里插入图片描述

  21. 继续输出下标为7的数组中的元素，此时效果如下图

    在这里插入图片描述

  22. 继续输出下标为8的数组中的元素，此时效果如下图

    在这里插入图片描述

  23. 继续输出下标为9的数组中的元素，此时效果如下图

    在这里插入图片描述

  24. 至此，第一次输出介绍，此时效果如下图

    在这里插入图片描述

到这个位置以个位数数字为基数的遍历完成

  1. 然后我们以未排序序列十位上的数字为基数。开始遍历（中间的过程和以个位上数字为基数时相同）。此时最终效果如下图

    在这里插入图片描述

  2. 遍历结束后，开始按照下标从0-9的顺序输出数组中的数据。开始输出下标为0的数组中的元素，此时效果如下图

    在这里插入图片描述

  3. 继续输出下标为1的数组中的元素，此时效果如下图

    在这里插入图片描述

  4. 输出下标为2的数组中的元素，此时效果如下图

    在这里插入图片描述

  5. 输出下标为3的数组中的元素，此时效果如下图

    在这里插入图片描述

  6. 至此，第二次输出介绍，此时效果如下图

    在这里插入图片描述

到这个位置整个基数排序完成完成

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

时间复杂度

  • 基数排序的最好时间复杂度为O(K*N);其中N为待排序元素个数，K为待排序元素最大值

空间复杂度

  • 基数排序的空间复杂度为O(K+N);其中N为待排序元素个数，K为待排序元素最大值

算法优缺点

  • 优点：稳定；速度快

  • 缺点：数据量大时，需要空间较大

效果展示

在这里插入图片描述

更多算法学习请关注我的公众号

在这里插入图片描述

说明

  • 在公众号中回复“算法源码”即可获取十大经典算法源码

  • 在公众号中回复“算法书籍”即可获取经典入门算法书籍

以上是 可视化基数排序算法 的全部内容， 来源链接： utcz.com/a/26441.html

回到顶部