2.4 链表选择排序
大约 2 分钟
2.4 链表选择排序
---1. 链表选择排序算法描述
- 使用两个指针
node_i
、node_j
。node_i
既可以用于控制外循环次数,又可以作为当前未排序链表的第一个链节点位置。 - 使用
min_node
记录当前未排序链表中值最小的链节点。 - 每一趟排序开始时,先令
min_node = node_i
(即暂时假设链表中node_i
节点为值最小的节点,经过比较后再确定最小值节点位置)。 - 然后依次比较未排序链表中
node_j.val
与min_node.val
的值大小。如果node_j.val < min_node.val
,则更新min_node
为node_j
。 - 这一趟排序结束时,未排序链表中最小值节点为
min_node
,如果node_i != min_node
,则将node_i
与min_node
值进行交换。如果node_i == min_node
,则不用交换。 - 排序结束后,继续向右移动
node_i
,重复上述步骤,在剩余未排序链表中寻找最小的链节点,并与node_i
进行比较和交换,直到node_i == None
或者node_i.next == None
时,停止排序。 - 返回链表的头节点
head
。
2. 链表选择排序实现代码
class Solution:
def sectionSort(self, head: ListNode):
node_i = head
# node_i 为当前未排序链表的第一个链节点
while node_i and node_i.next:
# min_node 为未排序链表中的值最小节点
min_node = node_i
node_j = node_i.next
while node_j:
if node_j.val < min_node.val:
min_node = node_j
node_j = node_j.next
# 交换值最小节点与未排序链表中第一个节点的值
if node_i != min_node:
node_i.val, min_node.val = min_node.val, node_i.val
node_i = node_i.next
return head
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.sectionSort(head)
3. 链表选择排序算法复杂度分析
- 时间复杂度:。
- 空间复杂度:。
练习题目
0148. 排序链表(链表选择排序会超时,仅做练习)