用链表写一个插入排序算法
时间: 2023-11-09 12:07:55 浏览: 42
插入排序是一种简单直观的排序算法,它的基本思想是:将一个元素插入到已经排好序的序列中,使得插入后仍然保持有序。
下面是使用链表实现插入排序算法的示例代码:
```python
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_sort(head: Node) -> Node:
if not head or not head.next:
return head
dummy = Node(-1, head)
last_sorted = head
curr = head.next
while curr:
if last_sorted.val <= curr.val:
last_sorted = last_sorted.next
else:
prev = dummy
while prev.next.val <= curr.val:
prev = prev.next
last_sorted.next = curr.next
curr.next = prev.next
prev.next = curr
curr = last_sorted.next
return dummy.next
```
这里使用了一个哑节点(dummy node),它的作用是方便处理头节点的情况。last_sorted表示已经排好序的最后一个节点,curr表示当前需要插入的节点。如果curr的值比last_sorted的值大,就将last_sorted向后移动一位;否则,从哑节点开始往后遍历,找到第一个比curr的值大的节点,将curr插入到它的前面。最后返回哑节点的下一个节点即可。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)