Python双向链表快速排序1、创建链表：
from random import randint
class DLinkedNode(object):
def__init__(self, data=None, pre=None, post=None):
self.data = data
self.pre = pre
self.post = post
class DLinkedList(object):
def__init__(self):
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.post = self.tail
self.tail.pre = self.head
def build(self, n):
pre = self.head
for _ in range(n):
data = randint(1, 100)
node = DLinkedNode(data, post=self.tail)
self.tail.pre = node
pre.post = node
node.pre = pre
pre = node
return self.head, self.tail
快速排序python实现2、快速排序：
class Solution(object):
def quick_sort(self, low, high):
if not low or not low.post:
return
if low != high:
p, q = low, high
key = p.data
while p != q:
while p != q and q.data >= key:
q = q.pre
p.data = q.data
while p != q and p.data <= key:
p = p.post
q.data = p.data
p.data = key
if low != p:
self.quick_sort(low, p.pre)
if p != high:
self.quick_sort(p.post, high)
3、测试：
h, t = DLinkedList().build(10)
curr = h
while curr.post:
print curr.post.data,
curr = curr.post
print()
while curr.pre:
print curr.pre.data,
curr = curr.pre
print()
Solution().quick_sort(h.post, h.post, t.pre)
curr = h
while curr.post:
print curr.post.data,
curr = curr.post
list快速排序：
import random
class Solution(object):
def quick_sort(self, a, left, right):
if left >= right: return
pivot = self.partition(a, left, right)
self.quick_sort(a, left, pivot-1)
self.quick_sort(a, pivot+1, right)
def partition(self, a, left, right):
index = left + 1
key = a[left]
for i in range(left+1, right+1):
if a[i] <= key:
a[i], a[index] = a[index], a[i]
index += 1
a[left], a[index-1] = a[index-1], key
return index-1
if__name__ == '__main__':
a = [random.randint(0, 100) for _ in range(10)]
print(a)
Solution().quick_sort(a, 0, len(a)-1)
print(a)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。