自己做配图的网站,微信小程序公众号开发,中国设计联盟网服务特点,php不用框架怎么做网站1. 链表排序简介
在数组排序中#xff0c;常见的排序算法有#xff1a;冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。
而对于链表排序而言#xff0c;因为链表不支持随机访问#xff0c;访问链表后面的节点只能依…1. 链表排序简介
在数组排序中常见的排序算法有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。
而对于链表排序而言因为链表不支持随机访问访问链表后面的节点只能依靠 next 指针从头部顺序遍历所以相对于数组排序问题来说链表排序问题会更加复杂一点。
下面先来总结一下适合链表排序与不适合链表排序的算法
适合链表的排序算法冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序。不适合链表的排序算法希尔排序。可以用于链表排序但不建议使用的排序算法堆排序。 希尔排序为什么不适合链表排序 希尔排序希尔排序中经常涉及到对序列中第 i gap 的元素进行操作其中 gap 是希尔排序中当前的步长。而链表不支持随机访问的特性导致这种操作不适合链表因而希尔排序算法不适合进行链表排序。 为什么不建议使用堆排序 堆排序堆排序所使用的最大堆 / 最小堆结构本质上是一棵完全二叉树。而完全二叉树适合采用顺序存储结构数组。因为数组存储的完全二叉树可以很方便的通过下标序号来确定父亲节点和孩子节点并且可以极大限度的节省存储空间。
而链表用在存储完全二叉树的时候因为不支持随机访问的特性导致其寻找子节点和父亲节点会比较耗时如果增加指向父亲节点的变量又会浪费大量存储空间。所以堆排序算法不适合进行链表排序。
如果一定要对链表进行堆排序则可以使用额外的数组空间表示堆结构。然后将链表中各个节点的值依次添加入堆结构中对数组进行堆排序。排序后再按照堆中元素顺序依次建立链表节点构建新的链表并返回新链表头节点。 需要用到额外的辅助空间进行排序的算法 刚才我们说到如果一定要对链表进行堆排序则需要使用额外的数组空间。除此之外计数排序、桶排序、基数排序都需要用到额外的数组空间。
接下来我们将对适合链表排序的 8 种算法进行一一讲解。当然这些排序算法不用完全掌握重点是掌握 「链表插入排序」、「链表归并排序」 这两种排序算法。
2. 链表冒泡排序
2.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.2 链表冒泡排序算法实现代码
class Solution:def bubbleSort(self, head: ListNode):node_i headtail None# 外层循环次数为 链表节点个数while node_i:node_j headwhile 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.valnode_j node_j.next# 尾指针向前移动 1 位此时尾指针右侧为排好序的链表tail node_jnode_i node_i.nextreturn headdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:return self.bubbleSort(head)2.3 链表冒泡排序算法复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)。空间复杂度 O ( 1 ) O(1) O(1)。
3. 链表选择排序
3.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。
3.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_inode_j node_i.nextwhile node_j:if node_j.val min_node.val:min_node node_jnode_j node_j.next# 交换值最小节点与未排序链表中第一个节点的值if node_i ! min_node:node_i.val, min_node.val min_node.val, node_i.valnode_i node_i.nextreturn headdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:return self.sectionSort(head)3.3 链表选择排序算法复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)。空间复杂度 O ( 1 ) O(1) O(1)。
4. 链表插入排序
4.1 链表插入排序算法描述 先使用哑节点 dummy_head 构造一个指向 head 的指针使得可以从 head 开始遍历。 维护 sorted_list 为链表的已排序部分的最后一个节点初始时sorted_list head。 维护 prev 为插入元素位置的前一个节点维护 cur 为待插入元素。初始时prev headcur head.next。 比较 sorted_list 和 cur 的节点值。 如果 sorted_list.val cur.val说明 cur 应该插入到 sorted_list 之后则将 sorted_list 后移一位。如果 sorted_list.val cur.val说明 cur 应该插入到 head 与 sorted_list 之间。则使用 prev 从 head 开始遍历直到找到插入 cur 的位置的前一个节点位置。然后将 cur 插入。 令 cur sorted_list.next此时 cur 为下一个待插入元素。 重复 4、5 步骤直到 cur 遍历结束为空。返回 dummy_head 的下一个节点。
4.2 链表插入排序实现代码
class Solution:def insertionSort(self, head: ListNode):if not head or not head.next:return headdummy_head ListNode(-1)dummy_head.next headsorted_list headcur head.next while cur:if sorted_list.val cur.val:# 将 cur 插入到 sorted_list 之后sorted_list sorted_list.next else:prev dummy_headwhile prev.next.val cur.val:prev prev.next# 将 cur 到链表中间sorted_list.next cur.nextcur.next prev.nextprev.next curcur sorted_list.next return dummy_head.nextdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:return self.insertionSort(head)4.3 链表插入排序算法复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)。空间复杂度 O ( 1 ) O(1) O(1)。
5. 链表归并排序
5.1 链表归并排序算法描述
分割环节找到链表中心链节点从中心节点将链表断开并递归进行分割。 使用快慢指针 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 作为合并后的头节点返回。
5.2 链表归并排序实现代码
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.next fast fast.next.next # 断开左右链节点left_head, right_head head, slow.next slow.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)5.3 链表归并排序算法复杂度分析
时间复杂度 O ( n × log 2 n ) O(n \times \log_2n) O(n×log2n)。空间复杂度 O ( 1 ) O(1) O(1)。
6. 链表快速排序
6.1 链表快速排序算法描述
从链表中找到一个基准值 pivot这里以头节点为基准值。然后通过快慢指针 node_i、node_j 在链表中移动使得 node_i 之前的节点值都小于基准值node_i 之后的节点值都大于基准值。从而把数组拆分为左右两个部分。再对左右两个部分分别重复第二步直到各个部分只有一个节点则排序结束。
6.2 链表快速排序实现代码
class Solution:def partition(self, left: ListNode, right: ListNode):# 左闭右开区间没有元素或者只有一个元素直接返回第一个节点if left right or left.next right:return left# 选择头节点为基准节点pivot left.val# 使用 node_i, node_j 双指针保证 node_i 之前的节点值都小于基准节点值node_i 与 node_j 之间的节点值都大于等于基准节点值node_i, node_j left, left.nextwhile node_j ! right:# 发现一个小与基准值的元素if node_j.val pivot:# 因为 node_i 之前节点都小于基准值所以先将 node_i 向右移动一位此时 node_i 节点值大于等于基准节点值node_i node_i.next# 将小于基准值的元素 node_j 与当前 node_i 换位换位后可以保证 node_i 之前的节点都小于基准节点值node_i.val, node_j.val node_j.val, node_i.valnode_j node_j.next# 将基准节点放到正确位置上node_i.val, left.val left.val, node_i.valreturn node_idef quickSort(self, left: ListNode, right: ListNode):if left right or left.next right:return leftpi self.partition(left, right)self.quickSort(left, pi)self.quickSort(pi.next, right)return leftdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:if not head or not head.next:return headreturn self.quickSort(head, None)6.3 链表快速排序算法复杂度分析
时间复杂度 O ( n × log 2 n ) O(n \times \log_2n) O(n×log2n)。空间复杂度 O ( 1 ) O(1) O(1)。
7. 链表计数排序
7.1 链表计数排序算法描述
使用 cur 指针遍历一遍链表。找出链表中最大值 list_max 和最小值 list_min。使用数组 counts 存储节点出现次数。再次使用 cur 指针遍历一遍链表。将链表中每个值为 cur.val 的节点出现次数存入数组对应第 cur.val - list_min 项中。反向填充目标链表 建立一个哑节点 dummy_head作为链表的头节点。使用 cur 指针指向 dummy_head。从小到大遍历一遍数组 counts。对于每个 counts[i] ! 0 的元素建立一个链节点值为 i list_min将其插入到 cur.next 上。并向右移动 cur。同时 counts[i] - 1。直到 counts[i] 0 后继续向后遍历数组 counts。 将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为新链表的头节点返回。
7.2 链表计数排序代码实现
class Solution:def countingSort(self, head: ListNode):if not head:return head# 找出链表中最大值 list_max 和最小值 list_minlist_min, list_max float(inf), float(-inf)cur headwhile cur:if cur.val list_min:list_min cur.valif cur.val list_max:list_max cur.valcur cur.nextsize list_max - list_min 1counts [0 for _ in range(size)]cur headwhile cur:counts[cur.val - list_min] 1cur cur.nextdummy_head ListNode(-1)cur dummy_headfor i in range(size):while counts[i]:cur.next ListNode(i list_min)counts[i] - 1cur cur.nextreturn dummy_head.nextdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:return self.countingSort(head)7.3 链表计数排序算法复杂度分析
时间复杂度 O ( n k ) O(n k) O(nk)其中 k k k 代表待排序链表中所有元素的值域。空间复杂度 O ( k ) O(k) O(k)。
8. 链表桶排序
8.1 链表桶排序算法描述
使用 cur 指针遍历一遍链表。找出链表中最大值 list_max 和最小值 list_min。通过 (最大值 - 最小值) / 每个桶的大小 计算出桶的个数即 bucket_count (list_max - list_min) // bucket_size 1 个桶。定义数组 buckets 为桶桶的个数为 bucket_count 个。使用 cur 指针再次遍历一遍链表将每个元素装入对应的桶中。对每个桶内的元素单独排序可以使用链表插入排序、链表归并排序、链表快速排序等算法。最后按照顺序将桶内的元素拼成新的链表并返回。
8.2 链表桶排序代码实现
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass Solution:# 将链表节点值 val 添加到对应桶 buckets[index] 中def insertion(self, buckets, index, val):if not buckets[index]:buckets[index] ListNode(val)returnnode ListNode(val)node.next buckets[index]buckets[index] node# 归并环节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.next fast fast.next.next # 断开左右链节点left_head, right_head head, slow.next slow.next None# 归并操作return self.merge(self.mergeSort(left_head), self.mergeSort(right_head)) def bucketSort(self, head: ListNode, bucket_size5):if not head:return head# 找出链表中最大值 list_max 和最小值 list_minlist_min, list_max float(inf), float(-inf)cur headwhile cur:if cur.val list_min:list_min cur.valif cur.val list_max:list_max cur.valcur cur.next# 计算桶的个数并定义桶bucket_count (list_max - list_min) // bucket_size 1buckets [[] for _ in range(bucket_count)]# 将链表节点值依次添加到对应桶中cur headwhile cur:index (cur.val - list_min) // bucket_sizeself.insertion(buckets, index, cur.val)cur cur.nextdummy_head ListNode(-1)cur dummy_head# 将元素依次出桶并拼接成有序链表for bucket_head in buckets:bucket_cur self.mergeSort(bucket_head)while bucket_cur:cur.next bucket_curcur cur.nextbucket_cur bucket_cur.nextreturn dummy_head.nextdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:return self.bucketSort(head)8.3 链表桶排序算法复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n m ) O(n m) O(nm)。 m m m 为桶的个数。
9. 链表基数排序
9.1 链表基数排序算法描述
使用 cur 指针遍历链表获取节点值位数最长的位数 size。从个位到高位遍历位数。因为 0 ~ 9 共有 10 位数字所以建立 10 个桶。以每个节点对应位数上的数字为索引将节点值放入到对应桶中。建立一个哑节点 dummy_head作为链表的头节点。使用 cur 指针指向 dummy_head。将桶中元素依次取出并根据元素值建立链表节点并插入到新的链表后面。从而生成新的链表。之后依次以十位百位…直到最大值元素的最高位处值为索引放入到对应桶中并生成新的链表最终完成排序。将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为新链表的头节点返回。
9.2 链表基数排序代码实现
class Solution:def radixSort(self, head: ListNode): # 计算位数最长的位数size 0cur headwhile cur:val_len len(str(cur.val))if val_len size:size val_lencur cur.next# 从个位到高位遍历位数for i in range(size):buckets [[] for _ in range(10)]cur headwhile cur:# 以每个节点对应位数上的数字为索引将节点值放入到对应桶中buckets[cur.val // (10 ** i) % 10].append(cur.val)cur cur.next# 生成新的链表dummy_head ListNode(-1)cur dummy_headfor bucket in buckets:for num in bucket:cur.next ListNode(num)cur cur.nexthead dummy_head.nextreturn headdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:return self.radixSort(head)9.3 链表基数排序算法复杂度分析
时间复杂度 O ( n × k ) O(n \times k) O(n×k)。其中 n n n 是待排序元素的个数 k k k 是数字位数。 k k k 的大小取决于数字位的选择十进制位、二进制位和待排序元素所属数据类型全集的大小。空间复杂度 O ( n k ) O(n k) O(nk)。
