商城网站是怎么做的,wordpress小说站数据,营销策划的重要性,wordpress计数ip在数组排序中#xff0c;常见的排序算法有#xff1a;冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。
而对于链表排序而言#xff0c;因为链表不支持随机访问#xff0c;访问链表后面的节点只能依靠 next 指针从头…
在数组排序中常见的排序算法有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。
而对于链表排序而言因为链表不支持随机访问访问链表后面的节点只能依靠 next 指针从头部顺序遍历所以相对于数组排序问题来说链表排序问题会更加复杂一点。
下面先来总结一下适合链表排序与不适合链表排序的算法
适合链表的排序算法冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序。 不适合链表的排序算法希尔排序。 可以用于链表排序但不建议使用的排序算法堆排序。 希尔排序为什么不适合链表排序
希尔排序希尔排序中经常涉及到对序列中第 i gap 的元素进行操作其中 gap 是希尔排序中当前的步长。而链表不支持随机访问的特性导致这种操作不适合链表因而希尔排序算法不适合进行链表排序。
为什么不建议使用堆排序
堆排序堆排序所使用的最大堆 / 最小堆结构本质上是一棵完全二叉树。而完全二叉树适合采用顺序存储结构数组。因为数组存储的完全二叉树可以很方便的通过下标序号来确定父亲节点和孩子节点并且可以极大限度的节省存储空间。
而链表用在存储完全二叉树的时候因为不支持随机访问的特性导致其寻找子节点和父亲节点会比较耗时如果增加指向父亲节点的变量又会浪费大量存储空间。所以堆排序算法不适合进行链表排序。
如果一定要对链表进行堆排序则可以使用额外的数组空间表示堆结构。然后将链表中各个节点的值依次添加入堆结构中对数组进行堆排序。排序后再按照堆中元素顺序依次建立链表节点构建新的链表并返回新链表头节点。
刚才我们说到如果一定要对链表进行堆排序则需要使用额外的数组空间。除此之外计数排序、桶排序、基数排序都需要用到额外的数组空间。 链表归并排序通过 分割环节找到链表中心链节点从中心节点将链表断开并递归进行分割。 使用快慢指针 fast head.next、slow head让 fast 每次移动 2 步slow 移动 1 步移动到链表末尾从而找到链表中心链节点即 slow。 从中心位置将链表从中心位置分为左右两个链表 left_head 和 right_head并从中心位置将其断开即 slow.next None。 对左右两个链表分别进行递归分割直到每个链表中只包含一个链节点。
归并环节将递归后的链表进行两两归并完成一遍后每个子链表长度加倍。重复进行归并操作直到得到完整的链表。 使用哑节点 dummy_head 构造一个头节点并使用 cur 指向 dummy_head 用于遍历。 比较两个链表头节点 left 和 right 的值大小。将较小的头节点加入到合并后的链表中。并向后移动该链表的头节点指针。 然后重复上一步操作直到两个链表中出现链表为空的情况。 将剩余链表插入到合并中的链表中。 将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为合并后的头节点返回。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def merge(self,left,right):dummy_head ListNode(-1)cur dummy_headwhile left and right:if left.val right.val:cur.next leftleft left.nextelse:cur.next rightright right.nextcur cur.nextif left:cur.next leftelif right:cur.next rightreturn dummy_head.nextdef mergeSort(self,head:ListNode):if not head or not head.next:return head# 快慢指针找到中心链节点slow,fast head,head.nextwhile fast and fast.next:slow slow.nextfast fast.next.next# 断开左右链节点 left_head,right_head head, slow.nextslow.next None# 归并操作return self.merge(self.mergeSort(left_head),self.mergeSort(right_head))def sortList(self, head: Optional[ListNode]) - Optional[ListNode]:return self.mergeSort(head)
