请用python写出链表计数排序的代码
时间: 2023-08-31 16:36:47 浏览: 74
### 回答1:
答案:
def countSort(lst):
max_num = max(lst)
count_list = [0] * (max_num + 1)
for i in lst:
count_list[i] += 1
j = 0
for i in range(max_num + 1):
for k in range(count_list[i]):
lst[j] = i
j += 1
return lst
### 回答2:
链表计数排序是一种基于比较的排序算法,它利用链表的特性实现排序。具体步骤如下:
1. 定义一个链表节点的类,包含value和next两个属性。
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
```
2. 定义链表计数排序的函数,接受一个无序链表作为参数,返回排序后的链表。
```python
def linkedListCountingSort(head):
if not head or not head.next:
return head
# 计算链表的最小值和最大值
min_val = head.value
max_val = head.value
cur = head.next
while cur:
min_val = min(min_val, cur.value)
max_val = max(max_val, cur.value)
cur = cur.next
# 创建计数数组,并初始化为0
count = [0] * (max_val - min_val + 1)
# 遍历链表并统计元素出现的次数
cur = head
while cur:
count[cur.value - min_val] += 1
cur = cur.next
# 根据计数数组构建排序后的新链表
dummy = Node(0)
cur = dummy
for i in range(len(count)):
for j in range(count[i]):
cur.next = Node(i + min_val)
cur = cur.next
return dummy.next
```
以下为一个使用示例:
```python
# 创建无序链表:5 -> 2 -> 3 -> 1 -> 4
head = Node(5)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(1)
head.next.next.next.next = Node(4)
# 调用链表计数排序函数
sorted_head = linkedListCountingSort(head)
# 输出排序后的结果
cur = sorted_head
while cur:
print(cur.value, end=" ")
cur = cur.next
```
输出结果为:1 2 3 4 5,表示链表已经按照升序进行了排序。