以单链表为存储结构的一组数据的简单选择排序算法。
时间: 2024-03-27 08:36:37 浏览: 61
简单选择排序是一种基于比较的排序算法,其基本思想是每次从未排序的元素中选择一个最小的元素,将其放到已排序的元素末尾。
对于单链表来说,简单选择排序的实现过程如下:
1. 从头节点开始遍历整个单链表,设当前节点为p,最小节点为min_node,最小节点的前驱节点为pre_min_node。
2. 在遍历过程中,记录当前节点的值与min_node的值进行比较,如果当前节点的值小于min_node的值,则更新min_node为当前节点,同时更新pre_min_node为当前节点的前驱节点。
3. 遍历结束后,将min_node节点从原链表中删除,并将其插入到已排序的节点的末尾。
4. 重复1-3步骤,直到所有节点都被排序完成。
以下是基于单链表的简单选择排序的实现代码:
```python
class Node:
def __init__(self, val=None):
self.val = val
self.next = None
def simple_select_sort(head):
if not head or not head.next:
return head
dummy = Node(0) # 创建哑节点
dummy.next = head
tail = dummy
while tail.next:
p = tail.next
min_node = p
pre_min_node = tail
while p.next:
if p.next.val < min_node.val:
min_node = p.next
pre_min_node = p
p = p.next
pre_min_node.next = min_node.next
min_node.next = tail.next
tail.next = min_node
tail = min_node
return dummy.next
```
时间复杂度为O(n^2),因为需要进行n次遍历,每次遍历需要找到最小节点。空间复杂度为O(1),因为只需要常数级别的额外空间。
阅读全文
相关推荐

















