一道题看快排
- 2019 年 10 月 5 日
- 笔记
一道题看快排
0.说在前面
1.排序链表2.快排实现2. 1 概括2.2 挖洞法2.3 双指针法3.作者的话
0.说在前面
今天除了早上没课，一天的满课，但是我仍然坚持发文了，仍然坚持做题了，你们吗？算法最优群各位同学加油啦！！！看最后有哪些坚持下来的！
今天研究的是排序链表，由这个排序链表衍生研究挖洞法与双指针法实现快排！同时在做排序链表完成后，学习了一位大佬的思路，并且手推排序，各位看不懂的可以留言，毕竟我写的字太搓了。。
1.排序链表
问题
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3 输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0 输出: -1->0->3->4->5
直接法
【思路】
直接遍历链表一次，O(n)时间复杂度，将所有节点值添加到list当中，并进行排序，排序时间复杂度O(logn)，那么最终的时间复杂度为O(nlogn)，但是空间复杂度为O(n)。
【实现】
def sortList(self, head): l = [] while head: l.append(head.val) head = head.next l.sort() p = head = ListNode(0) for i in l: p.next = ListNode(i) p = p.next p = head.next del head return p
冒泡排序
【思路】
这里采用冒泡排序算法进行实现，首先遍历一次链表，获取总结点个数，时间复杂度为O(n)，紧接着采用冒泡的O(n^2)时间复杂度进行排序，链表当中，每次将节点值较大的放在最后，这就是冒泡排序的一个优势，在每次排序后，可以得到一个节点在正确位置。空间复杂度为O(1)，这个学习一下就行，在网站上通不过。
【实现】
def sortList(self, head): p = head size = 0 while p: size += 1 p = p.next for i in range(size - 1): l = head for j in range(size - i - 1): p = l p1 = l.next if (p.val > p1.val): temp = p.val p.val = p1.val p1.val = temp l = l.next return head
快排一
【思路】
这里建议各位模拟一下实现，定义一个快指针与一个慢指针，然后通过快指针的元素与枢椎值比较，如果比枢椎小，则交换快慢指针元素值，否则快指针一直走到结尾，最后将慢指针的位置元素与枢椎元素之相交换就得到了一次快排结果，然后利用分治法，递归即可！最坏时间复杂度O(n^2)，最好O(nlogn)。空间复杂度O(1)。leetcode通不过，，，遗憾~
【实现】
def sortList(self, head): self.quickSort(head,None) return head def quickSort(self,head,tail): if head: slow = head fast = head.next while fast: if fast.val<head.val: slow = slow.next tmp = slow.val slow.val = fast.val fast.val = tmp fast = fast.next tmp = head.val head.val = slow.val slow.val = tmp if head != tail: self.quickSort(head,slow) self.quickSort(slow.next,None)
快排二
【参考】
这里参考自leetcode英文网站上的一个大佬代码：
https://leetcode.com/problems/sort-list/discuss/?orderBy=recent_activity
【思路】
【实现】
由于原始代码没有注释，为了更好的让大家学习这个代码，这里给出核心行注释！
这里说明一下一个链表的头结点与起始结点(第一个结点)的区别，一般链表为了方便操作统一，会创建一个头结点，也就是在一个链表的第一个结点前面创建一个结点，而这个结点就是头结点，例如原始链表为：1->3->4，那么加入头结点这为，假设头结点用x表示，则为x->1->3->4，那么在这个带有头结点的链表中，x为头结点，1为起始结点或者说第一个结点，对于头结点一个更特殊点在于，头结点没有数据，不包含任何值，所以在创建头结点的时候，直接创建一个空结点即可。在python中的创建头结点实现为：head = ListNode(0)或者head = ListNode(None)。
def sortList(self, head): # 头结点 hat = ListNode(None) # 指向链表起始节点 hat.next = head # 开始快排 self.quick_sort(hat, None) return hat.next def quick_sort(self,hat, tail): # 判断一开始所给链表至少2个节点以上 if hat.next is tail or hat.next.next is tail: return # hat1为小于枢椎链表的头结点 # hat2为等于枢椎链表的第一个结点 # hat3为大于枢椎链表的头结点 hat1, hat2, hat3 = hat, hat.next, ListNode(None) # 三个链表尾结点 tail1, tail2, tail3 = hat1, hat2, hat3 p, pivot = hat2.next, hat2.val while p is not tail: if p.val < pivot: tail1.next, tail1, p = p, p, p.next elif p.val == pivot: tail2.next, tail2, p = p, p, p.next else: tail3.next, tail3, p = p, p, p.next # 下面三行代码实现，将三个链表进行连接，构成一次排序后的链表！ # 大于枢椎的链表尾节点直接链接尾部结点 tail3.next = tail # 等于枢椎的链表连接大于枢椎链表，由于hat3为头结点，第一个结点为hat3.next tail2.next = hat3.next # 小于枢椎的链表连接等于枢椎链表的第一个结点 tail1.next = hat2 self.quick_sort(hat1, hat2) self.quick_sort(tail2, tail)
2.快排实现
2. 1 概括
由于这道题为链表，采用快排不是很方便，而在这里，顺时学了温故一下快排，这里给出两个方法，一个是挖洞法实现快排，另一个是双指针实现快排。
2.2 挖洞法
挖洞法实现快排思路是，选择一个数作为枢椎，将其与枢椎值相比较，此时比较过程为，假设枢椎选择第一个，那么从后往前遍历(左边index小于右边的index情况下)，直到找到比枢椎小的，将这个数挖去，也就是挖洞，然后填入前面枢椎位置，紧接着，从左往右找比枢椎大的(左边index小于右边的index情况下)，找到这个数，将其挖去，也就是挖洞，然后放在上一次的洞里面，填补，然后重复上述操作，最后将枢椎值填入最后左边与右边index相等的位置即可！
模拟图如下：
实现如下：
def qucikSort1(s,low,high): if low>high: return # 以第一个为枢椎 privor = s[low] i = low j = high while i<j: # 从右向左找比枢椎小的值，并挖洞 while i<j and s[j]>=privor: j-=1 # 开始填洞 if i<j: s[i]=s[j] i+=1 # 从左向右找比枢椎大的值，并挖洞 while i<j and s[i]<privor: i+=1 # 开始填洞 if i<j: s[j]=s[i] j-=1 # 枢椎填入ij相等位置 s[i] = privor # 分治法 qucikSort1(s,low,i-1) qucikSort1(s,i+1,high) return s l = [1,9,0,7,6] print("-------未排序前-------") print(l) print("-------排序后-------") print(qucikSort1(l,0,len(l)-1))
2.3 双指针法
双指针法实现快排，则是前后各一个指针，假设将第一个元素作为枢椎，那么循环的时候右边得先循环，这个解释看下面图即可！当左边index小于右边index的时候，先从右边遍历，找到比枢椎大的元素，然后找到了右边的index，也就是上面的挖洞处，开始处理左边的，找到比枢椎小的元素，然后找到了左边的index，也就是上面的挖洞出，此时左右两边洞口都找到了，那么让这两个位置元素进行交换，不断重复这个过程即可!
模拟图如下：
实现：
l = [1,9,0,7,6] def qucikSort(s,low,high): if low>high: return # 以第一个为枢椎 privor = s[low] i = low j = high while i<j: # 从右向左找比枢椎小的值 while i<j and s[j]>=privor: j-=1 # 从左向右找比枢椎大的值 while i<j and s[i]<=privor: i+=1 if i<j: tmp = s[i] s[i] = s[j] s[j] = tmp s[low] = s[i] s[i] = privor qucikSort(s,low,i-1) qucikSort(s,i+1,high) return s print("-------未排序前-------") print(l) print("-------排序后-------") print(qucikSort(l,0,len(l)-1))
