2.10 链表基数排序
大约 2 分钟
2.10 链表基数排序
---1. 链表基数排序算法描述
- 使用
cur
指针遍历链表,获取节点值位数最长的位数size
。 - 从个位到高位遍历位数。因为
0
~9
共有10
位数字,所以建立10
个桶。 - 以每个节点对应位数上的数字为索引,将节点值放入到对应桶中。
- 建立一个哑节点
dummy_head
,作为链表的头节点。使用cur
指针指向dummy_head
。 - 将桶中元素依次取出,并根据元素值建立链表节点,并插入到新的链表后面。从而生成新的链表。
- 之后依次以十位,百位,…,直到最大值元素的最高位处值为索引,放入到对应桶中,并生成新的链表,最终完成排序。
- 将哑节点
dummy_dead
的下一个链节点dummy_head.next
作为新链表的头节点返回。
2. 链表基数排序代码实现
class Solution:
def radixSort(self, head: ListNode):
# 计算位数最长的位数
size = 0
cur = head
while cur:
val_len = len(str(cur.val))
if val_len > size:
size = val_len
cur = cur.next
# 从个位到高位遍历位数
for i in range(size):
buckets = [[] for _ in range(10)]
cur = head
while cur:
# 以每个节点对应位数上的数字为索引,将节点值放入到对应桶中
buckets[cur.val // (10 ** i) % 10].append(cur.val)
cur = cur.next
# 生成新的链表
dummy_head = ListNode(-1)
cur = dummy_head
for bucket in buckets:
for num in bucket:
cur.next = ListNode(num)
cur = cur.next
head = dummy_head.next
return head
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.radixSort(head)
3. 链表基数排序算法复杂度分析
- 时间复杂度:。其中 是待排序元素的个数, 是数字位数。 的大小取决于数字位的选择(十进制位、二进制位)和待排序元素所属数据类型全集的大小。
- 空间复杂度:。