以单链表为存储结构实现选择排序
时间: 2023-12-14 11:58:34 浏览: 63
好的,下面是以单链表为存储结构实现选择排序的示例代码:
```python
# 定义链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 选择排序函数
def selection_sort(head):
# 如果链表为空或只有一个元素,直接返回
if not head or not head.next:
return head
# 遍历链表,把链表转为列表方便排序
cur = head
nums = []
while cur:
nums.append(cur.val)
cur = cur.next
# 对列表进行选择排序,时间复杂度 O(n^2)
n = len(nums)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if nums[j] < nums[min_idx]:
min_idx = j
nums[i], nums[min_idx] = nums[min_idx], nums[i]
# 把排序后的列表重新构造成链表
dummy = ListNode(0)
cur = dummy
for i in range(n):
cur.next = ListNode(nums[i])
cur = cur.next
return dummy.next
```
尝试运行上述代码,你会发现它可以对单链表进行选择排序。如果有其他问题,请继续提问。