1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
"""Quick Sort based on double linkedlist
"""
import collections
import random
class :
def __init__(self, val):
self._pre = None
self._val = val
self._nxt = None
class DoubleLinkedListIterator(collections.Iterator):
def __init__(self, head):
self._head = head
def __iter__(self):
return self
def __next__(self):
if not self.has_next():
raise StopIteration
val = self._head._val
self._head = self._head._nxt
return val
def has_next(self):
return self._head != None
class DoubleLinkedList:
def __init__(self):
self._first = None
self._last = None
def create(self, array):
for val in array:
new_node = DataNode(val)
new_node._pre = self._last
if not self._first:
self._first = new_node
else:
self._last._nxt = new_node
new_node._pre = self._last
self._last = new_node
return self._first
def add(self, val):
new_node = DataNode(val)
new_node = self._last
if not self._first:
self._first = new_node
self._last = new_node
def show(self):
ptr = self._first
while ptr:
print(ptr._val, end=' ')
ptr = ptr._nxt
print()
def __iter__(self):
return DoubleLinkedListIterator(self._first)
def quick_sort(linkedlist, left, right):
if left and right and left != right and right._nxt != left:
pivot = partition(linkedlist, left, right)
quick_sort(linkedlist, left, pivot)
quick_sort(linkedlist, pivot._nxt, right)
def partition(linkedlist, left, right):
head, tail = left, right
pivot_node = left
while True:
cross = False
while head._val <= pivot_node._val:
head = head._nxt
if head == tail:
cross = True
if head == right:
break
while tail._val >= pivot_node._val:
tail = tail._pre
if head == tail:
cross = True
if tail == left:
break
if cross:
break
head._val, tail._val = tail._val, head._val
if left._val >= tail._val:
left._val, tail._val = tail._val, left._val
else:
tail = tail._nxt
return tail
nums = [2, 5, 2, 3, 3, 4]
head = DoubleLinkedList()
head.create(nums)
quick_sort(head, head._first, head._last)
print(list(head), 'nn', sorted(nums))
print(list(head) == sorted(nums))
nums = random.sample(
[random.randint(1, 100) for _ in range(100)], k=random.randint(1, 100)
)
head = DoubleLinkedList()
head.create(nums)
quick_sort(head, head._first, head._last)
print(list(head), 'nn', sorted(nums))
print(list(head) == sorted(nums))
|
近期评论