2.3 链表冒泡排序
大约 2 分钟
2.3 链表冒泡排序
---1. 链表冒泡排序算法描述
- 使用三个指针
node_i
、node_j
和tail
。其中node_i
用于控制外循环次数,循环次数为链节点个数(链表长度)。node_j
和tail
用于控制内循环次数和循环结束位置。 - 排序开始前,将
node_i
、node_j
置于头节点位置。tail
指向链表末尾,即None
。 - 比较链表中相邻两个元素
node_j.val
与node_j.next.val
的值大小,如果node_j.val > node_j.next.val
,则值相互交换。否则不发生交换。然后向右移动node_j
指针,直到node_j.next == tail
时停止。 - 一次循环之后,将
tail
移动到node_j
所在位置。相当于tail
向左移动了一位。此时tail
节点右侧为链表中最大的链节点。 - 然后移动
node_i
节点,并将node_j
置于头节点位置。然后重复第 3、4 步操作。 - 直到
node_i
节点移动到链表末尾停止,排序结束。 - 返回链表的头节点
head
。
2. 链表冒泡排序算法实现代码
class Solution:
def bubbleSort(self, head: ListNode):
node_i = head
tail = None
# 外层循环次数为 链表节点个数
while node_i:
node_j = head
while node_j and node_j.next != tail:
if node_j.val > node_j.next.val:
# 交换两个节点的值
node_j.val, node_j.next.val = node_j.next.val, node_j.val
node_j = node_j.next
# 尾指针向前移动 1 位,此时尾指针右侧为排好序的链表
tail = node_j
node_i = node_i.next
return head
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.bubbleSort(head)
3. 链表冒泡排序算法复杂度分析
- 时间复杂度:。
- 空间复杂度:。
4. 总结
链表冒泡排序使用三个指针进行操作。node_i
控制外层循环次数,node_j
和 tail
控制内层循环。每次比较相邻节点的值,需要交换时就交换。每次内循环结束后,最大的节点会移动到链表末尾。
这个算法的时间复杂度是 ,因为需要进行两层循环。空间复杂度是 ,因为只使用了固定数量的指针变量,没有使用额外空间。
链表冒泡排序适合小规模数据排序。对于大规模数据,其他排序算法可能更高效。实现时需要注意指针移动和节点交换的操作。
练习题目
0148. 排序链表(链表冒泡排序会超时,仅做练习)