基数排序

#基数排序

  • 原理：规定一个0-9的辅助数组，依次对所需排列数字进行个位，十位，百位....的比较，最后得出结果(辅助队列可以灵活变换，不一定非要0-9，这样太狭隘)
  • 流程步骤：
  • 1.将每个元素取个位，挂到辅助数组的指针下，当有个位相同时，将该元素挂到上一个元素的指针下
  • 2.当所有元素均被挂在辅助数组的指针下时，依次从辅助数组指针下取下元素，并按顺序将后续元素连接上
  • 3.当前两个步骤完成后，所得到的数组链必然是按个位大小顺序排列的
  • 4.此时按每个元素的百位，再进行1,2的类似操作
  • 5.直到某次循环所有元素都被挂到辅助数组的0位指针下，此时排列完毕，顺序必然有序。PS：这是我自己理解说的，不代表真的这样实现，最好看看代码TAT

    • 空口说的头头是道，也不知道后面的我看了会怎么想，先说好，别骂我

    #基数排序算法

  • 哦，孩子，你一定想看代码是什么对吧，哦，不，据说不怎么考代码，那我谢毛线
  • 基数排序擅长解决的问题：
  • 1.数据元素的关键字可以方便的拆分成为d组
  • 2.每组关键字的取值范围不大，即r较小（r就是关键字的位数，个位十位百位...）
  • 3.数据元素个数n较大
  • 时间复杂度：O(d*(n+r))
  • 免得你不知道我还是把图放着
  • Pasted image 20260614160739.png