标签：self img 时间 初始化 containe 数字 用两个 tpm table
快速排序思路：
1）选定一个基准元素；
2）经过一趟排序，将所有元素分成两部分；
3）分别对两部分重复上述操作，直到所有元素都已排序成功。
因为单链表只能从链表头节点向后遍历，没有prev指针，因此必须选择头节点作为基准元素。这样第二步操作的时间复杂度就为O(n)。由于之后都是分别对两部分完成上述操作，因此会将链表划分为logn个段，因此时间复杂度为O(nlogn) 。
可以看出，快排实现也是先对数据进行一遍遍历找到关键值得位置，和数组不同的是数组可以从两端向中间靠拢，但是单向链表只能从一段开始，但用两个指针同样可以实现。
图解示意：
以[4，2，5，3，7，9，0，1]为例模拟一趟快排的过程：
1、初始化时，i指向链表首元素4；j = i +1，指向2。基准数字为当前i 指向的数字：4。
2、随后开始循环，j 当前指向2，因为2小于4，所以要把2移动到前面去。
按照算法步骤操作：
- i ++，首先 i 向后移动一位，指向2；
- swap(i， j) ，随后交换 i、j 位置的值，这里面是2和2自己交换；
- j ++，然后 j 向后移动一位，指向5；
执行一次交换后的结果如下：
3、接下来，由于 j 指向的值5 大于4，直接跳过，执行j++，此时 j 指向3；
4、 j 指向的值为3，小于4，仿照步骤2，我们再次执行一次交换移动过程。
- i ++，首先 i 向后移动一位，指向5；
- swap(i， j) ，随后交换 i、j 位置的值，这里面是5和3交换；
- j ++，然后 j 向后移动一位，指向7；
交换后的结果如下：
5、j指向的值为7，大于4，所以直接跳过，执行 j++，j 指向9：
6、同理，j 指向的值为9，也大于4，跳过，执行 j++，j 指向0：
7、j 指向的值为0，小于4，执行一次交换过程：
- i ++，首先 i 向后移动一位，指向5
- swap(i， j) ，随后交换 i、j 位置的值，这里面是5和0交换
- j ++，然后 j 向后移动一位，指向1
交换后的结果如下：
8、j 指向的值为1，小于4，我们再执行一次交换过程
- i ++，首先 i 向后移动一位，指向7
- swap(i， j) ，随后交换 i、j 位置的值，这里面是7和1交换
- j ++，然后 j 向后移动一位，已经超过了链表的长度，不再向后移动。
交换后的结果如下：
9、最后，交换当前 i指向的值1，和4。得到[1、2、3、0、4、9、5、7]，一趟排序结束。
此时可见：4的左边都是小于4的数字，右边都是大于4的数字，一趟排序确定了一个数字最终位置。
接下来，对左边和右边分别排序，递归，直到元素全部有序。
代码实现：
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val):
self.val = val
self.next = None
class LinkList(object):
# 单链表快速排序
def quickSort(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
ans = ListNode(0)
ans.next = head
return self.sort(ans, None)
def sort(self, head, end):
if head == end or head.next == end or head.next.next == end:
return head
tpmHead = ListNode(0)
# 划分节点
poi = head.next
# 遍历指针
cur = poi
pre = tpmHead
# 一趟划分
while cur.next != end:
# 当前节点值域小于划分节点的值域，则将当前节点放到左侧
if cur.next.val
运行截图：
单链表快速排序
标签：self img 时间 初始化 containe 数字 用两个 tpm table
原文地址：https://www.cnblogs.com/panweiwei/p/12897773.html